問題タブ [nth-element]

最近、STLにnth_elementというメソッドが存在することを知りました。説明を引用するには：

Nth_elementは、要素の範囲を部分的に順序付けるという点で、partial_sortに似ています。イテレータnthが指す要素が、全体がその位置にある要素と同じになるように、範囲[first、last）を配置します。範囲[最初、最後）がソートされました。さらに、範囲[nth、last）の要素は、範囲[first、nth）の要素のいずれよりも小さくなりません。

それは平均してO（n）の複雑さを持っていると主張しています。アルゴリズムはどのように機能しますか？説明が見つかりませんでした。

いくつかのC++コードをC＃に移植しています。

C＃には同等のものがstd::nth_element()ありますか、それとも自分でロールする必要がありますか？

Octave .oct 関数をコンパイルして、[5,8,4,6,7] のような奇数の長さのベクトルなど、長さが異なる並べ替えられたベクトルの上半分と下半分の中央値を計算しようとしています。 4,5 と 6 の「低い」中央値と 6,7 と 8 の「高い」中央値 (6 は両方の計算の一部です) が必要で、[5,8,4 などの偶数の長さのベクトルが必要です。 ,6,7,9] 4,5 と 6 の「低い」中央値と 7,8 と 9 の「高い」中央値が必要です。また、これを行うために高速な方法を使用しようとしています。私が適応させたこのコードを使用して、単純な中央値計算に使用します:-

入力ベクトルを理論上の半分に「分割」できます

私が抱えている問題は、上記の*コメントされた中央値計算を入力ベクトルの指定された関連部分だけに適用する構文がわからないことです。おそらく、入力は Octave ColumnVector 入力 = args(0).column_vector_value() であり、10 から 50 の値の長さになることに言及する必要があります。

のさまざまな実装の予想実行時間と最悪の場合の実行時間の両方を知っている人はいstd::nth_elementますか？私はこのアルゴリズムをほぼ毎日使用しています。

最近のMicrosoftコンパイラに同梱されているSTLバージョンに特に興味がありますが、このトピックに関する情報は役に立ちます。

これはこの質問の複製ではないことに注意してください。どのアルゴリズムが存在するかは理解していますが、どの実装がどのアルゴリズムを使用しているかに興味があります。

背景として、これを行うためのよく知られたアルゴリズムがあります。1つはO（n）平均ケースとO（n log n）ワーストケースで、もう1つはO（n）ワーストケースですが、実際には遅いです（中央値の中央値）。また、実際には高速な最悪の場合のO（n）実行時間を取得するための興味深い実装戦略の話があることにも注意してください。標準では、これはO（n）平均時間よりも悪いはずであるとされています。

ユーザーがベクトルに任意の数の値を入力でき、四分位数を返すことになっているプログラムを作成しましたが、「ベクトル添え字が範囲外です」というエラーが発生し続けます。

nth_element を使用して (x,y) ポイントのベクトルの中央値を見つけようとしています

tempOffsetsX は正常に動作していますが、tempOffsetsY が nth_element の後に非常に奇妙な結果をもたらすことがあります。マークされたデバッグ行での出力例を次に示します。

結果は、再コンパイルするまでかなり再現可能です。その時点で、詳細が変更され、一般的な問題が残ります。明らかにベクトルが何らかの形で破損していますが、その方法がわかりません。

また、nth_element の代わりに sort を使用すると、問題なく動作します。デバッグのために、ソートしてから nth_element を試してみましたが、うまくいきました。そのため、どういうわけか nth_element 内で発生する並べ替えがめちゃくちゃになっていますが、その方法がわかりません。

これがどのように起こっているかについてのアイデアはありますか？

編集- 私の環境に関する詳細情報。Arch Linux を実行しています。システムアップデートをしたばかりです。この同じコードは、更新前に問題なく動作していたことに注意してください。更新後に実行したのはこれが初めてです。しかし、それは数日のギャップであり、通常は私自身の問題についてシステム ライブラリを指摘することをためらっています。

長さ n の配列 A があります。B を、A のすべての k 番目の要素を含む配列 (個別に格納したくない - これは単に説明するためのものです) とします。B の中央値を見つけたいので、A のその要素をA の floor(n/2) 番目の位置。

これを効率的に行うにはどうすればよいですか？std::nth_element を 1 回呼び出して、A へのポインターを渡すことを考えています。ただし、このポインターを A の k 要素ずつインクリメントする必要があります。これを行うにはどうすればよいですか? 基本的に：

ここで、kFloat はフロートのように機能する構造ですが、ポインターをインクリメントすると、メモリ内で k*sizeof(float) が移動します。

注: 真の中央値 (n が偶数の場合の中央の 2 つの平均) は必要ありません。

編集:私が望むことを言う別の方法(kは定数ではないため、コンパイルされません):

編集 2:私は algorithm.cc を変更しているので、Boost のようなライブラリへの依存関係を導入したくありません。C++11 のコア機能 + std のみを使用したいと考えています。

私はこのプログラムの完成にとても近づいています。5 つの値の配列の中央値を見つけます。最後にもう 1 つ、なかなか消えないエラーがあります。私は C++ を初めて使用するので、何が問題なのかわかりません。こことGoogleで何度もエラーを調査しました。運がない。

コードは次のとおりです。

エラーの状態:「IntelliSense: オーバーロードされた関数 "std::nth_element" のインスタンスが引数リストと一致しません。引数の型は次のとおりです: (std::_Array_iterator、std::_Array_iterator、unsigned int、std::_Array_iterator)

この事を終わらせるのを手伝って！前もって感謝します。