Algorytm sortowania: plik dużego tekstu z liniami o zmiennej długości (wartości rozdzielane przecinkami)

Question

Co to jest dobry algorytm do sortowania plików tekstowych, które są większe niż dostępna pamięć (wiele 10 gigabajtów) i zawierają rekordy o zmiennej długości? Wszystkie algorytmy, które widziałem, zakładają 1) dane mieszczą się w pamięci lub 2) rekordy mają stałą długość. Ale wyobraźmy sobie duży plik CSV, który chciałem rozwiązać przez „Data urodzenia” pola (pole 4.):

Id,UserId,Name,BirthDate 
1,psmith,"Peter Smith","1984/01/01" 
2,dmehta,"Divya Mehta","1985/11/23" 
3,scohen,"Saul Cohen","1984/08/19" 
... 
99999999,swright,"Shaun Wright","1986/04/12" 
100000000,amarkov,"Anya Markov","1984/10/31" 

wiem, że:

1. będzie to działać na jeden komputerze (nie Rozpowszechniane).
2. Maszyna, na której działałbym, miała kilka procesorów.
3. Pliki, które będę sortował, mogą być większe niż pamięć fizyczna urządzenia.
4. Plik zawiera linie o zmiennej długości. Każda linia składa się ze stałej liczby kolumn (wartości oddzielone separatorami). Plik zostanie posortowany według określonego pola (tj. 4. pola w pliku).
5. Idealne rozwiązanie prawdopodobnie "użyje tego istniejącego narzędzia do sortowania", ale szukam najlepszego algorytmu .
6. Nie oczekuję w pełni zakodowanej, działającej odpowiedzi; coś więcej na wzór "sprawdź to, oto jak działa, lub tutaj, dlaczego działa dobrze dla tego problemu." Po prostu nie wiem, gdzie szukać ...
7. To nie jest praca domowa!

Dzięki! ♥

Answer 1

Ta klasa algorytmów nazywa się sortowaniem zewnętrznym. Zacznę od sprawdzenia Wikipedia entry. Zawiera dyskusję i wskazówki.

Answer 2

Standardowe podejście sortowania seryjnego zadziała. Wspólny schemat jest

1. podzielić plik na N części mniej więcej jednakowej wielkości
2. Sortuj każda część (w pamięci, jeśli jest na tyle mała, inaczej rekurencyjnie zastosować ten sam algorytm)
3. Merge posortowanych części

Answer 3

Zaproponuj następujące zasoby:

Merge Sort: http://en.wikipedia.org/wiki/Merge_sort

Algorytmy Seminumeryczne, tom 2 sztuki programowania komputerowego: Knuth: Addison Wesley: ISBN 0-201-03822-6 (v.2)

Answer 4

Nie ma potrzeby sortowania. Odczytaj plik ALL.CSV i dołączaj każdą linię odczytu do pliku na dzień, np. 19841231.CSV. Dla każdego dnia z danymi, w kolejności numerycznej, odczytaj ten plik CSV i dołącz te linie do nowego pliku. Optymalizacje są możliwe, na przykład, przetwarzając oryginalny plik więcej niż raz lub rejestrując dni faktycznie występujące w pliku ALL.CSV.

Zatem do pliku 19850228.CSV należy dodać wiersz zawierający "1985/02/28". Plik 19850228.CSV należy dołączyć do NEW.CSV po tym, jak plik 19850227.CSV został dołączony do NEW.CSV.W porządku numerycznym unika się stosowania algorytmów sortowania, choć może to prowadzić do torturowania systemu plików.

W rzeczywistości plik ALL.CSV można podzielić na plik na przykład na rok. 1984.CSV, 1985.CSV, i tak dalej.