シーケンスからn番目に小さい/大きい値を効率よく取得するにはどうすればいいのかなー。という話。
C++だとstd::nth_element
って関数が標準であって、n番目の値とか比較的簡単に効率的な実装で求めることができます。
C#...というか多くの言語で標準ライブラリでn番目の要素を、みたいなのはなさそう。 なのでC#用のそれを作りました。1ファイルなので、適当にコピペしても使えます。
どの言語の標準ライブラリでも、ソートするアルゴリズムは実装されているはずなので、最悪、全部ソートすればいいのだけど。 まぁ、それは最悪なので避けたいでしょう、シーケンスの長さ小さければまぁそれでもいいかもしれませんが....。
じゃぁどうすればいいのかな、というとstd::nth_elementがどういう実装してるかのぞけばいいわけです。 で、そのstd::nth_elementはどういう実装かというと、どうやらQuickSelectというアルゴリズムを使っているっぽいです。
QuickSelectはQuickSortの一部を切り出した感じのアルゴリズム。 説明するまでもありませんが、QuickSortは適当にpivot選んで配列をpivotより小さい/大きい2つに分割して、分割したそれぞれにに対してまたpivot選んで、と再帰的動作させることで全体がソートされていきます。 が、別にn番目の値が何か、ということだけに興味がある場合は、全部ソートする必要はないわけです。 なので、pivot選んで分割された2つのうち、n番目を含んでいる片方しか注目しないでいいわけです。 注目した片方をまた2つに分割、n番目を含んでいる方にのみ着目して...と、これを繰り返せば、全部ソートすることなくn番目の値が見つかるわけです。 賢い。
なので実装としても再帰関数書かずに普通にwhileでくるくる回していればいいのでスタックも積まれないしマシンに優しい。
QuickSortの平均計算量がO(nlogn)、QuickSelectがO(n)という感じ。
紹介したスクリプトだと、以下みたいにかけるようになってます。返り値にはn番目に小さいその値と、対応するインデックスが詰め込まれてる感じ。 ちなみにNthSmallest()とかの処理はゼロアロケーション。
ReadOnlySapn<int> source = Hoge(); int n = Fuga(); var result = source.NthSmallest(n); // or NthLargest(n) Console.WriteLine(result.Item) Console.WriteLine(result.Index)
QuickSelect、n番目の値を取得するだけじゃなくて、もうちょっと便利に使えます。 先程紹介したレポジトリのREADMEにも書いてあるんですが、n番目からm番目の値をとってくるのにも使えます。
こんな感じで。
ReadOnlySpan<int> source = Enumerable.Range(0, 100).Shuffle().ToArray().AsSpan(); var pool = ArrayPool<int>.Shared.Rent(source.Length); var indices = pool.AsSpan(0, source.Length); QuickSelect.Iota(indices); //like std::iota //Get 50 <= item < 60 QuickSelect.Execute(source, indices, 50); QuickSelect.Execute(source, indices[50..], 10); for (int i = 0; i < 10; i++) { Console.Write($"{source[indices[50 + i]]}, "); } // output : 50, 56, 51, 57, 55, 54, 53, 52, 58, 59, ArrayPool<int>.Shared.Return(pool);
私の実装は、配列そのものReadOnlyで、対応するインデックス配列を弄っています。 そのインデックス配列は1度QuickSelectにかけられる事で、n(上の例でいうと50)で分割されています。 なので、50~60の値が知りたい場合、インデックス配列の50より後ろだけを見るようにスライスして、n=10(= 60 - 50)でQuickSelectを再度実行してあげれば、50~60番目までの要素が取得できるようになります。 便利。
そんなわけでQuickSelect使えばn番目の要素をO(n)で取得できる、ということでした。 n番目の値を知りたいだけの場合には全部ソートするよりだいぶいいので思うので、よかったら使ってみてください。