27

私はstd::nth_elementアルゴリズムを見てきました。

結果のn番目の位置にある要素が、ソートされたシーケンスでその位置にある要素になるように、範囲[first、last）の要素を再配置します。その前の要素はどれも大きくなく、それに続く要素はそれよりも小さい。その前の要素も後の要素も順序付けが保証されていません。

ただし、私のコンパイラでは、次のコマンドを実行します。

    vector<int> myvector;
    srand(GetTickCount());

    // set some values:
    for ( int i = 0; i < 10; i++ )
        myvector.push_back(rand());

    // nth_element around the 4th element
    nth_element (myvector.begin(), myvector.begin()+4, myvector.end());

    // print results
    for (auto it=myvector.begin(); it!=myvector.end(); ++it)
        cout << " " << *it;

    cout << endl;

std :: sortとまったく同じ方法で、完全にソートされた整数のリストを常に返します。私は何かが足りないのですか？このアルゴリズムは何に役立ちますか？

編集：わかりました、はるかに大きなセットを使用した次の例は、かなりの違いがあることを示しています：

    vector<int> myvector;
    srand(GetTickCount());

    // set some values:
    for ( int i = 0; i < RAND_MAX; i++ )
        myvector.push_back(rand());

    // nth_element around the 4th element
    nth_element (myvector.begin(), myvector.begin()+rand(), myvector.end());

    vector<int> copy = myvector;
    std::sort(myvector.begin(), myvector.end());

    cout << (myvector == copy ? "true" : "false") << endl;
4

4 に答える 4

53

文書化されたセマンティクスを満たすために範囲全体を並べ替えることは完全に有効ですがstd::nth_element、そうすると、必要な複雑さ（線形）を満たすことができなくなります。重要な点は、そうする可能性があるということですが、そうする必要はありません。

これは、それstd::nth_elementが早期に救済できることを意味します-n'thあなたの範囲の要素が何になるかを知ることができるとすぐに、それは停止することができます。たとえば、範囲の場合

[9,3,6,2,1,7,8,5,4,0]

4番目の要素を与えるように依頼すると、次のような結果が得られる可能性があります

[2,0,1,3,8,5,6,9,7,4]

リストは部分的にソートされており、順番に4番目の要素がであることがわかるのに十分3です。

したがって、「どの番号が4番目に小さいか」または「4つ小さい番号がどれか」と答えたい場合std::nth_elementは、あなたの友達です。

最小の4つの数値を順番に取得したい場合は、の使用を検討してstd::partial_sortください。

于 2012-04-27T14:28:59.383 に答える
10

std::nth_elementの実装は次のようになります。

void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
{
    for (; _ISORT_MAX < _Last - _First; )
        {   // divide and conquer, ordering partition containing Nth
        pair<_RanIt, _RanIt> _Mid =
            _Unguarded_partition(_First, _Last, _Pred);

        if (_Mid.second <= _Nth)
            _First = _Mid.second;
        else if (_Mid.first <= _Nth)
            return; // Nth inside fat pivot, done
        else
            _Last = _Mid.first;
        }

    _Insertion_sort(_First, _Last, _Pred);  // sort any remainder
}

ここで、ISORT_MAXは32として定義されています。

したがって、シーケンスが32要素よりもショットが多い場合は、InsertionSortを実行するだけです。したがって、短いシーケンスは完全にソートされます。

于 2014-11-04T18:48:20.573 に答える
7

std::sortすべての要素を並べ替えます。std::nth_elenemtそうではありません。n番目の要素をn番目の位置に配置し、一方の側に小さい要素または等しい要素を配置し、もう一方の側に大きいまたは等しい要素を配置します。これは、（明らかに）n番目の要素を検索する場合、またはn個の最小または最大の要素が必要な場合に使用されます。フルソートはこれらの要件を満たします。

では、フルソートを実行してn番目の要素を取得してみませんか？O（Nlog（N））std::nth_elementであるのに対し、O（N）の複雑さを持つ必要があるためです。の複雑さの要件を満たすことはできません。範囲を完全に並べ替える必要がない場合は、それを使用すると便利です。std::sortstd::sortstd::nth_element

あなたの例として、GCC 4.7で同様のコードを実行すると、期待どおりの結果が得られます。

  for ( int i = 0; i < 10; i++ )
    myvector.push_back(rand()%32); // make the numbers small

  cout << myvector << "\n";
// nth_element around the 4th element
  nth_element (myvector.begin(), myvector.begin()+4, myvector.end());
  cout << myvector << "\n";
  std::sort(myvector.begin(), myvector.end());
  cout << myvector << "\n";

を生成します

{ 7, 6, 9, 19, 17, 31, 10, 12, 9, 13 }
{ 9, 6, 9, 7, 10, 12, 13, 31, 17, 19 }
{ 6, 7, 9, 9, 10, 12, 13, 17, 19, 31 }
               ^

ここでは、カスタムメイドを使用ostream operator<<して結果を印刷しました。

于 2012-04-27T14:27:31.907 に答える
0

ランダムなunsignedlonglongの大きなベクトル（512MB）で実行し、その中間要素を取得する場合のstd::sortとstd::nth_elementの実行時間を比較しました。はい、私はそれがO（N log（N））対O（N）であることを知っています、とにかく私はstd :: nth_element（mid）がstd::sortの約2倍の速さであると期待しました。要素の約半分を並べ替えます。結果は私を少し驚かせました、それが私がそれらを共有している理由です：

timeSort = 217407 (msec)
timeNthElement = 18218 (msec)

std::sortは約12倍遅くなりました

これが私が使用したコードです（windows.hを使用しています）：

#include <windows.h>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <random>

int main()
{
    static const size_t NUMELEM = 512 * 1024 * 1024;
    static const size_t NUMITER = 3;
    std::vector<unsigned long long> vec1(NUMELEM);
    std::vector<unsigned long long> vec2(NUMELEM);
    std::random_device rd;
    std::mt19937 rand(rd());
    std::uniform_int_distribution<unsigned long long> dist(0, NUMELEM * 2);

    unsigned long long timeNthElement = 0;
    unsigned long long timeSort = 0;

    for (size_t j = 0; j < NUMITER; ++j)
    {
        for (size_t i = 0; i < NUMELEM; ++i)
        {
            unsigned long long val = dist(rand);
            vec1[i] = val;
            vec2[i] = val;
        }
        ULONGLONG t1 = GetTickCount64();
        std::sort(begin(vec1), end(vec1));
        ULONGLONG t2 = GetTickCount64();
        std::nth_element(begin(vec2), begin(vec2)+NUMELEM/2, end(vec2));
        ULONGLONG t3 = GetTickCount64();
        if (vec1[NUMELEM / 2] != vec2[NUMELEM / 2])
        {
            Sleep(0); // I put a breakpoint here but of course never caught it...
        }
        timeSort += t2 - t1;
        timeNthElement += t3 - t2;
    }

    std::cout << "timeSort = " << timeSort << std::endl;
    std::cout << "timeNthElement = " << timeNthElement << std::endl;
    return 0;
}
于 2020-08-27T10:25:39.700 に答える