Rozwiązuję problem, który polega na bardzo szybkim sortowaniu 10 liczb (int32). Moja aplikacja musi posortować 10 liczb miliony razy tak szybko, jak to możliwe. Próbkuję zestaw danych z miliardami elementów i za każdym razem muszę wybrać z niego 10 liczb (uproszczone) i posortować je (i wyciągnąć wnioski z posortowanej listy 10 elementów).
Obecnie używam sortowania wstawianego, ale wyobrażam sobie, że mógłbym zaimplementować bardzo szybki niestandardowy algorytm sortowania dla mojego specyficznego problemu 10 liczb, który pokonałby sortowanie wstawiane.
Czy ktoś ma pojęcie o tym, jak podejść do tego problemu?
algorithm
sorting
insertion-sort
sorting-network
bodacydo
źródło
źródło
if
instrukcji powinna działać najlepiej. Unikaj pętli.Odpowiedzi:
(W następstwie sugestii HelloWorld, aby przejrzeć sieci sortujące).
Wygląda na to, że sieć porównania / wymiany 29 jest najszybszym sposobem na sortowanie 10-wejściowe. Użyłem sieci odkrytej przez Waksmana w 1969 r. Do tego przykładu w JavaScript, który powinien zostać przetłumaczony bezpośrednio na C, ponieważ jest to tylko lista
if
instrukcji, porównań i zamian .Oto graficzna reprezentacja sieci, podzielona na niezależne fazy. Aby skorzystać z przetwarzania równoległego, grupowanie 5-4-3-4-4-4-3-2 można zmienić na grupowanie 4-4-4-4-4-4-3-2.
źródło
#define SORTPAIR(data, i1, i2) if (data[i1] > data[i2]) { int swap = data[i1]... }
Kiedy zajmujesz się tym ustalonym rozmiarem, spójrz na Sorting Networks . Algorytmy te mają ustalony czas działania i są niezależne od wprowadzanych danych. W twoim przypadku użycia nie masz takiego narzutu, jaki mają niektóre algorytmy sortowania.
Sortowanie bitoniczne jest implementacją takiej sieci. Ten działa najlepiej z len (n) <= 32 na CPU. Przy większych wejściach można pomyśleć o przejściu na GPU. https://en.wikipedia.org/wiki/Sorting_network
Btw, dobra strona do porównywania algorytmów sortowania jest tutaj tutaj (choć brakuje jej
bitonic sort
.http://www.sorting-alameterms.com
źródło
Użyj sieci sortującej, która ma porównania w grupach po 4, dzięki czemu możesz to zrobić w rejestrach SIMD. Para spakowanych instrukcji min / max implementuje funkcję upakowanego komparatora. Niestety nie mam teraz czasu na poszukiwanie strony, o której pamiętam, ale mam nadzieję, że wyszukiwanie w sieciach sortujących SIMD lub SSE coś zmieni.
x86 SSE ma instrukcje spakowanych liczb całkowitych 32-bitowych liczb całkowitych dla wektorów czterech liczb 32-bitowych. AVX2 (Haswell i nowsze) mają to samo, ale dla wektorów 256b z 8 ints. Istnieją również wydajne instrukcje losowania.
Jeśli masz wiele niezależnych małych rodzajów, może być możliwe wykonanie 4 lub 8 rodzajów równolegle przy użyciu wektorów. Esp. jeśli wybierasz elementy losowo (aby dane do sortowania i tak nie były ciągłe w pamięci), możesz uniknąć przetasowań i po prostu porównać w wymaganej kolejności. 10 rejestrów do przechowywania wszystkich danych z 4 (AVX2: 8) list 10 ints wciąż pozostawia 6 rejestrów do miejsca na zarysowania.
Sieci do sortowania wektorowego są mniej wydajne, jeśli trzeba również sortować powiązane dane. W takim przypadku najbardziej wydajnym sposobem wydaje się być użycie spakowanego porównania, aby uzyskać maskę, której elementy uległy zmianie, i użyć tej maski do mieszania wektorów (odniesień do) powiązanych danych.
źródło
Co z rozwiniętym sortowaniem bez rozgałęzień?
http://coliru.stacked-crooked.com/a/71e18bc4f7fa18c6
Jedyne istotne wiersze to pierwsze dwa
#define
.Używa dwóch list i całkowicie ponownie sprawdza pierwszą dziesięciokrotnie, co byłoby źle zaimplementowanym rodzajem selekcji, jednak unika gałęzi i pętli o zmiennej długości, które mogą kompensować nowoczesne procesory i tak mały zestaw danych.
Reper
Przeprowadziłem testy porównawcze względem sieci sortującej, a mój kod wydaje się być wolniejszy. Próbowałem jednak usunąć rozwijanie i kopię. Uruchamianie tego kodu:
Konsekwentnie osiągam lepszy wynik dla sortowania bez gałęzi w porównaniu do sieci sortującej.
źródło
for ( ; i<10; i++) (m > a[i]) && (m = a[i], indx = i );
jest wyjątkowo dobrze zoptymalizowana. (zwarcie jest zwykle rodzajem rozgałęzienia)std::shuffle
zfor (int n = 0; n<10; n++) a[n]=g();
. Czas wykonania jest o połowę krótszy, a sieć szybsza.std::sort
?std::sort
też, ale działało tak źle, że nawet nie uwzględniłem go w teście porównawczym. Wydaje mi się, że przy małych zestawach danych jest to dość duże obciążenie.Pytanie nie mówi, że jest to pewnego rodzaju aplikacja internetowa. Jedyną rzeczą, która wpadła mi w oko, było:
Jako inżynier oprogramowania i sprzętu absolutnie krzyczy mi „FPGA” . Nie wiem, jakie wnioski należy wyciągnąć z posortowanego zestawu liczb lub skąd pochodzą dane, ale wiem, że przetworzenie gdzieś od stu milionów do miliarda z tych „sortujących i… analizować „operacje na sekundę . W przeszłości wykonywałem sekwencjonowanie DNA przy pomocy FPGA. Niemożliwe jest pokonanie ogromnej mocy obliczeniowej układów FPGA, gdy problem dobrze pasuje do tego typu rozwiązania.
Na pewnym poziomie jedynym czynnikiem ograniczającym jest to, jak szybko można przerzucić dane do FPGA i jak szybko można je wyciągnąć.
Jako punkt odniesienia zaprojektowałem wysokowydajny procesor obrazu w czasie rzeczywistym, który odbierał 32-bitowe dane obrazu RGB z szybkością około 300 milionów pikseli na sekundę. Dane przesyłane strumieniowo przez filtry FIR, mnożniki macierzy, tabele odnośników, bloki wykrywania krawędzi przestrzennych i szereg innych operacji przed wyjściem na drugi koniec. Wszystko to na stosunkowo małej FPGA Xilinx Virtex2 z wewnętrznym taktowaniem od około 33 MHz do, o ile dobrze pamiętam, 400 MHz. Och, tak, miał także implementację kontrolera DDR2 i obsługiwał dwa banki pamięci DDR2.
FPGA może wyprowadzać rodzaj dziesięciu 32-bitowych liczb przy każdym przejściu zegara podczas pracy z setkami MHz. Na początku operacji wystąpiłoby krótkie opóźnienie, ponieważ dane wypełniają rurociąg (y) przetwarzania. Następnie powinieneś być w stanie uzyskać jeden wynik na zegar. Lub więcej, jeśli przetwarzanie może być zrównoleglone poprzez replikację potoku sortowania i analizy. Rozwiązanie jest w zasadzie banalne.
Chodzi o to: jeśli aplikacja nie jest powiązana z komputerem, a strumień danych i przetwarzanie są „kompatybilne” z rozwiązaniem FPGA (samodzielnym lub jako karta koprocesora w maszynie), nie ma mowy być w stanie pokonać osiągalny poziom wydajności dzięki oprogramowaniu napisanemu w dowolnym języku, niezależnie od algorytmu.
EDYTOWAĆ:
Po prostu uruchomiłem szybkie wyszukiwanie i znalazłem gazetę, która może Ci się przydać. Wygląda na to, że pochodzi z 2012 roku. Dzisiaj możesz zrobić DUŻO lepszą wydajność (a nawet wtedy). Oto on:
Sortowanie sieci według układów FPGA
źródło
Niedawno napisałem małą klasę, która wykorzystuje algorytm Bose-Nelson do generowania sieci sortującej w czasie kompilacji.
Można go użyć do stworzenia bardzo szybkiego sortowania dla 10 liczb.
Zauważ, że zamiast
if (compare) swap
instrukcji jawnie kodujemy trójskładnikowe operatory dla wartości min i max. Ma to na celu skłonienie kompilatora do używania kodu bez rozgałęzień.Benchmarki
Poniższe testy porównawcze zostały skompilowane z clang -O3 i uruchomione na moim MacBooku Air z połowy 2012 roku.
Sortowanie losowych danych
Porównując go z kodem DarioP, oto liczba milisekund potrzebnych do posortowania 1 miliona 32-bitowych tablic int o rozmiarze 10:
Siatka sortująca na sztywno 10: 88,774 ms Sortowanie według matrycy
Bose-Nelson 10: 27,815 ms
Korzystając z tego szablonowego podejścia, możemy również generować sieci sortujące po czasie kompilacji dla innej liczby elementów.
Czas (w milisekundach) na posortowanie 1 miliona tablic o różnych rozmiarach.
Liczba milisekund dla tablic o rozmiarach 2, 4, 8 wynosi odpowiednio 1.943, 8.655, 20.246.
Podziękowania dla Glenna Teitelbauma za rodzaj rozwijanego wstawiania.
Oto średnie zegary według rodzaju dla małych zestawów 6 elementów. Kod testu i przykłady można znaleźć pod tym pytaniem:
Najszybszy rodzaj tablicy int o stałej długości 6
Działa tak szybko, jak najszybszy przykład w pytaniu dla 6 elementów.
Wydajność sortowania posortowanych danych
Często tablice wejściowe mogą być już posortowane lub w większości posortowane.
W takich przypadkach lepszym wyborem może być rodzaj wstawiania.
Możesz wybrać odpowiedni algorytm sortowania w zależności od danych.
Kod użyty do testów porównawczych można znaleźć tutaj .
źródło
v1 = v0 < v1 ? v1 : v0; // Max
nadal mogą oddziału, w tym przypadku może być zastąpionev1 += v0 - t
, ponieważ jeślit
jestv0
wtedyv1 + v0 -t == v1 + v0 - v0 == v1
jeszczet
jestv1
iv1 + v0 -t == v1 + v0 - v1 == v0
maxss
lubminss
na nowoczesnych kompilatorach. Ale w przypadkach, gdy to nie działa, można zastosować inne sposoby zamiany. :)Chociaż sortowanie sieciowe ma duże szanse, że będzie szybkie na małych tablicach, czasem nie można pokonać sortowania wstawiania, jeśli jest odpowiednio zoptymalizowane. Na przykład wkładka wsadowa z 2 elementami:
źródło
in[y+2]= in[y];
, literówka?Możesz w pełni rozwinąć
insertion sort
Aby to ułatwić, rekursywne
template
s mogą być używane bez narzutu funkcji. Ponieważ już jest totemplate
,int
może być równieżtemplate
parametrem. To sprawia, że tworzenie tablic kodowania innych niż 10 jest banalne.Pamiętaj, że sortowanie
int x[10]
połączenia odbywa się,insert_sort<int, 9>::sort(x);
ponieważ klasa korzysta z indeksu ostatniego elementu. Można to zawinąć, ale to będzie więcej kodu do przeczytania.W moich testach było to szybsze niż przykłady sieci sortowania.
źródło
Z powodów podobnych do tych, które opisałem tutaj , funkcje po sortowaniu
sort6_iterator()
isort10_iterator_local()
powinny wykonywać dobrze, gdzie sieć sortowania zostało pobranych z tutaj :Aby wywołać tę funkcję, przekazałem
std::vector
iterator.źródło
Sortowanie wstawiania wymaga średnio 29,6 porównań, aby posortować 10 danych wejściowych, przy czym najlepszy przypadek to 9, a najgorszy wynik to 45 (dane wejściowe są w odwrotnej kolejności).
Sortowanie pocisków {9,6,1} wymaga średnio 25,5 porównań, aby posortować 10 danych wejściowych. Najlepszy przypadek to 14 porównań, najgorszy to 34, a sortowanie odwróconego wejścia wymaga 22.
Zatem użycie shellsort zamiast sortowania wstawiania zmniejsza średnią wielkość liter o 14%. Chociaż najlepszy przypadek jest zwiększony o 56%, najgorszy przypadek jest zmniejszony o 24%, co jest znaczące w aplikacjach, w których ważne jest utrzymanie najgorszego przypadku pod kontrolą. Odwrotna sprawa jest zmniejszona o 51%.
Ponieważ wydaje się, że znasz sortowanie wstawiania, możesz zaimplementować algorytm jako sieć sortującą dla {9,6}, a następnie zastosować sortowanie wstawiania ({1}) po tym:
źródło