こんにちは。Keiです。
今までQiitaはもっぱら見る専でしたが、いよいよ書く側に回ろうと思います。
記念すべき最初の投稿は、Pythonで非常に要素数の多いリストからランダムに複数の要素を取得する処理を高速化する方法についてです。
というのも自分は普段進化ゲーム理論を利用した数値シミュレーションに取り組んでおり、よくやる処理の1つに
- エージェント(要は人間に相当するオブジェクト)を大量に用意し、リストに格納
- リストからエージェントをランダムに2人選んできてゲームをさせる
- 対戦したエージェントは母集団から取り除く
- 全員がゲームするまで2~3を繰り返す
というものがあるのですが、これを普通にやろうとすると猛烈に遅い。
自分が最初に試作したコードでは2~4のループ部分だけでプログラム全体の実行時間の実に95%以上を占めていました！
というわけでこの処理を高速化するために色々実験してみました。実は以下の説明には載せていない試み(Cython,Numbaの利用など)も沢山やってみたのですが、どれも謎のエラーを吐き出し続けるだけで一向に埒が明かなかったので、素直に関数やアルゴリズムの工夫だけでなんとかする道を探ることにしました。
実行環境
lenovo ideapad 330S
Intel® Core™ i5-8250U CPU 1.60GHz × 8
Python 3.7.3
まずは普通に実装
最初は特に工夫せず、上の1〜4の処理を素直に実装して実行時間を計測してみました。
プログラムはjupyter notebook上で実行し、timeitマジックコマンドで実行時間を計測しました。
from numpy import random as rnd
import random
%%timeit
agents = [i for i in range(10000)] # 今回はエージェントの代わりに整数を格納
while agents != []:
agent1, agent2 = rnd.choice(agents, 2, replace=False) # 重複を許さずにゲームのプレイヤーを2人選ぶ
'''
本来はここでゲームをする処理が入る
'''
agents.remove(agent1) # ゲームをプレイした人は母集団から取り除く
agents.remove(agent2)
12.3 s ± 274 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
12秒!!。これを実際の進化ゲームのシミュレーションでは計算結果が収束するまで数万回、数十万回と繰り返すとなると日が暮れるどころの騒ぎじゃないです。
そこでline_profilerを使って行ごとの処理時間を見てましたが、原因は主にrnd.choiceの部分でした。乱数を使う処理は結構遅いみたいです。
またnp.random.choiceではなく標準ライブラリのrandomモジュールに入っているrandom.sampleも同様の処理が可能とのことだったので試してみました。結果は以下の通り。
%%timeit
agents = [i for i in range(10000)]
while agents != []:
agent1, agent2 = random.sample(agents, 2) # 違いはここだけ
agents.remove(agent1)
agents.remove(agent2)
309 ms ± 2.58 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
お、かなり速くなった!高速化ならとにかくnumpyってイメージがあった(のは自分だけ?)ので意外でしたが、どうも乱数に関してはnumpyを使うより通常のrandomモジュールを使う方が速いみたいです。
でもこれで満足してしまってはいけません。数値シミュレーション屋は速さを永遠に追い求める種族なのです(なら初めからC++使えよとか言われるとつらい)
ということで少し発想を変えてみました。ランダムに要素を選ぶのではなく、リストの要素の格納順をシャッフルし、それからリストの先頭あるいは末尾の要素を選んでくれば、それもランダムに要素を選んだと言えますよね。
というわけで実験。
#「要素の並び順をシャッフル ⇒ リストの先頭/末尾の要素を取得」に変更
リストの並び順をシャッフルするにはnp.random.shuffleメソッドが使えます。
その後リストの先頭と2番目の要素を取得するようにしたのが以下です。
%%timeit
agents = [i for i in range(10000)]
rnd.shuffle(agents) # 並び順をシャッフル
while agents != []:
agent1, agent2 = agents[0], agents[1]
agents.remove(agent1)
agents.remove(agent2)
8.4 ms ± 41.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
おぉ！さっきと比べて30倍以上速くなりました！
ついでにエージェントを取得して母集団から取り除く処理をpopメソッドでスッキリさせたのが次のものです。
なおpopを使う時は必ず引数無しでリストの末尾の要素を取得するようにしないと信じられないくらい遅くなるので注意してください。下記参照:[https://x1.inkenkun.com/archives/861]
%%timeit
agents = [i for i in range(10000)]
rnd.shuffle(agents)
while agents != []:
agent1 = agents.pop() # リストの末尾の要素を取得してかつ母集団から削除
agent2 = agents.pop()
1.09 ms ± 2.51 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
は、速いっ! ! ! www
最初のコードと比べると実に7000倍近い高速化に成功しました! !
結論
numpy.random.choiceは使ってはいけない。shuffleしてからpopで取り出すべし。
ただ、shuffleを1回使うのもchoiceを5000回繰り返すのも結局同じ回数乱数を取り出しているはずなので、両者にここまで速度差が出る理由はよくわかりません。randomモジュール内部の実装にお詳しい方いたらコメントよろしくお願いしますm(_ _)m