問題タブ [partial-sort]

多くの基準でソート可能なデータセットのページングアルゴリズムを実装しようとしています。残念ながら、これらの基準の一部はデータベースレベルで実装できますが、一部はアプリレベルで実行する必要があります（別のデータソースと統合する必要があります）。ページング（実際には無限スクロール）の要件があり、ページング呼び出しごとにアプリレベルでデータセット全体を並べ替える手間を最小限に抑える方法を探しています。

絶対にソートする必要があるリストの部分のみをソートして、部分的なソートを行うための最良の方法は何ですか？std::partial_sort.NETライブラリで利用可能なC++の関数に相当するものはありますか？この問題をどのように解決すればよいですか？

編集：これが私がしようとしていることの例です：

いくつかの並べ替え基準に従って、1000要素セットの要素21〜40を取得する必要があるとします。並べ替えを高速化するために、そしてとにかく毎回データセット全体を調べる必要があるため（これは、ステートレスであるHTTPを介したWebサービスです）、データセット全体を注文する必要はありません。正しく注文するには、要素21〜40だけが必要です。3つのパーティションを作成するだけで十分です。要素1〜20、ソートされていません（ただし、すべて要素21未満）。要素21〜40、ソート済み; および要素41〜1000、ソートされていません（ただし、すべて要素40より大きい）。

があることは知っていますがnumpy.percentile(myArray,5)、バックグラウンドでこれが最初に配列の完全な並べ替えを行うことを理解しています。これは、最小の 5% の値のみを並べ替える必要がある場合は非効率的です。また、ヒープソートアプローチがこの部分ソートの問題に適していることも読みましたが、2D numpy 配列で機能する実装が見つからないようです。

これが私が試したことです：

私のシステムでは約 15 ミリ秒かかります (私のリアルタイム アプリケーションには遅すぎます)。

heapq を試す:

私のシステムでは 300 ミリ秒かかります。heapq が物事をスピードアップできることを願っています!

C# プログラマーが LINQ を使用して 3 つの異なる配列から上位 5 つの数値を抽出する方法を示しているブログを読みました。

私は C++ で同じことをしようとしましたが、ベクトルと並べ替えを使用して次の 5 行のコードだけを書きました。出力は88 89 110 888 921期待どおりです。

しかし、質問は、より良い解決策がありますか?

タスクは、ベクトルがソートされた場合、中央値 (n 番目の要素) がその位置にある重複のあるベクトルを部分的にソートすることです。小さい要素はすべて左側に配置し、大きい要素はすべて右側に配置する必要があります。中央値と同じ値を持つすべての要素は元の順序である必要がありますが、残りの要素ではありません。

これをどのように解決しますか？

私の最初の解決策：

1. std::nth_element() を使用して中央値の要素を見つけます
2. ベクトルをトラバースし、インデックスに関して中央値と同じ値を持つ要素のみを並べ替えます。これを効率的に行うにはどうすればよいですか？

Vec生産量が非常に多いa から上位 N 個のアイテムを取得する必要があります。現在、私はこの非効率的な方法でそれを行っています:

C++ では を使用しますが、 Rust のドキュメントstd::partial_sortで同等のものを見つけることができません。

私はそれを見落としているだけですか、それとも（まだ）存在しませんか？