list.sort : sorted random.shuffle : shuffled?
配列のシャッフル
を見て、
リストを変更するlist.sortに対し、新たなリストを返すsortedがあるように
リストをシャッフルするrandom.shuffleに対応する、「shuffled」関数を作ってみました。
from __future__ import print_function import random from timeit import Timer def shuffled0(iterable, random=random.random): return sorted(iterable, key=lambda x:random()) def shuffled1(x): return random.sample(x, len(x)) def shuffled2(x): x = list(x) random.shuffle(x) return x def main(): ls = list(xrange(100)) for f in [shuffled0, shuffled1, shuffled2]: t = Timer(lambda: f(ls)) print(f.__name__, t.timeit(100000)) if __name__ == "__main__": main()
shuffled0 | 9.2551360578 |
shuffled1 | 10.538108335 |
shuffled2 | 8.95892438843 |
random.sample(population, k)を利用したshuffled1が遅いのは、
sampleは、本来リストの一部分を取ってくる関数なので、
len(population) と k の比較などの無駄のせいでしょう。
また、shuffled0よりshuffled2が高速でした。
shuffled0で使用したsortedはC言語レベルで定義された関数で、
やっている事は
def sorted(x, *a, **kw): y = list(x) y.sort(*a, **kw) return y
と、同じです。
listでコピーしているのはshuffled0もshuffled2も同じな上
random.shuffleはPure Python で書かれているのに
数%とはいえshuffled2の方が高速。
なぜか?
多分、比較回数の差だと思います。
Pythonクックブックに「Pythonでは、『比較』より『リファレンスの変更』の方が安価」
という意味の記述がありました。
比較は__lt__メソッドの参照などのインタープリタの高度な機能が必要な反面、
リファレンスの変更は単にポインタの代入をするだけです。
random.random()はfloatを返すので、
return sorted(iterable, key=lambda x:random())では、何度もfloatの比較が必要になります。
一方、random.shuffleでは、floatの比較は全くありません。
#random.Randomクラスのメソッドとして、定義されている def shuffle(self, x, random=None, int=int): """x, random=random.random -> shuffle list x in place; return None. Optional arg random is a 0-argument function returning a random float in [0.0, 1.0); by default, the standard random.random. """ if random is None: random = self.random for i in reversed(xrange(1, len(x))): # pick an element in x[:i+1] with which to exchange x[i] j = int(random() * (i+1)) x[i], x[j] = x[j], x[i]
ところで、なぜPython標準ライブラリに、
リストを返すrandom.shuffledが定義されていないのでしょう?
これも想像ですが、ユーザーを効率的な操作に誘導するためだと思います。
リストをランダムにソートする場合、
元のリストはもはや破壊しても問題ない(random.shuffle)場合か、
数個の要素しか必要ない(random.sample)場合
がほとんどであり、その場合shuffledはかえって非効率なのでしょう。