Pythonで学ぶアルゴリズム（二分探索とデータ構造）

# はじめに
本記事は、Pythonによるアルゴリズム（二分探索とデータ構造）の検証結果のまとめです。

## 仮説
二分探索をPythonで記述する場合、合わせてデータ構造を考慮すると、Pythonでもリストより配列の方が早いと考えました。配列の場合、連続的にメモリのアドレスを確保し、ランダムアクセスやすべての要素を瞬時に調べることができるためです。対して、リストだと10番目の要素を読み取りたい場合は、9番目の要素を読み取って10番目の要素をたどる必要があるなど、総合的に配列の方が早いと思いました。

## 検証
1億個の要素から、目的の要素を見つけるのにかかる計算時間を計測します。
まずは、学習がてら単純探索より、二分探索が早いことを確認します。
次に、二分探索でリストと配列の場合での計算時間を計測します。

環境：MacBook Air
プロセッサ名:Intel Core i5
プロセッサ速度:1.6 GHz
メモリ:4 GB

### 単純探索
まずは、試しに以下のプログラムを実行し、単純探索でかかる計算時間を見てみます。

- simple_search.py

```python
my_list = []
for i in range(100000000):
    my_list.append(i)

def simple_search(list, item):
    for i in list:
        guess = i
        if guess == item:
            return guess

print(simple_search(my_list, 77777777))
```

timeコマンドでsimple_search.pyを実行したところ、約3分ほどかかりました。

```console
$ time python3 simple_search.py 
77777777

real	2m56.905s
user	0m59.758s
sys	    0m53.585s
```

### 二分探索
binary_search関数は、ソート済みの配列とアイテムを1つずつ受け取ります。そのアイテムが配列に含まれている場合、その位置（インデックス）の値を返します。

二分探索の検証では、binary_search.pyとbinary_search2.pyのプログラムを使用します。
binary_search関数の動きは同じですが、データを用意する方法をそれぞれ変えました。

binary_search.pyは、forでデータを取り出し、リストに追加して用意します。
binary_search2.pyは、リスト内包表記でデータを取り出し、Numpyの一次元配列に格納して用意します。

- binary_search.py

```python
my_list = []
for i in range(100000000):
    my_list.append(i)

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    return None

print (binary_search(my_list, 77777777))
```

timeコマンドでsimple_search.pyを実行したところ、約1分半ほどかかりました。
想定通りですが、二分探索の方が単純探索より早いです。

```console
$ time python3 binary_search.py 
77777777

real	1m34.540s
user	0m43.687s
sys	    0m38.348s
```
- binary_search2.py

```python
import numpy as np

my_list = np.array([i for i in range(100000000)])

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    return None

print (binary_search(my_list, 77777777))
```

データをリスト内包表記にして、Numpyに置き換えて実行すれば、リストより早いと考えていましたが、1回目はリストの方に軍配が上がりました。


```console
77777777

real	1m57.078s
user	0m41.351s
sys	    0m43.036s
```

## 検証結果
検証の精度を上げるため、それぞれ、3回ずつ実行した結果が以下になります。

| 二分探索（リスト）       | 二分探索（配列）      | 
|:-----------------|:------------------|
|1回目：1m34.540s   |1回目：1m57.078s            |
|2回目：1m56.788s   |2回目：1m24.709s            |
|3回目：1m33.924s   |3回目：1m28.110s            |
|平均：1m41.751s    |平均：1m36.632s             |

上記より、3回ずつ実行した結果の平均では、仮説の通りに二分探索（リスト）より、二分探索（配列）の早い（※）ことが確認できました。

（※）但し、1回目のタイムのように、キャッシュしていない状態だと、二分探索（リスト）の方が早い場合があります。

### キャッシュメモリ
それぞれ、2回目以降のタイムが1回目より早くなっているのは、キャッシュするためです。

Intelプロセッサではキャッシュメモリが3段になっており、CPUがメモリアクセスを行うときに、まずはキャッシュメモリを見に行き、キャッシュメモリにない場合はメインメモリからデータをキャッシュメモリにコピーして使います。また、メインメモリにもキャッシュがあるので、同様の動きをします。

一般的には、キャッシュメモリへデータをコピーする場合は、ブロック呼ばれる単位で、まとめてコピーします。L1キャッシュの場合は64バイト単位でコピーされます。よって、配列のアクセスを行う場合は、連絡的にアクセスすると効率的です。

参考：今回のプログラムは単純ですが、コンテナや1GBのラズパイで試したところ、OOM Killerが発生しました。Numpyでメモリ消費を抑える場合は、dtype=np.float32を使用するといいかもしれません。

# おわりに
プログラミングを学ぶことができるWebサービスはたくさんありますが、アルゴリズムについて教えてくれているサイトはあまりないような気がします。

プログラミング言語は、あくまでサービスを実現する手段なので、本質的なところを突き詰めるのもおもしろいです。次は、システムコールの呼びだしからメモリがどのように確保されるかなど、もっと掘り下げて検証したいと思います。