Sortowanie wektora w kolejności malejącej

310

Powinienem użyć

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

lub

std::sort(numbers.rbegin(), numbers.rend());   // note: reverse iterators

posortować wektor w kolejności malejącej? Czy są jakieś zalety lub wady jednego lub drugiego podejścia?

fredoverflow
źródło
2
+1 Myślę, że odpowiedź jest oczywista, ale to pytanie ma ciekawą ciekawostkę. :)
wilhelmtell
3
Głosowałbym na pierwszą opcję, tylko dlatego, że nigdy nie będę musiał sobie z nią radzić reverse_iterator.
evandrix
2
@wilhelmtell Pytanie noob, ale dlaczego drugi powinien sortować w kolejności malejącej? Podajemy tę samą tablicę, co dane wejściowe do metody sortowania. Po prostu podajemy go w odwrotnej kolejności, więc dlaczego miałby być sortowany w kolejności malejącej, a nie rosnącej, tak jak w przypadku ar.begin () i ar.end.
shshnk
6
@shshnk std::sort(b, e);stawia minimum na b(w naszym przypadku rbegin, więc ostatni element) i maksimum na e(w naszym przypadku rend, więc pierwszy element).
fredoverflow

Odpowiedzi:

114

Właściwie pierwszy to zły pomysł. Użyj albo drugiego , albo tego:

struct greater
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};

std::sort(numbers.begin(), numbers.end(), greater());

W ten sposób Twój kod nie zostanie po cichu zerwany, gdy ktoś zdecyduje się numberswstrzymać longlub long longzamiast niego int.

użytkownik541686
źródło
1
@FredOverflow: Zrobiłeś zaszczyty w swoim komentarzu;)
user541686 28.04.2013
2
Lub trzymaj się pierwszego. Użyj typeedef dla numberContainer - dobry pomysł, aby ktoś MOŻE zamienić na długi - i napisz: std :: sort (numbers.begin (), numbers.end (), std :: greater <numContainer :: value_type> ( ));
RichardHowells
1
+1 Pierwszy jest naprawdę mylący. Co jest greaterinne? rbegini rendzostały wykonane w określonym celu.
Abhishek Divekar,
6
Dlaczego nie tylko std::greater<typename decltype(numbers)::value_type>()czy coś?
einpoklum
1
Ta odpowiedź jest nieaktualna - możesz używać std::greater<>()od C ++ 14.
Nikolai
70

Użyj pierwszego:

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

To jawne, co się dzieje - mniejsze prawdopodobieństwo błędnej rbeginjak begin, nawet z komentarzem. Jest jasny i czytelny, a dokładnie tego chcesz.

Ponadto drugi może być mniej wydajny niż pierwszy, biorąc pod uwagę naturę iteratorów odwrotnych, chociaż trzeba by go profilować, aby mieć pewność.

Pubby
źródło
68

W c ++ 14 możesz to zrobić:

std::sort(numbers.begin(), numbers.end(), std::greater<>());
niepokojące
źródło
30

A co z tym?

std::sort(numbers.begin(), numbers.end());
std::reverse(numbers.begin(), numbers.end());
shoumikhin
źródło
13
Powodem może być uniknięcie dodatkowej złożoności: O (n * log (n)) + O (n) vs O (n * log (n))
greg
32
@greg O (n * log (n)) = O (n * log (n) + n). Są dwa sposoby definiowania tego samego zestawu. Chcesz powiedzieć „To może być wolniejsze”.
pjvandehaar
4
@pjvandehaar Greg jest w porządku. On wyraźnie nie powiedział: O (n * log (n) + n), powiedział O (n * log (n)) + O (n). Masz rację, że jego sformułowania są niejasne (szczególnie jego niewłaściwe użycie złożoności słowa), ale mógłbyś odpowiedzieć w bardziej uprzejmy sposób. Np .: Może chciałeś użyć słowa „obliczenie” zamiast słowa „złożoność”. Odwracanie liczb jest niepotrzebnym krokiem O (n) do identycznego poza tym kroku O (n * log (n)).
Ofek Gila
3
@OfekGila Rozumiem, że notacja big-O dotyczy zbiorów funkcji, a notacja zawiera =i +oznacza tylko wygody oznaczające i . W takim przypadku O(n*log(n)) + O(n)jest to wygodny zapis, dla O(n*log(n)) ∪ O(n)którego jest taki sam jak O(n*log(n)). Słowo „obliczenie” jest dobrą sugestią i masz rację co do tonu.
pjvandehaar
22

Zamiast funktora, jak zaproponował Mehrdad, można użyć funkcji Lambda.

sort(numbers.begin(), numbers.end(), [](const int a, const int b) {return a > b; });
Julian Declercq
źródło
16

Według mojej maszyny sortowanie long longwektora [1..3000000] przy użyciu pierwszej metody zajmuje około 4 sekund, podczas gdy użycie drugiej zajmuje około dwa razy więcej czasu. To oczywiście coś mówi, ale ja też nie rozumiem, dlaczego. Pomyśl tylko, że byłoby to pomocne.

To samo zgłoszono tutaj .

Jak powiedział Xeo, -O3wykorzystują mniej więcej tyle samo czasu na zakończenie.

zw324
źródło
12
Czy może po prostu nie skompilowałeś przy włączonych optymalizacjach? Wygląda na to, że reverse_iteratoroperacje nie zostały wprowadzone, a biorąc pod uwagę, że są one tylko otokami rzeczywistych iteratorów, nic dziwnego, że zajmują dwa razy więcej czasu bez wprowadzania.
Xeo
@Xeo Nawet jeśli zostały wprowadzone, niektóre implementacje używają dodatków według dereferencji.
Pubby
@ildjarn: Bo tak to jest? Na base()przykład funkcja członka zwraca zawinięty iterator.
Xeo
1
@Xeo Teraz oba kończą w sekundę. Dzięki!
zw324
3
@Xeo: Cofam to; norma faktycznie nakazuje, że std::vector<>::reverse_iteratorjest wdrażana pod względem std::reverse_iterator<>. Dziwaczny; Dzisiaj się uczę. :-P
ildjarn
11

Pierwsze podejście dotyczy:

    std::sort(numbers.begin(), numbers.end(), std::greater<>());

Możesz zastosować pierwsze podejście ze względu na większą wydajność niż drugie.
Złożoność czasowa pierwszego podejścia mniejsza niż druga.

rashedcs
źródło
To jest ta sama odpowiedź, co mrexciting. Uwaga na temat złożoności jest również dla mnie niejasna.
Philipp Claßen,
7
bool comp(int i, int j) { return i > j; }
sort(numbers.begin(), numbers.end(), comp);

źródło
4
by być poprawną odpowiedzią, powinieneś pomyśleć o napisaniu czegoś o zaletach /
wadach
3

TL; DR

Użyj dowolnego. Są prawie takie same.

Nudna odpowiedź

Jak zwykle są plusy i minusy.

Użyj std::reverse_iterator:

  • Podczas sortowania typów niestandardowych i nie chcesz implementować operator>()
  • Gdy jesteś zbyt leniwy, aby pisać std::greater<int>()

Użyj, std::greatergdy:

  • Gdy chcesz mieć bardziej wyraźny kod
  • Gdy chcesz uniknąć używania niejasnych iteratorów odwrotnych

Jeśli chodzi o wydajność, obie metody są równie wydajne. Próbowałem następującego testu porównawczego:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std::chrono;

/* 64 Megabytes. */
#define VECTOR_SIZE (((1 << 20) * 64) / sizeof(int))
/* Number of elements to sort. */
#define SORT_SIZE 100000

int main(int argc, char **argv) {
    std::vector<int> vec;
    vec.resize(VECTOR_SIZE);

    /* We generate more data here, so the first SORT_SIZE elements are evicted
       from the cache. */
    std::ifstream urandom("/dev/urandom", std::ios::in | std::ifstream::binary);
    urandom.read((char*)vec.data(), vec.size() * sizeof(int));
    urandom.close();

    auto start = steady_clock::now();
#if USE_REVERSE_ITER
    auto it_rbegin = vec.rend() - SORT_SIZE;
    std::sort(it_rbegin, vec.rend());
#else
    auto it_end = vec.begin() + SORT_SIZE;
    std::sort(vec.begin(), it_end, std::greater<int>());
#endif
    auto stop = steady_clock::now();

    std::cout << "Sorting time: "
          << duration_cast<microseconds>(stop - start).count()
          << "us" << std::endl;
    return 0;
}

Za pomocą tego wiersza poleceń:

g++ -g -DUSE_REVERSE_ITER=0 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out
g++ -g -DUSE_REVERSE_ITER=1 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out

std::greater demo std::reverse_iterator demo

Czasy są takie same. Valgrind zgłasza taką samą liczbę braków pamięci podręcznej.

ivaigult
źródło
2

Nie sądzę, że powinieneś użyć jednej z metod w pytaniu, ponieważ obie są mylące, a druga jest krucha, jak sugeruje Mehrdad.

Zalecałbym następujące, ponieważ wygląda ona jak standardowa funkcja biblioteki i wyraźnie wyjaśnia jej intencję:

#include <iterator>

template <class RandomIt>
void reverse_sort(RandomIt first, RandomIt last)
{
    std::sort(first, last, 
        std::greater<typename std::iterator_traits<RandomIt>::value_type>());
}
Martin Broadhurst
źródło
2
To jest tysiąc razy bardziej mylące niż zwykłe korzystanie z std::greaterkomparatora ...
Apollys obsługuje Monikę
@Apollys Zgadzam się, że począwszy od C ++ 14, std :: greater <> wygląda jak preferowane rozwiązanie. Jeśli nie masz C ++ 14, może być przydatne, jeśli chcesz wykluczyć wszelkie niespodzianki ze std :: greater <int> (np. Gdy typy w pewnym momencie zmieniają się z int na long).
Philipp Claßen,
2

Możesz użyć pierwszego lub wypróbować poniższy kod, który jest równie wydajny

sort(&a[0], &a[n], greater<int>());
Krish Munot
źródło