Published on

Pythonでデータ構造

Authors
  • avatar
    Name
    Kikusan
    Twitter

Refs

アルゴリズムとデータ構造について、コーディング試験対策も交えて教えてくれています。
一部のアルゴリズムとデータ構造についての抜粋と自分なりのコメントアウトです。

Big O 記法

アルゴリズムの計算量を表記する記法。

データ量をnとして、O(n)というような式で表す。

O(1) < O(logn) < O(n) < O(n2)

ソート

Bubbleソート

次の要素と比較置換を繰り返し、端から要素を確定していくソート。

計算量: O(n2)

def bubble_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(len_numbers):
        # limit内で隣の要素を比べていく
        # [- i] はlimitの引き下げ。i=1のとき、末尾1つは一番大きいものと確定している
        for j in range(len_numbers - 1 - i):
            # 次要素と比較し、大きいものは末尾へ
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

    return numbers

Selectionソート

先頭から要素を比較していき、tmp領域に保持する。先頭から要素を確定していく。
BubbleSortの改良版。

計算量: O(n2)

def selection_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        # 先頭の要素をtmpとして保持
        min_idx = i
        # [i+1]はstart要素を次に移す。 i=1のとき、先頭1つは一番小さいもので確定している
        for j in range(i+1, len(numbers)):
            # 次以降の要素と比較し、最小をtmpとして保持
            if numbers[min_idx] > numbers[j]:
                min_idx = j
        # 先頭を確定
        numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
    return numbers

Insertionソート

一つの値に着目し、正しい位置まで置換を繰り返す。

計算量: O(n2)

def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    # 先頭の1つ後から
    for i in range(1, len_numbers):
        # 1つの値に着目
        temp = numbers[i]
        j = i - 1
        # 着目した値が正しい位置にくるまで
        while j >= 0 and numbers[j] > temp:
            # 値を右に一つずらす
            numbers[j + 1] = numbers[j]
            # 一つ左の要素と比較
            j -= 1

        # 正しい位置に挿入する
        numbers[j + 1] = temp

    return numbers

Shellソート

要素数を2で割った値をgapとして利用する。
InsertionSortを計算量が減るようにしたもの。

計算量: O(n logn) ～ O(n2)

def shell_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    # 要素数を2で切り捨て除算した値をgapとする. 大体中央値
    gap = len_numbers // 2
    while gap > 0:
        # gapから最後まで
        for i in range(gap, len_numbers):
            # tempに値を保持
            temp = numbers[i]
            j = i
            # 値が正しい位置にくるまでgap分左に離れた値と比較する
            while j >= gap and numbers[j-gap] > temp:
                # 右側に値を詰める
                numbers[j] = numbers[j-gap]
                j -= gap
            # 正しい位置に挿入する
            numbers[j] = temp
        # gapを2で切り捨て除算する. 0になるまで繰り返す
        gap //= 2

    return numbers

Quickソート

リストを大小で分割していき、ソートする。

計算量: O(n logn)

def partition(numbers: List[int], low: int, high: int) -> int:
    i = low - 1 # i partition_index - 1 になる
    pivot = numbers[high] # 末尾をパーティションの値として利用
    # high - 1 の位置まで
    for j in range(low, high):
        # パーティションより小さい値は左に詰める
        if numbers[j] <= pivot:
            i += 1 # 詰める位置(partition_index)をインクリメント
            # 詰める
            numbers[i], numbers[j] = numbers[j], numbers[i]
    # パーティションの値をpartition_indexに詰める
    numbers[i+1], numbers[high] = numbers[high], numbers[i+1]
    return i+1


def quick_sort(numbers: List[int]) -> List[int]:
    def _quick_sort(numbers: List[int], low: int, high: int) -> None:
        # 全ての要素が比較し終わるまで
        if low < high:
            # パーティションのindexを取得する
            # 同時にhighのindexの値の左:小, 右:大になるよう並べ替える
            partition_index = partition(numbers, low, high)
            # パーティションより左を再帰的にクイックソート
            _quick_sort(numbers, low, partition_index-1)
            # パーティションより右を再帰的にクイックソート
            _quick_sort(numbers, partition_index+1, high)

    _quick_sort(numbers, 0, len(numbers)-1)
    return numbers

Mergeソート

リストを位置で分割していき、ソートする。

計算量: O(n logn)

def merge_sort(numbers: List[int]) -> List[int]:
    # 要素数が1なら抜ける
    if len(numbers) <= 1:
        return numbers

    # 前半と後半で分ける
    center = len(numbers) // 2
    left = numbers[:center]
    right = numbers[center:]

    # 再帰的に左と右をソートする
    merge_sort(left)
    merge_sort(right)

    # 左と右の要素を順番に比べていきnumbersに詰めかえる
    l = r = n = 0
    # 小さなものは左へ
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            numbers[n] = left[l]
            l += 1
        else:
            numbers[n] = right[r]
            r += 1
        n += 1

    # 大きなものは右へ
    while l < len(left):
        numbers[n] = left[l]
        l += 1
        n += 1
    while r < len(right):
        numbers[n] = right[r]
        r += 1
        n += 1

    return numbers

LinearSearch(線形探索)

先頭から探していくサーチ方法

計算量: O(n)

from typing import List, NewType


IndexNum = NewType('IndexNum', int)


def linear_search(numbers: List[int], value: int) -> IndexNum:
    for i in range(0, len(numbers)):
        if numbers[i] == value:
            return i
    return -1

BinarySearch(2分探索)

整列されたデータに限り計算量を減らせる分割探索法

計算量: O(logn)

from typing import List, NewType


IndexNum = NewType('IndexNum', int)


def binary_search(numbers: List[int], value: int) -> IndexNum:
    """whileで書いた場合"""
    left, right = 0, len(numbers) - 1
    while left <= right:
        mid = (left + right) // 2
        if numbers[mid] == value:
            return mid
        elif numbers[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1


def binary_search(numbers: List[int], value: int) -> IndexNum:
    """再帰で書いた場合"""
    def _binary_search(numbers: List[int], value: int,
                       left: IndexNum, right: IndexNum) -> IndexNum:
        if left > right:
            return -1

        mid = (left + right) // 2
        if numbers[mid] == value:
            return mid
        elif numbers[mid] < value:
            return _binary_search(numbers, value, mid + 1, right)
        else:
            return _binary_search(numbers, value, left, mid - 1)

    return _binary_search(numbers, value, 0, len(numbers) - 1)

リンクリスト

要素をポインタで繋ぐデータ構造。末尾要素はNull(None)

単方向リンクリスト

片方向からのみ繋がっているリンクリスト

from __future__ import annotations
from typing import Any


class Node(object):
    """データとポインタを持つデータ構造"""
    def __init__(self, data: Any, next_node: Node = None):
        self.data = data
        self.next = next_node


class LinkedList(object):
    """単方向リンクリスト"""
    def __init__(self, head=None) -> None:
        # 先頭データ
        self.head = head

    def append(self, data: Any) -> None:
        """末尾にノードを追加"""
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        # 先頭データでない場合
        last_node = self.head
        # 末尾までノードをたどる
        while last_node.next:
            last_node = last_node.next
        # 新ノードを追加
        last_node.next = new_node

    def insert(self, data: Any) -> None:
        """先頭にノードを追加"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def remove(self, data: Any) -> None:
        """一致するデータを持つノードを1つ削除する"""
        # 先頭の場合
        current_node = self.head
        if current_node and current_node.data == data:
            self.head = current_node.next
            current_node = None
            return

        # 先頭以外の場合
        previous_node = None
        # 一致するデータではない場合
        while current_node and current_node.data != data:
            # 前のノードを保持
            previous_node = current_node
            # 次のノードを探す
            current_node = current_node.next
        # 削除するものがない場合
        if current_node is None:
            return
        # 前のノードのポインタに次のノードをつなく
        previous_node.next = current_node.next
        current_node = None

双方向リンクリスト

両末端から繋がっているリンクリスト
ノードに前ポインタと次ポインタを持つ。
先頭のデータの前ポインタは、Null(None)を指す。

from __future__ import annotations
from typing import Any, Optional


class Node(object):
    def __init__(self, data: Any, next_node: Node = None, prev_node: Node = None) -> None:
        self.data = data
        self.next = next_node
        self.prev = prev_node


class DoublyLinkedList(object):

    def __init__(self, head: Node = None) -> None:
        self.head = head

    def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
        new_node.prev = current_node

    def insert(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

    def remove(self, data: Any) -> Node:
        current_node = self.head
        if current_node and current_node.data == data:
            if current_node.next is None:
                current_node = None
                self.head = None
                return
            else:
                next_node = current_node.next
                next_node.prev = None
                current_node = None
                self.head = next_node
                return

        while current_node and current_node.data != data:
            current_node = current_node.next

        if current_node is None:
            return

        if current_node.next is None:
            prev = current_node.prev
            prev.next = None
            current_node = None
            return
        else:
            next_node = current_node.next
            prev_node = current_node.prev
            prev_node.next = next_node
            next_node.prev = prev_node
            current_node = None
            return

ハッシュテーブル

データの格納位置をハッシュ値で保存するデータ構造
key=value型のデータで、keyをハッシュ関数でハッシュ値に変換して一意な位置になるようにする。
実現には基本的に配列が利用され、ハッシュ値は基本的に配列のIndexになる。

import hashlib
from typing import Any


class HashTable(object):

    def __init__(self, size=10) -> None:
        self.size = size
        # [[[key, value], [same_hash_key, value]], [another_hash_key, value]] indexはhash値
        self.table = [[] for _ in range(self.size)]

    def hash(self, key) -> int:
        """
        ハッシュ関数
        何度実行しても同じkeyからは同じIndexが算出される
        """
        return int(hashlib.md5(key.encode()).hexdigest(), base=16) % self.size

    def add(self, key, value) -> None:
        """
        要素追加関数
        衝突した場合はオープンアドレス法ではなくチェーン法を採用
        """
        index = self.hash(key)
        # Indexを指定して追加
        for data in self.table[index]:
            # 同じkeyの場合上書き
            if data[0] == key:
                data[1] = value
                break
        else:
            self.table[index].append([key, value])

    def get(self, key) -> Any:
        index = self.hash(key)
        for data in self.table[index]:
            if data[0] == key:
                return data[1]

    def __setitem__(self, key, value) -> None:
        """HashTable[key]で値を挿入した場合に呼ばれる特別関数"""
        self.add(key, value)

    def __getitem__(self, key) -> Any:
        """HashTable[key]で値を取得した場合に呼ばれる特別関数"""
        return self.get(key)

スタック

LIFOのデータ構造

from typing import Any


class Stack(object):

    def __init__(self) -> None:
        self.stack = []

    def push(self, data) -> None:
        self.stack.append(data)

    def pop(self) -> Any:
        if self.stack:
            return self.stack.pop()

キュー

FIFOのデータ構造

from collections import deque
from typing import Any


class Queue(object):

    def __init__(self) -> None:
        self.queue = []

    def enqueue(self, data: Any) -> None:
        self.queue.append(data)

    def dequeue(self) -> Any:
        if self.queue:
            return self.queue.pop(0)

ツリー

親子関係で階層構造を表すデータ構造

Binary Search Tree (二分探索木)

各節(node)が最大2つの子を持てるツリー(二分木)のうち、
左部分木に属するnodeはそのnodeの値より小さく、右部分木に属するnodeはそのnodeの値より大きいもの。

class Node(object):
    def __init__(self, value: int) -> None:
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree(object):

    def __init__(self) -> None:
        self.root = None

    def insert(self, value: int) -> None:
        """node追加関数"""
        if self.root is None:
            self.root = Node(value)
            return

        def _insert(node: Node, value: int) -> Node:
            """引数のnodeに属する、最深ノードにvalueを挿入する"""
            # nodeが無ければ追加
            if node is None:
                return Node(value)

            # valueの大小により、再帰的に最深部を探索する
            if value < node.value:
                node.left = _insert(node.left, value)
            else:
                node.right = _insert(node.right, value)
            return node

        # rootから探索
        _insert(self.root, value)

    def inorder(self) -> None:
        """Left Root Rightの順に表示する関数"""
        def _inorder(node: Node) -> None:
            if node is not None:
                # 再帰呼び出し
                _inorder(node.left) # 左は必ず小さい
                print(node.value)
                _inorder(node.right) # 右は必ず大きい
        _inorder(self.root)

    def search(self, value: int) -> bool:
        """値の存在をチェックする関数"""
        def _search(node: Node, value: int) -> bool:
            # 末端までに無ければFalse
            if node is None:
                return False

            # 再帰的に探索
            if node.value == value:
                return True
            elif node.value > value:
                return _search(node.left, value)
            elif node.value < value:
                return _search(node.right, value)
        return _search(self.root, value)

    def min_value(self, node: Node) -> Node:
        """node以下から一番小さいnodeを返す関数"""
        current = node
        while current.left is not None:
            current = current.left
        return current

    def remove(self, value: int) -> None:
        """指定の値を持つnodeを1つ削除する関数"""
        def _remove(node: Node, value: int) -> Node:
            if node is None:
                return node

            # 再帰的に探索
            if value < node.value:
                node.left = _remove(node.left, value)
            elif value > node.value:
                node.right = _remove(node.right, value)
            # 一致した場合
            else:
                if node.left is None:
                    return node.right # 左がなければ右を返す
                elif node.right is None:
                    return node.left # 右がなければ左を返す
                # 左も右もある場合右から最小nodeを現在のnodeに入れる
                temp = self.min_value(node.right) # 右の最小は必ず現在ノード以上の値
                node.value = temp.value
                node.right = _remove(node.right, temp.value) # 右の枝を再構成する
            return node
        _remove(self.root, value)

Heap

深さの浅い順に左詰めにした二分木のうち、どの親子にも一定の大小関係があるもの。
Mini Heap : rootが一番小さいもの。 HeapSort : 計算量: O(n logn) : Heapの親を取り出す操作を続けて、sortする手法。

import sys
from typing import Optional


class MiniHeap(object):

    def __init__(self) -> None:
        self.heap = [-1 * sys.maxsize] # system内最小値 index: 0
        self.current_size = 0

    def parent_index(self, index: int) -> int:
        return index // 2 # 完全二分木なので2で割った商が親のindexになる

    def left_child_index(self, index: int) -> int:
        return 2 * index # 2倍で左の子のindex

    def right_child_index(self, index: int) -> int:
        return (2 * index) + 1 # 2倍+1で右の子のindex

    def swap(self, index1: int, index2: int) -> None:
        """indexを指定して値を交換する"""
        self.heap[index1], self.heap[index2] = self.heap[index2], self.heap[index1]

    def heapify_up(self, index: int) -> None:
        """子からrootに向かって、親のほうが値が小さいとき交換する"""
        while self.parent_index(index) > 0:
            if self.heap[index] < self.heap[self.parent_index(index)]:
                self.swap(index, self.parent_index(index))
            index = self.parent_index(index) # 親をindexとして繰り返す

    def push(self, value: int) -> None:
        """heapにnodeを追加し、並び変える"""
        self.heap.append(value)
        self.current_size += 1
        self.heapify_up(self.current_size)

    def min_child_index(self, index: int) -> int:
        """下に向かって、heapで一番小さい値のindexを取得する"""
        # 右の子がなければ左の子で確定
        if self.right_child_index(index) > self.current_size:
            return self.left_child_index(index)
        else:
            # 左と右で小さいほうの値を持つindexを返す
            if (self.heap[self.left_child_index(index)] <
                self.heap[self.right_child_index(index)]):
                return self.left_child_index(index)
            else:
                return self.right_child_index(index)

    def heapify_down(self, index: int) -> None:
        """下に向かって、indexの値が正しい位置になるまで置換し続ける"""
        while self.left_child_index(index) <= self.current_size: # 最後の要素まで
            # 直下の子の小さいほうの値を取得
            min_child_index = self.min_child_index(index)
            # 子のほうが小さければ交換する
            if self.heap[index] > self.heap[min_child_index]:
                self.swap(index, min_child_index)
            index = min_child_index # 交換先をindexとして繰り返す

    def pop(self) -> Optional[int]:
        """rootを取り出し、heapを再構成する"""
        if len(self.heap) == 1:
            return

        root = self.heap[1]
        # heap末尾のデータを保持 (List.pop())
        data = self.heap.pop()
        if len(self.heap) == 1:
            return root

        # 末尾データをrootとして、heapを再構成する
        self.heap[1] = data
        self.current_size -= 1
        self.heapify_down(1)
        return root
Discuss on Twitter