問題タブ [nth-element]

std::nth_element次のように、ベクトルのパーセンタイルの (ほぼ正しい) 値を取得するために使用しています。

最大 32 要素の長さの vectorIn の場合、ベクトルが完全にソートされることに気付きました。33 要素から始まると、(予想どおり) ソートされません。

これが問題かどうかはわかりませんが、関数は「(Matlab-)mex c++ コード」にあり、「Microsoft Windows SDK 7.1 (C++)」を使用して Matlab 経由でコンパイルされます。

編集：

関数に渡された 1e5 ベクトル内の最長のソート済みブロックの長さの次のヒストグラムも参照してください (ベクトルには 1e4 のランダム要素が含まれ、ランダムなパーセンタイルが計算されました)。非常に小さい値でのピークに注意してください。

nth_elementStackOverflow およびその他の場所には、 O(n)であり、通常は Introselect で実装されているという多くの主張があります: http://en.cppreference.com/w/cpp/algorithm/nth_element

これをどのように達成できるか知りたいです。ウィキペディアの Introselect の説明を見たところ、さらに混乱しました。アルゴリズムは QSort と Median-of-Medians をどのように切り替えることができますか?

ここで Introsort の論文を見つけました: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5196&rep=rep1&type=pdfしかし、それは言う:

この論文では、ソートの問題に集中し、後のセクションで簡単に選択の問題に戻ります。

nth_elementがどのように実装されているかを理解するために STL 自体を読み込もうとしましたが、すぐに理解できなくなります。

Introselect の実装方法の疑似コードを教えてもらえますか? もちろん、STL 以外の実際の C++ コードでも構いません :)

これは常に次の結果になりますか？

または、他の可能な結果は次のようになります。

私のマシンで何度も試してみたところ、n番目の値が常に連続していました。しかし、それは証拠ではありません;)。

目的:

一意の Kdtree を構築したいのですが、ベクターに重複があります。現在、中央値を見つけるために nth_element を使用しています。問題は、ベクトルを再度トラバースすることなく、一意の再構成可能な中央値を選択することです。中央値が連続している場合は、あまりトラバースせずに一意の中央値を選択できます。

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

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

私の最初の解決策：

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

指定された並べ替えられていないベクトルから、n 番目に小さい要素を取得したいと考えています。標準ライブラリにメソッドがあることがわかりました。しかし、次の結果がわかりません。

エントリ {3,4,5,2,3} を持つベクトルを取得し、2 番目に小さい要素が必要です。次のコードを実行すると、2 番目の位置に数字 2 が表示されます。実際には 3 になるはずです。2 は 2 番目ではなく 1 番目に小さい要素だからです。

私の間違いは何ですか？

nth_elementクラス内で独自の並べ替え関数 (オブジェクトのデータにアクセスする必要があります) で関数を使用したいと考えています。現在、私は次のことを行っています。

もちろん、これは機能せず、「非静的メンバー関数への参照を呼び出す必要があります」というエラーが発生しました。その後、Reference to non-static member function must be called、How to initialize std::functionwith a member-function? を見ました。ここでいくつかの他の質問。これが機能しなかった理由は理解していますが、これを解決する方法がわかりません。

誰かが私を助けて、この問題を解決する方法を教えてもらえますか?

Vantage Point Tree を Python で実装したいのですが、C++ で std::nth_element を使用しています。

したがって、Pythonまたはnumpyで同等の「nth_element」関数を見つけたいと思います。

nth_element は配列を半順序付けするだけで、O(N) であることに注意してください。

そして今、ベクトルは次のようになります。

そして、n番目の要素を取得したいだけでなく、リストの2つの部分[3,0,2,1,4]と[6,7,9,8]を再配置したいと考えています。

さらに、nth_element サポートは、2 つの要素を比較できる関数を受け入れます。たとえば、以下のように、ベクトルはベクトル op DataPoint であり、DistanceComparator 関数は 2 つのポイントの距離を the_v.begin() と比較します。

編集：

私はbhuvan-venkateshの回答を使用し、テストするコードをいくつか書きました。

そして結果：

そして、C++ コードを使用してさらにテストを行います。

しかし、問題があります。numpy を使用すると、常に新しい配列が返され、配列が巨大な場合に多くのメモリが浪費されます。どうすればそれを処理できますか。または、Python 用の C++ エクステンドを作成する必要があります。

EDIT2：

@bhuvan-venkateshパーティション機能をお勧めいただきありがとうございます。

以下のようなパーティションを使用します。

プロファイラーを次のように実行しました。

結果は次のとおりです。

そして、次のように配列全体をコピーすることはありません: numpy.partition(a, 3)

結論: numpy.ndarray.partition は、私が見つけたいものです。