Algorytmiczne elementy składowe
Zaczynamy od złożenia algorytmicznych bloków konstrukcyjnych z biblioteki standardowej:
#include <algorithm> // min_element, iter_swap,
// upper_bound, rotate,
// partition,
// inplace_merge,
// make_heap, sort_heap, push_heap, pop_heap,
// is_heap, is_sorted
#include <cassert> // assert
#include <functional> // less
#include <iterator> // distance, begin, end, next
- narzędzia iteratora, takie jak non-member
std::begin()/ std::end()oraz as std::next()są dostępne tylko od wersji C ++ 11 i późniejszych. W przypadku C ++ 98 należy je napisać samodzielnie. Istnieją substytuty z Boost.Range w boost::begin()/ boost::end()i od Boost.Utility w boost::next().
std::is_sortedalgorytm jest dostępna tylko dla c ++ 11 i poza nią. W przypadku C ++ 98 można to zaimplementować w postaci std::adjacent_findobiektu funkcji napisanego ręcznie. Boost.Algorytm zapewnia również boost::algorithm::is_sortedjako substytut.std::is_heapalgorytm jest dostępna tylko dla c ++ 11 i poza nią.
Składniowe gadżety
C ++ 14 zapewnia przejrzyste komparatory formy, std::less<>które działają polimorficznie na ich argumenty. Pozwala to uniknąć konieczności podawania typu iteratora. Można tego użyć w połączeniu z domyślnymi argumentami szablonu funkcji w C ++ 11, aby utworzyć pojedyncze przeciążenie dla algorytmów sortujących, które biorą <za porównanie, oraz tych, które mają zdefiniowany przez użytkownika obiekt funkcji porównania.
template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});
W C ++ 11 można zdefiniować alias szablonu wielokrotnego użytku, aby wyodrębnić typ wartości iteratora, co dodaje drobne zakłócenia do podpisów algorytmów sortowania:
template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;
template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});
W C ++ 98 trzeba napisać dwa przeciążenia i użyć pełnej typename xxx<yyy>::typeskładni
template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation
template<class It>
void xxx_sort(It first, It last)
{
xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}
- Kolejną zaletą syntaktyczną jest to, że C ++ 14 ułatwia pakowanie komparatorów zdefiniowanych przez użytkownika za pomocą polimorficznych lambd (z
autoparametrami, które są wywnioskowane jak argumenty szablonu funkcji).
- C ++ 11 ma tylko jednomorficzne lambdy, które wymagają użycia powyższego aliasu szablonu
value_type_t.
- W C ++ 98 należy napisać autonomiczny obiekt funkcji lub zastosować pełną składnię
std::bind1st/ std::bind2nd/ std::not1.
- Boost.Bind poprawia to dzięki składni
boost::bindi _1/ _2placeholder.
- C ++ 11 i poza nim również
std::find_if_not, podczas gdy C ++ 98 potrzeby std::find_ifz std::not1całego obiektu funkcyjnego.
Styl C ++
Nie ma jeszcze ogólnie akceptowanego stylu C ++ 14. Na dobre lub na złe, uważnie śledzę projekt Scotta Meyersa Effective Modern C ++ i odnowiony GotW . Korzystam z następujących zaleceń dotyczących stylu:
- Zalecenia Herb Suttera „Prawie zawsze auto” i zalecenie Scotta Meyersa „Wolę auto od deklaracji określonego typu” , dla których zwięzłość nie ma sobie równych, chociaż jego jasność jest czasem kwestionowana .
- Scott Meyers „Rozróżnij
()i {}podczas tworzenia obiektów” i konsekwentnie wybieraj opcję inicjacji usztywnionej {}zamiast starej dobrej inicjalizacji ()w nawiasach (aby pominąć wszystkie najbardziej irytujące kwestie w kodzie ogólnym).
- Scott Meyers „Wolę deklaracje aliasów niż typedefs” . W przypadku szablonów jest to i tak konieczne, a używanie go wszędzie zamiast
typedefoszczędzać czas i zapewnia spójność.
for (auto it = first; it != last; ++it)W niektórych miejscach używam wzorca, aby umożliwić niezmienne sprawdzanie pętli dla już posortowanych podzakresów. W kodzie produkcyjnym użycie while (first != last)i ++firstgdzieś wewnątrz pętli może być nieco lepsze.
Sortuj wybór
Sortowanie selekcji w żaden sposób nie dostosowuje się do danych, więc jego czas działania jest zawszeO(N²). Jednak sortowanie według wyboru ma właściwość minimalizowania liczby zamian . W aplikacjach, w których koszt wymiany elementów jest wysoki, algorytm wyboru może być bardzo dobrze sortowany.
Aby zaimplementować go przy użyciu biblioteki standardowej, kilkakrotnie użyj, std::min_elementaby znaleźć pozostały minimalny element i iter_swapzamienić go na miejsce:
template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
for (auto it = first; it != last; ++it) {
auto const selection = std::min_element(it, last, cmp);
std::iter_swap(selection, it);
assert(std::is_sorted(first, std::next(it), cmp));
}
}
Zauważ, że selection_sortjuż przetworzony zakres został [first, it)posortowany jako niezmiennik pętli. Minimalne wymagania to iteratory przesyłania dalej , w porównaniu do std::sortiteratorów dostępu swobodnego.
Szczegóły pominięte :
- sortowanie wyboru można zoptymalizować za pomocą wczesnego testu
if (std::distance(first, last) <= 1) return;(lub dla iteratorów do przodu / dwukierunkowych:) if (first == last || std::next(first) == last) return;.
- w przypadku iteratorów dwukierunkowych powyższy test można połączyć z pętlą w przedziale
[first, std::prev(last)), ponieważ ostatni element jest gwarantowanym minimalnym pozostałym elementem i nie wymaga wymiany.
Sortowanie przez wstawianie
Chociaż jest to jeden z elementarnych algorytmów sortowania o O(N²)najgorszym czasie, sortowanie z wstawianiem jest algorytmem z wyboru, gdy dane są prawie posortowane (ponieważ są adaptacyjne ) lub gdy rozmiar problemu jest mały (ponieważ ma niewielki narzut). Z tych powodów oraz ze względu na stabilność , sortowanie wstawiania jest często stosowane jako rekurencyjna podstawa (gdy rozmiar problemu jest niewielki) w celu uzyskania wyższych algorytmów sortowania dziel i zwyciężaj, takich jak sortowanie scalone lub szybkie sortowanie.
Aby zaimplementować insertion_sortw Bibliotece standardowej, kilkakrotnie użyj, std::upper_boundaby znaleźć lokalizację, do której powinien przejść bieżący element, i użyj, std::rotateaby przesunąć pozostałe elementy w górę w zakresie wejściowym:
template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
for (auto it = first; it != last; ++it) {
auto const insertion = std::upper_bound(first, it, *it, cmp);
std::rotate(insertion, it, std::next(it));
assert(std::is_sorted(first, std::next(it), cmp));
}
}
Zauważ, że insertion_sortjuż przetworzony zakres został [first, it)posortowany jako niezmiennik pętli. Sortowanie wstawiania działa również z iteratorami do przodu.
Szczegóły pominięte :
- sortowanie wstawiania można zoptymalizować za pomocą wczesnego testu
if (std::distance(first, last) <= 1) return;(lub dla iteratorów do przodu / dwukierunkowych:) if (first == last || std::next(first) == last) return;i pętli w przedziale [std::next(first), last), ponieważ gwarantuje się, że pierwszy element jest na miejscu i nie wymaga obrotu.
- w przypadku dwukierunkowych iteratorów wyszukiwanie binarne w celu znalezienia punktu wstawienia można zastąpić odwrotnym wyszukiwaniem liniowym za pomocą
std::find_if_notalgorytmu biblioteki standardowej .
Cztery aktywne przykłady ( C ++ 14 , C ++ 11 , C ++ 98 i Boost , C ++ 98 ) dla poniższego fragmentu:
using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first),
[=](auto const& elem){ return cmp(*it, elem); }
).base();
- W przypadku losowych danych wejściowych daje to
O(N²)porównania, ale poprawia się to w O(N)porównaniu do prawie posortowanych danych wejściowych. Wyszukiwanie binarne zawsze wykorzystuje O(N log N)porównania.
- W przypadku małych zakresów wejściowych lepsza lokalizacja pamięci (pamięć podręczna, pobieranie wstępne) wyszukiwania liniowego może również zdominować wyszukiwanie binarne (należy to oczywiście przetestować).
Szybkie sortowanie
Po dokładnym wdrożeniu szybkie sortowanie jest niezawodne i O(N log N)oczekuje się złożoności, ale z O(N²)najgorszą złożonością, która może zostać wywołana przy przeciwnie wybranych danych wejściowych. Gdy sortowanie stabilne nie jest potrzebne, szybkie sortowanie jest doskonałym sortowaniem ogólnego zastosowania.
Nawet w przypadku najprostszych wersji szybkie sortowanie jest nieco bardziej skomplikowane do wdrożenia przy użyciu biblioteki standardowej niż w przypadku innych klasycznych algorytmów sortowania. Poniższe podejście wykorzystuje kilka narzędzi iteratora do zlokalizowania środkowego elementu zakresu wejściowego [first, last)jako osi przestawnej, a następnie użyj dwóch wywołań std::partition(które są O(N)) w celu trójstronnego podziału zakresu wejściowego na segmenty elementów, które są mniejsze niż, równe, i odpowiednio większy niż wybrany element przestawny. Na koniec dwa segmenty zewnętrzne z elementami mniejszymi i większymi niż oś są rekurencyjnie sortowane:
template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
auto const N = std::distance(first, last);
if (N <= 1) return;
auto const pivot = *std::next(first, N / 2);
auto const middle1 = std::partition(first, last, [=](auto const& elem){
return cmp(elem, pivot);
});
auto const middle2 = std::partition(middle1, last, [=](auto const& elem){
return !cmp(pivot, elem);
});
quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
quick_sort(middle2, last, cmp); // assert(std::is_sorted(middle2, last, cmp));
}
Jednak szybkie sortowanie jest dość trudne, aby uzyskać prawidłowe i wydajne, ponieważ każdy z powyższych kroków musi być dokładnie sprawdzony i zoptymalizowany pod kątem kodu poziomu produkcyjnego. W szczególności, dla O(N log N)złożoności, oś przestawna musi skutkować zrównoważonym podziałem danych wejściowych, co nie może być ogólnie gwarantowane dla O(1)osi przestawnej, ale które można zagwarantować, jeśli ustawimy oś jako O(N)medianę zakresu wejściowego.
Szczegóły pominięte :
- powyższa implementacja jest szczególnie podatna na specjalne dane wejściowe, np. ma
O(N^2)złożoność dla danych wejściowych „ piszczałki organowej ” 1, 2, 3, ..., N/2, ... 3, 2, 1(ponieważ środek jest zawsze większy niż wszystkie inne elementy).
- mediana-3- punktowa selekcja przestawna z losowo wybranych elementów z zakresu wejściowego chroni przed prawie posortowanymi danymi wejściowymi, dla których w przeciwnym razie złożoność by się pogorszyła
O(N^2).
- Podział na 3 strony (oddzielanie elementów mniejszych, równych i większych niż oś przestawna), jak pokazują dwa wywołania,
std::partitionnie jest najbardziej wydajnymO(N)algorytmem do osiągnięcia tego wyniku.
- dla przypadkowych iteratorów dostępu , gwarantowane
O(N log N)złożoność można osiągnąć poprzez mediany selekcji obrotu za pomocą std::nth_element(first, middle, last), a następnie rekurencyjnych wywołań quick_sort(first, middle, cmp)i quick_sort(middle, last, cmp).
- ta gwarancja wiąże się jednak z pewnymi kosztami, ponieważ stały współczynnik
O(N)złożoności std::nth_elementmoże być droższy niż O(1)złożoności mediany 3-osiowej, po której następuje O(N)wywołanie std::partition(które jest przyjazne dla pamięci podręcznej pojedyncze przejście do przodu dane).
Scal sortowanie
Jeśli korzystanie z O(N)dodatkowej przestrzeni nie ma znaczenia, sortowanie po scaleniu jest doskonałym wyborem: jest to jedyny stabilny O(N log N) algorytm sortowania.
Jest prosty do wdrożenia przy użyciu standardowych algorytmów: użyj kilku narzędzi iteracyjnych, aby zlokalizować środek zakresu wejściowego [first, last)i połączyć dwa rekursywnie posortowane segmenty z std::inplace_merge:
template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
auto const N = std::distance(first, last);
if (N <= 1) return;
auto const middle = std::next(first, N / 2);
merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
merge_sort(middle, last, cmp); // assert(std::is_sorted(middle, last, cmp));
std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}
Sortowanie po scaleniu wymaga iteratorów dwukierunkowych, przy czym wąskim gardłem jest std::inplace_merge. Pamiętaj, że podczas sortowania list połączonych sortowanie po scaleniu wymaga tylko O(log N)dodatkowego miejsca (do rekurencji). Ten drugi algorytm jest implementowany std::list<T>::sortw bibliotece standardowej.
Sortuj sterty
Sortowanie sterty jest proste do wdrożenia, wykonujeO(N log N)sortowanie na miejscu, ale nie jest stabilne.
Pierwsza pętla, O(N)faza „heapify”, ustawia tablicę w kolejności stosu. Druga pętla, O(N log Nfaza „sortdown”, wielokrotnie wyodrębnia maksimum i przywraca porządek sterty. Biblioteka standardowa sprawia, że jest to wyjątkowo proste:
template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}
W przypadku, gdy uznają to za „oszustwo” w użyciu std::make_heapi std::sort_heapmożna przejść jeden poziom głębiej i pisać te funkcje się w warunkach std::push_heapi std::pop_heapodpowiednio:
namespace lib {
// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
for (auto it = first; it != last;) {
std::push_heap(first, ++it, cmp);
assert(std::is_heap(first, it, cmp));
}
}
template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
for (auto it = last; it != first;) {
std::pop_heap(first, it--, cmp);
assert(std::is_heap(first, it, cmp));
}
}
} // namespace lib
Biblioteka standardowa określa zarówno push_heapi pop_heapjako złożoność O(log N). Zauważ jednak, że zewnętrzna pętla w zakresie [first, last)powoduje O(N log N)złożoność make_heap, a std::make_heapma tylko O(N)złożoność. Dla ogólnej O(N log N)złożoności heap_sortnie ma to znaczenia.
Szczegóły pominięte : O(N)wdrożeniemake_heap
Testowanie
Oto cztery przykłady na żywo ( C ++ 14 , C ++ 11 , C ++ 98 i Boost , C ++ 98 ) testujące wszystkie pięć algorytmów na różnych wejściach (nieprzeznaczonych jako wyczerpujące lub rygorystyczne). Zauważ, że ogromne różnice w LOC: C ++ 11 / C ++ 14 potrzebują około 130 LOC, C ++ 98 i Boost 190 (+ 50%), a C ++ 98 ponad 270 (+ 100%).