余白

https://blog.lacolaco.net/ に移転しました

IEnumerable<T>#Random()の実装について

C#LINQネタです。

LINQIE<T>を扱っていると、「ランダムに要素を1つ取り出したい」と思うことが時々あります。なのでそういう時は拡張メソッドで

IEnumerable<T>#Random()

を実装すると便利ですね。
ところでこのメソッドの中身、どう実装するのがパフォーマンスがいいのかを実験してみたので書いてみます。
とりあえず思いついたのは3種類だったのでそれぞれ実装しました

  • RandomOrderBy

SQLなんかでよくやる、OrderByでランダムにソートして先頭を取り出すというやりかた。
全要素に対して1回のソートが必要なので計算量はO(n)ですかね

  • RandomElementAt

これは直感的に、ランダムな位置の要素を直接取り出すというやり方。
計算はRandom#Nextの一回とElementAtの2回だけですが、ElementAtの実装によってはインデックスの値によって計算量が変わるかも…?

  • RandomSkip

これはちょっと工夫して、ランダムな数だけ要素をスキップして得られた列挙の先頭をとるやり方です。効率はそんなによくなさそうですが操作が単純なので内部の実装しだいでは勝てるかもと思って実装しました

それぞれを要素数100000の整数の列挙に対して1000回行った実行時間でパフォーマンスを比較しますが、IE<T>の内部実装によって挙動が変わるかもしれないので、サンプルの方も、
IE<T>型、配列型、List<T>型の3種類を用意しました。最終的なコードがこちら

そして実行結果がこちら

  • RandomOrderBy

遅い。とにかく遅い。内部実装によらず遅い。論外。

  • RandomElementAt

クッソ早い。IE<T>型はおそらく内部でインデックス化されていないために若干の時間ロスがあるが、配列、List<T>型ではあまりにも早い。多分これが最強。

  • RandomSkip

これも結構早い。ElementAtには勝てない。

結論: ElementAtを使うべき。

だいたい予想通りの結果になりましたがOrderByのあまりの遅さとElementAtのあまりの早さに笑いました。
ElementAtは早かったですが、さらにこれは多分要素数に非依存なので、他の2つとくらべて100000件よりもずっと大きな列挙に対しても同じようなパフォーマンスが得られると思います。

以上LINQ小ネタでした。多分Qiitaにも要約して書きます