はじめに
本記事は、Pythonによるアルゴリズム（二分探索とデータ構造）の検証結果のまとめです。
仮説
二分探索をPythonで記述する場合、合わせてデータ構造を考慮すると、Pythonでもリストより配列の方が早いと考えました。配列の場合、連続的にメモリのアドレスを確保し、ランダムアクセスやすべての要素を瞬時に調べることができるためです。対して、リストだと10番目の要素を読み取りたい場合は、9番目の要素を読み取って10番目の要素をたどる必要があるなど、総合的に配列の方が早いと思いました。
検証
1億個の要素から、目的の要素を見つけるのにかかる計算時間を計測します。
まずは、学習がてら単純探索より、二分探索が早いことを確認します。
次に、二分探索でリストと配列の場合での計算時間を計測します。
環境：MacBook Air
プロセッサ名:Intel Core i5
プロセッサ速度:1.6 GHz
メモリ:4 GB
単純探索
まずは、試しに以下のプログラムを実行し、単純探索でかかる計算時間を見てみます。
- simple_search.py
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分ほどかかりました。
$ 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
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分半ほどかかりました。
想定通りですが、二分探索の方が単純探索より早いです。
$ time python3 binary_search.py
77777777
real 1m34.540s
user 0m43.687s
sys 0m38.348s
- binary_search2.py
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回目はリストの方に軍配が上がりました。
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サービスはたくさんありますが、アルゴリズムについて教えてくれているサイトはあまりないような気がします。
プログラミング言語は、あくまでサービスを実現する手段なので、本質的なところを突き詰めるのもおもしろいです。次は、システムコールの呼びだしからメモリがどのように確保されるかなど、もっと掘り下げて検証したいと思います。