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はかえって非効率なのでしょう。