Efektywny sposób sortowania konkatenacji list (STL), scalania wskazówek sortowania, częściowego sortowania

Mam sytuację, w której otrzymuję listę wartości, które są już częściowo posortowane. Na mojej liście końcowej znajduje się N bloków, każdy blok jest posortowany. Więc w końcu o listę danych, takich jak ten (ukośniki są tylko dla podkreślenia):Efektywny sposób sortowania konkatenacji list (STL), scalania wskazówek sortowania, częściowego sortowania

1 2 3 4 5 6 7 8/1 2 3 4 5/2 3 4 5 6 7 8 9/1 2 3 4

mam je w wektorze jako serię wskaźników do obiektów. Obecnie używam tylko std::sort z niestandardowym komparatorem do sortowania. Sądzę, że jest to nieoptymalne, ponieważ moja sekwencja jest zdegenerowana.

Czy są jakieś inne funkcje standardowe, wskazówki lub inne, które mogłem użyć, aby zapewnić optymalny rodzaj takich danych? (Biblioteki doładowania również są w porządku).

Chociaż nie mogę łatwo zepsuć danych wejściowych, z pewnością mogę określić, gdzie zaczynają się pod-sekwencje.

Źródło

2010-11-21 edA-qa mort-ora-y

Wierzę, że dla list połączonych sortowanie scalone jest jednym z niewielu algorytmów, które działają dobrze. –

Przez * listę * miałem na myśli tylko abstrakcyjną strukturę danych. W rzeczywistości są one przechowywane w 'std :: vector'. –

Możesz spróbować std::merge, chociaż ten algorytm może scalać tylko dwie posortowane kolekcje, więc musisz wywołać je w pętli. Zauważ też, że std::list zapewnia merge jako funkcję członka.

EDIT Właściwie std::inplace_merge może być jeszcze lepszym kandydatem.

Źródło

2010-11-21 09:52:56 icecrime

Złożoność czasu wykonywania jest taka sama jak sortowanie tutaj. * O (n * log (n)) *. Im mniej podlisty, tym lepsze środowisko wykonawcze. Tylko dla 2 podliści jest * O (n) *. –

Nie mogę łatwo podzielić danych na niezależne listy, aby wykonać sortowanie scalone. Musiałbym utworzyć dwie listy tymczasowe i przejść do jednego podzespołu na raz.Mogę spróbować. Przypuszczam, że przydział pamięci na liście może być droższy niż nieefektywny. –

@ edA-qa: Nie musisz ich dzielić. [std :: merge] (http://www.cppreference.com/wiki/algorithm/merge) pozwala określić element początkowy i końcowy. Jeśli martwisz się pamięcią, możesz rzucić okiem na [std :: inplace_merge] (http://www.cppreference.com/wiki/algorithm/inplace_merge) –

można iterować na wszystkich listach jednocześnie, zachowując i indeksując dla każdej listy. i porównywanie tylko pozycji w tym indeksie.

może to być znacznie szybsze niż zwykłe sortowanie: O (n) kontra O (n * log (n)) gdzie n jest liczbą pozycji we wszystkich listach.

zobacz artykuł wikipedia.

C++ ma std :: merge dla niego, ale nie będzie obsługiwać wielu list naraz, więc możesz stworzyć własną wersję, która ma.

Źródło

2010-11-21 09:51:41

Jeśli zrobisz to źle, zwiększysz całkowite porównania. – Chris

Ta opcja ulega awarii w przypadku wielu podlist. W najgorszym przypadku o podskładkach * n * masz złożoność * O (n²) * w czasie wykonywania. –

Wymaga to "łączenia wieloetapowego". Standardowa biblioteka nie ma odpowiedniego algorytmu do tego. Jednak równoległe rozszerzenie biblioteki standardowej GCC wynosi:

__gnu_parallel::multiway_merge.

Źródło

2010-11-21 09:57:31

Wygląda na to, że mógłbym sprawić, by działał bez dynamicznego przydzielania pamięci. Dzięki! –

To jest zły pomysł, nie jest standardowy i może się zmienić. Spróbuj znaleźć coś bardziej standardowego, jeśli to możliwe. Lub prześlij żądanie funkcji do zwiększenia. –

Ja wolę standardowy, ale niestandardowy mi nie przeszkadza. Korzystam już z kilku wbudowanych GCC w tej części kodu. –

Jeśli możesz zaoszczędzić pamięć, mergesort sprawdzi się bardzo dobrze. Aby uzyskać najlepsze wyniki, połącz dwa najmniejsze łańcuchy naraz, aż do uzyskania tylko jednego.

Źródło

2010-11-21 09:58:51 Chris

Czy kolejność łączenia ma znaczenie? –

Im bliżej są listy, tym mniej średnich porównań jest wymaganych na scalenie. Budowanie od dołu do góry daje optymalną liczbę porównań bez konieczności wykonywania wielu prac planistycznych. Możesz nieznacznie ulepszyć wydajność pamięci podręcznej przy nieco trudniejszym planowaniu, ale naprawdę nie warto. – Chris

Algorytm sortowania, który działa dobrze w przypadku częściowo posortowanych danych, to sortowanie według powłoki. W najlepszym przypadku ma wydajność O (n). Niestety nie jest częścią standardowej biblioteki. Będziesz musiał to zaimplementować samodzielnie.

Źródło

2010-11-21 09:59:22 noxmetus

Rodzaj sortowania podany w pytaniu nie jest już sortowaniem, z którym współpracuje wiele algorytmów sortujących. –

Rodzaj sortowania, o którym mowa w pytaniu, to rodzaj sortowania, w którym szybki typ std ulegnie degeneracji do O (n^2) i jednocześnie jest to rodzaj sortowania, na którym sortowanie Shell będzie bardziej skuteczne . – noxmetus

Na szczęście dla nas standardowa biblioteka nie * używa * quicksort i nigdy nie zwyrodnia się do O (n^2). (Oczywiście, jest to szczegół implementacji, dotyczy jednak każdej nowoczesnej i istotnej implementacji C++ stdlib). –

Efektywny sposób sortowania konkatenacji list (STL), scalania wskazówek sortowania, częściowego sortowania

Odpowiedz

Powiązane problemy