Python
高速化
乱数
ゲーム理論
マルチエージェントシステム

リストからランダムに要素を取得する処理を鬼速くしてみた

こんにちは。Keiです。

今までQiitaはもっぱら見る専でしたが、いよいよ書く側に回ろうと思います。

記念すべき最初の投稿は、Pythonで非常に要素数の多いリストからランダムに複数の要素を取得する処理を高速化する方法についてです。

というのも自分は普段進化ゲーム理論のモデルを利用した数値シミュレーションに取り組んでおり、よくやる処理の1つに


  1. エージェント(要は人間に相当するオブジェクト)を大量に用意し、リストに格納

  2. リストからエージェントをランダムに2人選んできてゲームをさせる

  3. 対戦したエージェントは母集団から取り除く

  4. 全員がゲームするまで2~3を繰り返す

というものがあるのですが、これを普通にやろうとすると猛烈に遅い

自分が最初に試作したコードでは2~4のループ部分だけでプログラム全体の実行時間の実に95%以上を占めていました!

というわけでこの処理を高速化するために色々実験してみました。実は以下の説明には載せていない試み(Cython,Numbaの利用など)も沢山やってみたのですが、どれも謎のエラーを吐き出し続けるだけで一向に埒が明かなかったので、素直に関数やアルゴリズムの工夫だけでなんとかする道を探ることにしました。


まずは普通に実装

最初は特に工夫せず、上の1~4の処理を素直に実装して実行時間を計測してみました。

プログラムはjupyter notebook上で実行し、timeitマジックコマンドで実行時間を計測しました。


In [1]: from numpy import random as rnd
import random

In [2]: %%timeit
list = [i for i in range(10000)] # 今回はエージェントの代わりに整数を格納
while list != []:
a1 = None # a1とa2がゲームで対戦する
a2 = None
a1, a2 = rnd.choice(list, 2, replace=False) # 重複を許さずにゲームのプレイヤーを2人選ぶ
list.remove(a1) # ゲームをプレイした人はリストから取り除く
list.remove(a2)
3.27 s ± 23.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

大学にあるそこそこ性能の良いデスクトップマシンを使って約3秒。これを実際の進化ゲームのシミュレーションでは計算結果が収束するまで数万回、数十万回と繰り返すとなると日が暮れるどころの騒ぎじゃないです。

そこでline_profilerを使って行ごとの処理時間を見てましたが、原因は主にrnd.choiceの部分でした。乱数を使う処理は結構遅いみたいです。

またnp.random.choiceではなく標準ライブラリのrandomモジュールに入っているrandom.sampleも同様の処理が可能とのことだったので試してみました。結果は以下の通り。

In [3]: %%timeit

list = [i for i in range(10000)]
while list != []:
a1 = None
a2 = None
a1, a2 = random.sample(list,2) # sampleメソッドも重複無しで複数の要素を取得できます
list.remove(a1) # ゲームをプレイした人はリストから取り除く
list.remove(a2)
227 ms ± 9.56 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

お、かなり速くなった!高速化ならとにかくnumpyってイメージがあった(のは自分だけ?)ので意外でしたが、どうも乱数に関してはnumpyを使うより通常のrandomモジュールを使う方が速いみたいです。

でもこれで満足してしまってはいけません。数値シミュレーション屋は速さを永遠に追い求める種族なのです(なら初めからC++使えよとか言われるとつらい)

ということで少し発想を変えてみました。ランダムに要素を選ぶのではなく、リストの中身の順番をシャッフルし、それからリストの先頭あるいは末尾の要素を選んでくれば、それもランダムに要素を選んだと言えますよね。

というわけで実験。


「要素の並び順をシャッフル ⇒ リストの先頭/末尾の要素を取得」に変更

リストの並び順をシャッフルするにはnp.random.shuffleメソッドが使えます。

その後リストの先頭と2番目の要素を取得するようにしたのが以下です。

In [4]:%%timeit

list = [i for i in range(10000)]
rnd.shuffle(list) # リストの並び順をシャッフル

while list != []:
a1 = None
a2 = None
a1 = list[0] # 先頭の要素を取得
a2 = list[1] # 2番目の要素を取得
list.remove(a1)
list.remove(a2)
7.6 ms ± 75.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

おぉ!さっきと比べて30倍近く速くなりました!

ついでにa1=list[0]からlist.remove(a2)までの部分が野暮ったいのでpopメソッドでスッキリさせたのが次のものです。

なおpopを使う時は必ず引数無しでリストの末尾の要素を取得するようにしないと信じられないくらい遅くなるので注意してください。下記参照:[https://x1.inkenkun.com/archives/861]

%%timeit

list = [i for i in range(10000)]
rnd.shuffle(list) # リストの並び順をシャッフル

while list != []:
a1 = None
a2 = None
a1 = list.pop() # リストの末尾の要素を取得
a2 = list.pop()
1.09 ms ± 2.51 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

は、速いっ! ! ! www

最初のコードと比べると実に3000倍もの高速化に成功しました! !


結論

numpy.random.choiceは使ってはいけない。shuffleしてからpopで取り出すべし。

ただ、shuffleを1回使うのもchoiceを5000回繰り返すのも結局同じ回数乱数を取り出しているはずなので、両者にここまで速度差が出る理由はよくわかりません。randomモジュール内部の実装にお詳しい方いたらコメントよろしくお願いしますm(_ _)m