Pythonにおける2重ループとitertoolsの速度比較
バブルソート
今回はバブルソートを用いて比較を行った. まず,バブルソートのアルゴリズムを以下に示す.
- リストの先頭から順に n 番目と n+1 番目の要素を比較する.
- 要素の順序が逆であれば,入れ替える.
- この操作をデータ数 - 1 回繰り返す.
最悪計算時間は,O(n2) である.
Python での実装を以下に示す.
import random nums = [random.randint(0, 100000) for _ in xrange(1000)] for y in xrange(len(nums) - 1): for x in xrange(len(nums) - 1): if nums[x] > nums[x+1]: nums[x], nums[x+1] = nums[x+1], nums[x]
itertools
Python には itertools モジュールがあり,product メソッドを用いることで,ジェネレータ式の入れ子 for ループと等価になる. 先程の for ループを itertools で書き換えると以下のようになる.
import itertools import random nums = [random.randint(0, 100000) for _ in xrange(1000)] for y, x in itertools.product(xrange(len(nums) - 1), xrange(len(nums) - 1)): if nums[x] > nums[x+1]: nums[x], nums[x+1] = nums[x+1], nums[x]
速度比較
両者の計算時間の比較を行った.実験条件を下記に示す.
- 1000個のランダムな整数をソートする
- 100試行を行う
平均値および1標準偏差を以下に示す.
for : 0.2769294 ± 0.02847064 [s] itertools : 0.3409318 ± 0.03678625 [s]
Kolmogorov-Smirnov test を適応した結果,正規性が確認できなったため,Wilcoxon test を用いて平均値の差の検定を行った結果.有意水準1%において有意であった.
結論
for のが早いっぽい.