O(n) vs O(nlogn)

Pythonは、インタプリタ型の言語なので、インタプリタのオーバーヘッドに気をつけなければならない。以下のようなパフォーマンスのテストを行ってみた。

import time

def min1(lst):
    min_v = lst[0]
    for v in lst:
        if min_v > v:
            min_v = v
    return min_v

def min2(lst):
    lst_sorted = sorted(lst)
    return lst_sorted[0]

a = range(10000)
a.reverse()

t1 = time.time()
for i in range(10000):
    v1 = min1(a)
t2 = time.time()
print v1
print 'time of min1() =', t2 - t1  #=> time of min1() = 6.641

t1 = time.time()
for i in range(10000):
    v2 = min2(a)
t2 = time.time()
print v2
print 'time of min2() =', t2 - t1  #=> time of min2() = 4.233

つまり、Pythonでは、インタプリタのオーバーヘッドにより、O(n)より、O(nlogn)の計算量の方が、このケースにおいては早い。
sorted()では、関数の中でループを行っており、オーバーヘッドは少ない。しかし、forを使用した例では、ループごとに毎回オーバーヘッドが加算される。
つまり、Pythonでは、大量のデータに対するforループは遅い。なるべく、リスト内包表記を使用すべきであるが、関数呼び出しを伴ってしまう場合は、どちらが早いかはケースバイケースであると思われる。

ここら辺の処理を早くする工夫(ライブラリ)もあるので、今後の研究課題にするつもりである。