Posortuj zawartość bardzo dużego (800 GB) pliku tekstowego w systemie Windows

25

Mam plik tekstowy ze słowem w każdej linii, rozmiar pliku to 800 GB. Muszę posortować słowa alfabetycznie.

Próbowałem użyć programu sortującego Windows , używając:

sort.exe input.txt /o output.txt

co daje błąd: Za mało pamięci głównej, aby zakończyć sortowanie.

Mam 32 GB pamięci RAM, więc kiedy próbuję określić 10 GB pamięci dla sortowania przy użyciu:

sort.exe input.txt /o output.txt /M 10000000

Dostaję:

Ostrzeżenie: określony rozmiar pamięci jest redukowany do dostępnej pamięci stronicowania.

Rekord wejściowy przekracza maksymalną długość. Podaj większe maksimum.

Jakie są moje opcje?

MaYaN
źródło
10
To nie jest post-cross, nie jestem maszyną, więc opublikowanie tego i usunięcie drugiego zajmuje kilka minut!
MaYaN
3
W przyszłości pozwól społeczności na migrację twojego pytania
Ramhound
4
W systemie Linux możesz zastosować tę metodę . W przypadku plików 100 Mb nie powinno to stanowić większego problemu.
Eric Duminil,
3
Jakiej wersji systemu Windows używasz? Sort.exe z dość starym systemem Windows Server 2012 R2 twierdzi, że jest w stanie przeprowadzić zewnętrzne sortowanie scalające przy użyciu pliku tymczasowego na dysku (bez dokumentowania limitu rozmiaru). Spróbuj użyć / T, aby określić dysk z 800 GB wolnego miejsca dla pliku tymczasowego. A komunikat „rekord wejściowy przekracza maksymalną długość” wydaje się niezwiązany z przestrzenią - spójrz na opcję / REC i zastanów się, jaki jest twój terminator linii.
davidbak

Odpowiedzi:

16

Jakie są moje opcje?

Wypróbuj bezpłatne narzędzie do sortowania wiersza poleceń CMSort .

Używa wielu plików tymczasowych, a następnie łączy je na końcu.

CMsort czyta rekordy pliku wejściowego, dopóki nie zostanie osiągnięta dostosowana pamięć. Następnie rekordy są sortowane i zapisywane w pliku tymczasowym. Będzie to powtarzane do momentu przetworzenia wszystkich rekordów. Na koniec wszystkie pliki tymczasowe są scalane w plik wyjściowy. Jeśli dostępna pamięć jest wystarczająca, pliki tymczasowe nie są zapisywane i scalanie nie jest konieczne.

Jeden użytkownik informuje, że posortował plik o wartości 130 000 000 bajtów.

Jeśli chcesz poprawić kod samemu, istnieje również Sortowanie ogromnych plików tekstowych - CodeProject - „Algorytm sortowania linii w plikach tekstowych, których rozmiar przekracza dostępną pamięć”

DavidPostill
źródło
26
Wow, 130 megabajtów !!! +1
David Foerster,
3
@DavidPostill Czy jesteś pewien, że sortowanie od coreutils dla Windows nie jest bardziej wydajne ( --parallelopcja, jeśli masz więcej niż jeden rdzeń ...)?
Hastur
23

Inną opcją jest załadowanie pliku do bazy danych. EG MySQL i MySQL Workbench.
Bazy danych są idealnymi kandydatami do pracy z dużymi plikami

Jeśli plik wejściowy zawiera tylko słowa oddzielone nowym wierszem, nie powinno to być trudne.

Po zainstalowaniu bazy danych i MySQL Workbench musisz to zrobić.
Najpierw utwórz schemat (przy założeniu, że słowa nie będą dłuższe niż 255 znaków, chociaż możesz to zmienić, zwiększając wartość argumentu). Pierwsza kolumna „idwords” jest kluczem podstawowym.

CREATE SCHEMA `tmp` ;

CREATE TABLE `tmp`.`words` (
  `idwords` INT NOT NULL AUTO_INCREMENT,
  `mywords` VARCHAR(255) NULL,
  PRIMARY KEY (`idwords`));

Po drugie, zaimportuj dane: EG Spowoduje to zaimportowanie wszystkich słów do tabeli (wykonanie tego kroku może trochę potrwać. Radzę najpierw uruchomić test z plikiem małych słów, a gdy będziesz pewien, że format jest taki sam jak większy (skróć tabelę. IE Wyczyść go i załaduj pełny zestaw danych).

LOAD DATA LOCAL INFILE "C:\\words.txt" INTO TABLE tmp.words
LINES TERMINATED BY '\r\n'
(mywords);


Ten link może pomóc w dostosowaniu formatu do obciążenia. https://dev.mysql.com/doc/refman/5.7/en/load-data.html
EG Jeśli chcesz pominąć pierwszą linię, wykonaj następujące czynności.

LOAD DATA LOCAL INFILE "H:\\words.txt" INTO TABLE tmp.words
-- FIELDS TERMINATED BY ','
LINES TERMINATED BY '\r\n'
IGNORE 1 LINES
(mywords);

Na koniec zapisz posortowany plik. Może to chwilę potrwać, w zależności od komputera.

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
INTO OUTFILE 'C:\\sorted_words.csv';

Możesz również wyszukiwać dane według własnego uznania. EG To da ci pierwsze 50 słów w porządku rosnącym (zaczynając od 0 lub pierwszego słowa).

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
LIMIT 0, 50 ;

Powodzenia
Pete

Peter H.
źródło
2
To jest poprawna odpowiedź ze znacznym marginesem.
MonkeyZeus
1
Takie podejście będzie zdecydowanie bardziej elastyczne, zwłaszcza jeśli odkryjesz, że musisz ponownie uruchomić sortowanie z inną kolejnością, na przykład.
grill
Nie obchodzi mnie, jak szybka jest twoja instancja MySQL , MariaDB lub innego DBMS , nie będzie ona zbliżona do wydajności wstawiania SQLite działającego na tym samym komputerze. Nawet z czymś tak szybkim jak SQLite ta ilość danych jest zbyt duża (i powolna) do przetworzenia (zaufaj mi, że najpierw tego spróbowałem!), Więc najlepszym rozwiązaniem jest sortowanie i usuwanie duplikatów najpierw, a następnie wstawianie do bazy danych, takiej jak SQLite . Więc chociaż to rozwiązanie może być poprawne w niektórych przypadkach, z pewnością nie jest to, co próbuję zrobić. Dziękujemy za poświęcenie czasu na opublikowanie tego.
MaYaN,
Zamawianie przez mywordszajmie wieczność. Nawet z LIMIT, zajmie to tyle samo czasu, ponieważ MySQL będzie musiał przejrzeć każdą pojedynczą wartość mywordsi uporządkować je. Aby to naprawić, musisz wykonać następujące czynności po zakończeniu LOAD DATA. Dodaj indeks do mywords. Teraz możesz zamówić według tej kolumny i nie zajmie to tysiąclecia. I to jest lepiej, aby dodać indeksu po załadowaniu danych niż w momencie utworzonej tabeli (o wiele szybciej obciążenia danymi).
Buttle Butkus
7

sort

Istnieje wiele algorytmów używanych do sortowania plików uporządkowanych i niez uporządkowanych [ 1 ] .
Ponieważ wszystkie te algorytmy są już zaimplementowane, wybierz program już przetestowany.

W coreutils (z Linuksa, ale dostępny również dla systemu Windows [ 2 ] ) istnieje sortpolecenie, które może działać równolegle pod procesorami wielordzeniowymi: zwykle wystarczy.

Jeśli Twój plik jest tak duży , możesz pomóc w przetwarzaniu dzielenia ( split -l), pliku w niektórych porcjach, być może przy użyciu opcji równoległej ( --parallel) i sortowania wynikowych uporządkowanych porcji za pomocą -mopcji ( sortowanie scalone ).
Wyjaśniono tutaj jeden z wielu sposobów (dzielenie pliku, porządkowanie pojedynczych porcji, łączenie uporządkowanych porcji, usuwanie plików tymczasowych).

Uwagi:

  • W systemie Windows 10 istnieje tak zwany podsystem systemu Windows dla systemu Linux, w którym cały przykład systemu Linux wydaje się bardziej naturalny.
  • Sortowanie przy użyciu różnych algorytmów ma różne czasy wykonania, które są skalowane w zależności od liczby pozycji danych do posortowania (O (n m ), O (nlogn) ...).
  • Wydajność algorytmu zależy od kolejności, która jest już obecna w oryginalnym pliku.
    (Na przykład sortowanie bąbelkowe jest najszybszym algorytmem dla już zamówionego pliku - dokładnie N - ale nie jest skuteczne w innych przypadkach).
Hastur
źródło
2

Aby zaoferować alternatywne rozwiązanie dla Petera H, istnieje program q, który pozwala na polecenia SQL w stylu przeciwko plikom tekstowym. Poniższe polecenie zrobiłoby to samo (uruchamiane z wiersza polecenia w tym samym katalogu co plik), bez konieczności instalowania programu SQL Workbench lub tworzenia tabel.

q "select * from words.txt order by c1"

c1 jest skrótem dla kolumny 1.

Możesz wykluczyć zduplikowane słowa za pomocą

q "select distinct c1 from words.txt order by c1"

i wyślij dane wyjściowe do innego pliku

q "select distinct c1 from words.txt order by c1" > sorted.txt
Brian
źródło
Masz pomysł, czy poradzi sobie z plikiem 800 gig?
Rawling,
1
Nie jestem w 100% pewien - testowałem powyższy plik 1200 linii (9 KB). Strona programistów ma stronę „ograniczeń”, która nie wspomina nic o maksymalnym rozmiarze pliku. Duży plik może wciąż napotykać problem z pamięcią.
Brian
3
q nie może przetworzyć takiej ilości danych pamiętaj, że q używa SQLite za sceną, jeśli nie mogę załadować danych bezpośrednio do SQLite, co sprawia, że q może?
MaYaN
2

Jeśli słowa w każdym wierszu pochodzą z ograniczonego słownictwa (np. Angielskiego), możesz posortować listę w czasie O (n + m log m) za pomocą TreeMap i liczenia nagrań (gdzie m jest liczbą unikalnych wartości).

W przeciwnym razie możesz użyć dużego sortera biblioteki Java . Dzieli dane wejściowe na posortowane pliki pośrednie i łączy je wydajnie (ogólnie O (nlogn)). Sortowanie pliku wygląda następująco:

Sorter.serializerTextUtf8()
      .input(inputFile)
      .output(outputFile)
      .loggerStdOut() // display some progress
      .sort();

Utworzyłem plik 1,7 GB (100m linii) z losowo generowanymi 16 znakowymi słowami i posortowałem go jak wyżej w 142s i na podstawie złożoności obliczeniowej metody O (n log n) stosowanej przeze mnie metody Szacuję, że 800 GB 16-znakowych słów byłoby sortowanie jednowątkowe na moim laptopie i5 2,3 GHz z dyskiem SSD zajmuje około 24 godzin.

Dave Moten
źródło