Pythonでsetからランダムサンプリングすると遅い

この記事は何?

Pythonでsetからランダムサンプリングするコードを書いたところ,非常に時間がかかっていたので簡単に計測した時のメモです. 実行環境はPython 3.5.1 (Anaconda 2.5.0)です.

実験条件

サンプリング元はlistおよびsetとし,サイズを10, 100, 1000, 10000, 100000と変えていったときのサンプリングに必要な時間を見ていきます. サンプリングは1000回行うとし,3回実行した時の中央値で評価します.

コード

コード全体はここにアップロードしてあります. サンプリングの計測関数は以下のようなものです.

def sample_test(items, loop):
    start = time.time()
    for _ in range(loop):
        random.sample(items, 1)
    end = time.time()
    return end - start

実行結果

listからサンプリング

f:id:sz_dr:20160723012051p:plain

setからサンプリング

f:id:sz_dr:20160723012108p:plain

listからサンプリングする場合はサンプリング元のサイズに依らずおよそ一定時間ですが,setからサンプリングする場合はサンプリング元のサイズに比例して時間がかかることがわかります(x軸はlogスケールです).

setからサンプリングしたい時は,一度listに変換してからサンプリングするのが良さそうです.