乱数生成が遅いのはモジュールだから仕方ないっぽい

京都の嵐山でお花見してきたbonlifeです。ベラシとその仲間たちよ、ありがとう！
さてさて、話は急に変わりまして。モンティホール問題(ジレンマ)について扱ったこの日記を見ていたら、Ruby、PHPに比べてPythonが異常に遅いと指摘されていたので、ちょっと調べてみました。RubyやPHPでは乱数を生成するrand()が組み込みなのに対して、Pythonでは標準モジュールでの提供なので、まぁ仕方ないんだろうな、と思いつつ調査。

>>> import random
>>> import profile
>>> def random_generate(num):
	for i in range(num):
		random.randint(1,3)

		
>>> 
>>> 
>>> profile.run('random_generate(100000)')
         300005 function calls in 3.396 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    0.442    0.000    0.442    0.000 :0(random)
        1    0.006    0.006    0.006    0.006 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        1    0.445    0.445    3.396    3.396 <pyshell#11>:1(random_generate)
        1    0.000    0.000    3.396    3.396 <string>:1(<module>)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    3.396    3.396 profile:0(random_generate(100000))
   100000    1.500    0.000    1.941    0.000 random.py:147(randrange)
   100000    1.004    0.000    2.945    0.000 random.py:211(randint)

なんだか、randintしか呼び出してないつもりだったのにrandrangeが使われてるじゃないの。しかも、結構時間がかかってる様子。仕方がないので、random.pyの中身を確認してみると、以下のようになってました。

    def randint(self, a, b):
        """Return random integer in range [a, b], including both end points.
        """

        return self.randrange(a, b+1)

なんだなんだ。randrangeに引数をほぼそのまま渡してるだけじゃないですか。ということで、今度はrandrangeの内容をチェック。沢山あるオプションに対応するようにPythonコード内で色々と処理を分けていました。もうちょっと速そうなのないかしら、と探しているとchoiceを発見。

    def choice(self, seq):
        """Choose a random element from a non-empty sequence."""
        return seq[int(self.random() * len(seq))]  # raises IndexError if seq is empty

これは極めてシンプル。単純なシーケンスを渡すだけなら、これが速いだろうと推測。

>>> def random_generate(num):
	list = [1,2,3]
	for i in range(num):
		random.choice(list)

		
>>> profile.run('random_generate(100000)')
         300005 function calls in 2.060 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    0.259    0.000    0.259    0.000 :0(len)
   100000    0.264    0.000    0.264    0.000 :0(random)
        1    0.002    0.002    0.002    0.002 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        1    0.425    0.425    2.059    2.059 <pyshell#17>:1(random_generate)
        1    0.000    0.000    2.059    2.059 <string>:1(<module>)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    2.060    2.060 profile:0(random_generate(100000))
   100000    1.108    0.000    1.632    0.000 random.py:246(choice)

おぉ、速くなりましたよ！とは言うものの、やっぱり遅いですね。random自体にはあまり時間がかかってませんが、choiceになるとちょっとアララな感じです。ほんのちょっとしたコードでも結構時間かかっちゃうんですね…。(choiceのどこで時間がかかるのかイメージが湧きませんが。)そんなこんなで、速度改善のために勝手に添削です。(オリジナルの70%ぐらいの時間で処理できるはず。でも、遅っ。)

rand.py

#!/usr/bin/python

import random

def Bingo(times):
    hit = 0
    i = 0
    list = [1, 2, 3]
    while i < times:
        bingo = random.choice(list)
        player = random.choice(list)
        host = player
        while host == player:
            host = random.choice(list)

        if host != bingo:
            i = i + 1
            if player == bingo:
                hit = hit + 1
    return hit

attempt = 100000
for j in range(10):
    print "Hit "+ str(Bingo(attempt)) + " times in " + str(attempt) + " attempts."

まず、シーケンスを事前に用意した上で、randintを全部choiceに変更。後、最後の行にあった j = j + 1 は不要だったので削除。
スピードよりもコードのシンプルさを望むのであれば、randomモジュールのsample()を使うと良いかもしれないですね。下記の4行を1行で表現できます。(sample()は沢山あるリストの中から重複しない複数の要素をランダムに取得したい時に、かなり便利に使えそうです。)

        player = random.choice(list)
        host = player
        while host == player:
            host = random.choice(list)

        player, host = random.sample(list,2)

そんなこんなしてる中で、標準モジュールもPythonのコードなので、頑張ればある程度は読めることに気付きましたよ。後、profileの基本的な使い方を学びました。イェイ。
ところで、random.pyの中で"import _random"ってしてる部分がありますが、これってどこからimportしてるのでしょう…。誰かご存知でしたら教えてくださいませ。