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

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.

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.

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.

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?

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

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.

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) :-)

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.