Algorytmy sortowania, które działają na dużej ilości danych

12

Szukam algorytmów sortowania, które mogą działać na dużej ilości danych, tj. Mogą działać nawet wtedy, gdy cały zestaw danych nie może być jednocześnie przechowywany w pamięci głównej.

Jedynym kandydatem, którego do tej pory znalazłem, jest sortowanie według scalania: możesz zaimplementować algorytm w taki sposób, że skanuje on zestaw danych przy każdym scaleniu bez zatrzymywania wszystkich danych w pamięci głównej na raz. Odmiana sortowania scalonego, o której myślę, została opisana w tym artykule w rozdziale Używanie z napędami taśm .

Myślę, że to dobre rozwiązanie (ze złożonością O (nx log (n)), ale jestem ciekawy, czy istnieją inne (być może szybsze) algorytmy sortowania, które mogą działać na dużych zestawach danych, które nie mieszczą się w pamięci głównej.

EDYTOWAĆ

Oto kilka dodatkowych informacji, zgodnie z wymaganiami odpowiedzi:

  • Dane muszą być sortowane okresowo, np. Raz w miesiącu. Nie muszę wstawiać kilku rekordów i stopniowo sortować dane.
  • Mój przykładowy plik tekstowy ma około 1 GB tekstu UTF-8, ale ogólnie chciałem rozwiązać problem, nawet jeśli plik miałby, powiedzmy, 20 GB.
  • Nie ma go w bazie danych i ze względu na inne ograniczenia nie może być.
  • Dane są zrzucane przez innych jako plik tekstowy, mam własny kod do odczytu tego pliku tekstowego.
  • Format danych to plik tekstowy: znaki nowej linii to separatory rekordów.

Jednym z możliwych ulepszeń, które miałem na myśli, było podzielenie pliku na pliki, które są wystarczająco małe, aby można je było posortować w pamięci, a na koniec scalić wszystkie te pliki przy użyciu algorytmu, który opisałem powyżej.

Giorgio
źródło
1
Jakie dane? Różne zestawy danych mogą oznaczać różne algorytmy, które najlepiej pasują do twoich celów.
whatsisname
To plik tekstowy i muszę posortować linie. Linie nie mają ustalonej długości, ale długość nie zmienia się zbytnio (około 50 znaków na rekord).
Giorgio
3
Nie znam twojego środowiska ani ograniczeń, ale w miarę możliwości korzystałbym z bazy danych do sortowania. Jest tak, ponieważ jest prawie w 100% odporny na błędy i będzie znacznie wydajniejszy niż mój kod.
NoChance
Pracuję na Linux / Java. Wdrożyłem sortowanie korespondencji seryjnej i wydaje się, że działa dość płynnie. Sortowanie kilku milionów wierszy zajmuje sporo czasu, ale muszę to robić tylko raz na jakiś czas.
Giorgio
@Giorgio, dobrze, że zaimplementowałeś taki algorytm. Do prac produkcyjnych nadal sugeruję korzystanie z bazy danych. Nie tylko ze względu na szybkość, ale także dla niezawodności i łatwości konserwacji.
NoChance,

Odpowiedzi:

13

Kanonicznym odniesieniem do sortowania i wyszukiwania jest Knuth, tom. 3 . Zacznij tam.

Książka została pierwotnie spisana, gdy komputery były o wiele mniejsze i wolniejsze niż obecnie, co sprawiło, że techniki sortowania z braku pamięci były ważniejsze niż są obecnie postrzegane.

John R. Strohm
źródło
2
Dzięki za referencje: jestem prawie pewien, że znajdę interesujący materiał w książce Knutha. Nie jestem pewien, czy techniki sortowania z braku pamięci nie są dziś aktualne. Może nie do typowych codziennych zadań, ale mogę sobie wyobrazić, że wciąż istnieje wiele sytuacji, w których trzeba przetwarzać bardzo duże zbiory danych.
Giorgio
Algorytmy Knutha są zawsze pomocne. Na przykład sortowanie scalane z buforem sortowania sterty może być bardzo skuteczne i BARDZO łatwe do wdrożenia.
Sulthan
4
Niezbyt przydatna odpowiedź, ponieważ odnośny materiał nie jest bezpłatny. W przypadku OP sugeruję, że Google szuka odpowiedzi. Nie musisz zarabiać 50 dolarów, aby zdobyć książkę, gdy tego rodzaju informacje można znaleźć, przeglądając internet. Oczywiście, prawdopodobnie możesz pobrać to również za darmo z ( ahem ) niektórych stron. Nie zasługuję na zaakceptowaną odpowiedź.
Thomas Eding,
1
@ThomasEding, istnieją takie rzeczy zwane „bibliotekami”, które zawierają duże ilości tych przestarzałych urządzeń do przechowywania i wyszukiwania informacji zwanych „książkami”. „Biblioteki” udostępniają „książki” ZA DARMO. Jeśli twoja konkretna „biblioteka” nie ma konkretnej „książki”, której szukasz, oferują one również BEZPŁATNĄ usługę o nazwie „pożyczka międzybiblioteczna”, która pozwala „bibliotece” pożyczyć „książkę” z innej „biblioteki”, dzięki czemu mogą pożyczyć to tobie.
John R. Strohm,
6

Zewnętrzne scalanie R-Way jak w sortpoleceniu UNIX jest dobrą alternatywą. Z twojego sformułowania nie jestem pewien, czy jest to algorytm, który miałeś na myśli z „sortowaniem scalonym”, a jeśli go nie znasz, spójrz.

Thiton
źródło
Dzięki. Zewnętrzne scalanie R-Way wydaje się inne niż to, co miałem na myśli. Ciekawa lektura.
Giorgio
4

Bez bardziej szczegółowych informacji „Sortowanie według kolejności” jest prawdopodobnie najlepszą odpowiedzią, jaką można uzyskać, jednak można zaimplementować coś znacznie mądrzejszego w zależności od wymagań.

Na przykład, czy możesz po prostu utworzyć indeks pliku w pamięci, a następnie skopiować wszystkie wartości naraz, buforując lokalizację różnych kluczowych wartości? Czy 1/2 mieści się w pamięci jednocześnie, czy 1/1000000? Jeśli jest to drugi, to możesz nie być w stanie zmieścić indeksu w pamięci, jeśli pierwszy, to możesz posortować obie połówki bardziej efektywnie, a następnie scalić je w jednym ostatnim kroku.

Do diabła, ponieważ nie określono, że możliwe jest, że wszystkie dane znajdują się w bazie danych, jeśli tak, możesz po prostu utworzyć tabelę indeksu i nazwać ją dobrą (domyślam się, że tak nie jest, ale po prostu zaznaczam, że Twoja sytuacja ma kluczowe znaczenie dla rozwiązania tak skomplikowanego problemu jak ten).

Jeśli chcesz to zrobić tylko raz i szukasz bardzo szybkiego hacka, wygląda na to, że ten zewnętrzny sposób scalania byłby dobrym początkiem, jeśli używasz Uniksa (ponieważ najwyraźniej jest wbudowany)

Jeśli musisz zachować porządek i zawsze dodajesz pojedynczy rekord, konieczne będzie sortowanie według wstawiania (dodawanie jednego rekordu do posortowanych danych jest zawsze sortowaniem przez wstawianie).

Czy potrafisz kontrolować kod, który „odczytuje” dane? Jeśli tak, to wiele form indeksowania (zamiast sortowania poprzez przenoszenie danych na dysku) pomoże DUŻO (w rzeczywistości będzie absolutnym wymogiem).

Więc:

  • W miejscu czy w wielu plikach?
  • Raz, co jakiś czas, czy zawsze przez cały czas uporządkowane?
  • O ile większy niż pamięć (ile ładowań pamięci, aby przejść przez cały zestaw danych)?
  • Czy to jest w bazie danych? Może być?
  • Czy kontrolujesz kod odczytujący dane, czy też inni będą bezpośrednio zrzucać plik?
  • Format pliku? (Tekst? Naprawiono zapis?)
  • Jakieś inne szczególne okoliczności, o które nie pytałem?
Bill K.
źródło
Dziękuję za odpowiedź. Co rozumiesz przez „W miejscu lub w wielu rekordach”?
Giorgio
Przepraszam, powinienem był sprawdzić moją odpowiedź - miałem na myśli wiele plików. W miejscu prawie implikowane są ustalone rozmiary rekordów i indeksowanie, w którym to momencie prawdopodobnie będziesz potrzebować bazy danych.
Bill K
Nie, nie jest na miejscu: rekordy nie mają ustalonego rozmiaru. Używam czterech plików tymczasowych do mojej bieżącej implementacji.
Giorgio
Czy potrafisz zinterpretować dane wyjściowe za pomocą kodu, czy też musi on mieć określony format (płaski plik tekstowy?) Jak często trzeba go sortować - za każdym razem, gdy coś jest dodawane lub tylko od czasu do czasu? Kiedy coś jest dodawane, czy jest to dodawane tylko na końcu, czy możesz napisać kod, który to dodaje?
Bill K
Każda linia może być parsowana w rekordzie (plik jest plikiem CSV), ale większość pól to tekst. Raz na jakiś czas trzeba go posortować (np. Co miesiąc), a moja obecna implementacja zajmuje około 1 godziny. Aby wstawić wiersz, mógłbym napisać kod, który wstawia wiersz we właściwym miejscu: z kodem, który do tej pory mam, napisanie takiego narzędzia zajęłoby mi 20 minut.
Giorgio
3

Jeśli naprawdę chcesz skalowalnego rozwiązania, powinieneś spojrzeć na TeraSort, standardową implementację sortowania z mapowaniem; więcej szczegółów na temat StackOverflow .

m3th0dman
źródło
1
+1: Ciekawy link. Czy scalanie nie jest przykładem mapowania / zmniejszania, w którym mapa odpowiada sortowaniu list podrzędnych, a redukcja odpowiada scalaniu?
Giorgio
Może się to wydawać, ale możesz użyć Hadoop do zrobienia tego za Ciebie, zamiast pisać to sam.
m3th0dman
1

Możesz być zainteresowany sortowaniem w formie wiadra . Średnia wydajność przypadku to czas liniowy.

= O (n + d) n: liczba elementów id = długość największej liczby, jeśli masz intuicję na temat swoich danych, tj. Jeśli wiesz, ile „cyfr” jest Twoją największą liczbą. Więc jeśli masz 2 miliony liczb 6-cyfrowych => 0 (n), więc liniowych.

kamieniste
źródło
0

Użyj zewnętrznego algorytmu sortowania korespondencji seryjnej (jeśli dane są ciągłe) lub sortowania segmentowego z sortowanie przez zliczanie jako realizacji sortowania do łyżek (jeśli dane są dyskretne i równomiernie rozłożone).

Prawdopodobnie najlepszym rozwiązaniem jest zbudowanie własnego pliku indeksu / odwzorowania, jeśli przyrost jest niewielki.

  1. Jakoś zamów swoją „bazę danych”
  2. Przypisz liczbę całkowitą do każdego wpisu (1, 2, 3, 4, ..., n) (lepiej: użyj niektórych rzadkich indeksów)
  3. Dodając przyrost, po prostu znajdź lukę, w której lewa liczba jest mniejsza lub równa, a prawa liczba jest większa lub równa (nie powinno być to trudne w przypadku niektórych zmodyfikowanych wersji wyszukiwania binarnego)
  4. Wstaw, podczas gdy luki są wystarczająco duże, jeśli nie: po prostu powtórz (nigdy nie sortuj ponownie) :-)
malejpavouk
źródło
0

Właśnie zbudowałem pewne abstrakcyjne struktury zwane dużą kolejką i dużą tablicą, aby uprościć sortowanie i wyszukiwanie dużych danych na jednym komputerze z ograniczoną pamięcią. Zasadniczo zastosowany algorytm jest podobny do tego, o którym wspomniałeś powyżej - sortowanie według scalania zewnętrznego.

Mogę posortować dane 128 GB (każdy element 100 bajtów) w ciągu 9 godzin na jednym komputerze, a następnie wyszukiwać binarnie posortowane dane prawie natychmiast.

Oto post o tym, jak przeszukiwać duże zbiory danych za pomocą mojej wielkiej kolejki i struktur dużej tablicy typu open source.

Buldog
źródło