9

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

double percentile(std::vector<double> &vectorIn, double percent)
{
    std::nth_element(vectorIn.begin(), vectorIn.begin() + (percent*vectorIn.size())/100, vectorIn.end());

    return vectorIn[(percent*vectorIn.size())/100];
}  

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

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

編集:

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

longes でソートされたブロックの長さのヒストグラム

4

1 に答える 1

6

これは、標準ライブラリの実装ごとに異なります (他の要因によって異なる場合があります) が、一般的には次のようになります。

  • std::nth_element は、nth_element が位置 n にあり、コンテナーが位置 n で分割されている場合、適切と思われるように入力コンテナーを再配置できます。

  • 小さなコンテナの場合、スケーラブルではありませんが、通常はクイック選択よりも完全な挿入ソートを実行する方が高速です。

標準ライブラリの作成者は通常、最速のソリューションを選択するため、ほとんどの nth_element の実装 (さらに言えば、並べ替えの実装) は、小さな入力 (または再帰の下部にある小さなセグメント) に対してカスタマイズされたアルゴリズムを使用します。必要以上に積極的に。スカラー値のベクトルの場合、キャッシュを最大限に活用するため、挿入ソートは非常に高速です。ストリーミング拡張機能を使用すると、並列比較を行うことでさらに高速化できます。

ところで、しきい値反復子を 1 回だけ計算することで、計算量を少し節約できます。

double percentile(std::vector<double> &vectorIn, double percent)
{
    auto nth = vectorIn.begin() + (percent*vectorIn.size())/100;
    std::nth_element(vectorIn.begin(), nth, vectorIn.end());
    return *nth;
}
于 2015-02-16T19:27:49.797 に答える