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.
źródło
Odpowiedzi:
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.
źródło
Zewnętrzne scalanie R-Way jak w
sort
poleceniu 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.źródło
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:
źródło
Jeśli naprawdę chcesz skalowalnego rozwiązania, powinieneś spojrzeć na TeraSort, standardową implementację sortowania z mapowaniem; więcej szczegółów na temat StackOverflow .
źródło
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.
źródło
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.
źródło
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.
źródło