巨人の肩の上に登る

先人の積み重ねた発見に基づいて、なにかを発見しようとすることを指す。

Pythonにおける2重ループとitertoolsの速度比較

バブルソート

今回はバブルソートを用いて比較を行った. まず,バブルソートのアルゴリズムを以下に示す.

  1. リストの先頭から順に n 番目と n+1 番目の要素を比較する.
  2. 要素の順序が逆であれば,入れ替える.
  3. この操作をデータ数 - 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]


速度比較

両者の計算時間の比較を行った.実験条件を下記に示す.

  1. 1000個のランダムな整数をソートする
  2. 100試行を行う

平均値および1標準偏差を以下に示す.

for       : 0.2769294 ± 0.02847064 [s]
itertools : 0.3409318 ± 0.03678625 [s]

Kolmogorov-Smirnov test を適応した結果,正規性が確認できなったため,Wilcoxon test を用いて平均値の差の検定を行った結果.有意水準1%において有意であった.


結論

for のが早いっぽい.