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

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?

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ęć”

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

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

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

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.