2012-04-27 31 views
15

Szukałem na std :: nth_element algorytm, który najwyraźniej:Jaka jest praktyczna różnica między std :: nth_element a std :: sort?

zmienia kolejność elementów w przedziale [pierwszy i ostatni), w taki sposób, że element w uzyskanej pozycji n jest element, który w tej pozycji byłby w tej pozycji uporządkowany, przy czym żaden z elementów nie byłby większy i żaden z elementów po nim nie byłby mniejszy niż on. Ani elementy poprzedzające go, ani następujące po nim elementy nie mogą być uporządkowane.

Jednak z mojego kompilatora, uruchamiając następujące:

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; 

zawsze zwraca całkowicie posortowaną listę liczb całkowitych w dokładnie taki sam sposób, jak std :: sort robi. Czy czegoś brakuje? Do czego jest przydatny ten algorytm?

EDIT: Ok następujący przykład stosując znacznie większy zestaw pokazuje, że nie jest dość różnica:

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; 
+2

Tylko dlatego, że implementacja wydaje się robić to za proste przykłady, nie oznacza, że ​​zawsze to robi, ani że wszystkie inne implementacje to robią. – PlasmaHH

+1

Jaki kompilator, jaka implementacja biblioteki? Wypróbuj większe tablice w liczbie 10000. –

+1

Używanie "sortowania" wewnętrznie jako aliasu dla 'nth_element' spełnia formalną regułę. –

Odpowiedz

34

To całkowicie ważne, aby std::nth_element sortować cały zakres dla udokumentowanego semantycznego - jednak nie spełni wymaganej złożoności (liniowej). Kluczową sprawą jest to, że może to być może zrobić, ale to nie ma mieć do.

Oznacza to, że std::nth_element może wyskoczyć wcześniej - gdy tylko będzie mógł stwierdzić, jaki będzie element Twojego zakresu, może się zatrzymać.Na przykład, w odniesieniu do zakresu

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

prosząc go, aby dać Ci czwarty element może otrzymując coś

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

Lista została częściowo sortowane, po prostu wystarczająco dobre, aby móc powiedzieć, że czwartego elementu w kolejności będzie 3.

Dlatego jeśli chcesz odpowiedzieć "która liczba to czwarta-najmniejsza" lub "która jest czterema najmniejszymi" liczbami, to twoim przyjacielem jest std::nth_element.

Jeśli chcesz uzyskać cztery najmniejsze numery w kolejności, możesz rozważyć użycie std::partial_sort.

+6

+1 za wprowadzenie 'partial_sort'. –

+0

Świetne wyjaśnienie z dobrymi przykładami przydatności, dziękuję :-) – Benj

+0

Jaka jest różnica między std :: partition a std :: nth_element? – soandos

5

std::sort sortuje wszystkie elementy. std::nth_elenemt nie. Po prostu umieszcza n-ty element w n-tym położeniu, z mniejszymi lub równymi elementami po jednej stronie i większymi lub równymi elementami po drugiej. Jest używany, jeśli chcesz znaleźć n-ty element (oczywiście) lub jeśli chcesz n najmniejszych lub największych elementów. Pełne sortowanie spełnia te wymagania.

Dlaczego więc nie wykonać pełnego sortowania i uzyskać n-ty element? Ponieważ std::nth_element ma wymaganie złożoności O (N), natomiast std::sort jest O (Nlog (N)). std::sort nie może spełnić wymagania złożoności std::nth_element. Jeśli nie potrzebujesz pełnego sortowania zakresu, korzystniej go używać.

Jak dla przykładu, kiedy uruchomić podobny kod na GCC 4.7, dostaję oczekiwanych rezultatów:

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"; 

produkuje

{ 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 } 
      ^

gdzie Użyłem zamówienie ostream operator<< do druku wyniki.

6

Realizacja std :: nth_element wygląda następująco:

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 
} 

gdzie ISORT_MAX zdefiniowany jako 32.

Więc jeśli sekwencja jest Shoter niż 32 elementów to po prostu wykonuje Sortowanie przez wstawianie na nim. Dlatego Twoja krótka sekwencja jest sortowana w całości.

+2

Ten fragment kodu wyjaśnia, dlaczego krótkie sekwencje są w pełni sortowane, co powoduje, że zastanawiamy się, jak to jest możliwe przy złożoności O (n). Implementacja używa algorytmu wyboru, dopóki pozostały zakres nie będzie większy niż ISORT_MAX, a następnie posortuje ten zakres [_First, _Last] według sortowania insercji. –

+0

Jest to średnio O (n). A sortowanie tablic 32-elementowych zajmuje niewielką liczbę operacji, możemy je traktować jako stałe asymptotycznie. @DavidKhosid – Temak

+0

Które wdrożenie? Standard definiuje tylko to, co biblioteka musi zrobić; poszczególni operatorzy decydują, w jaki sposób jest on osiągany, a nie powołujesz się na stdlib tego narzędzia. Szybkie Google sugeruje mi, że pochodzi ze STL lub jego pochodnej, ale nie powinienem szukać. –

Powiązane problemy