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?
Odpowiedzi:
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.
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ęć”
źródło
--parallel
opcja, jeśli masz więcej niż jeden rdzeń ...)?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.
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).
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.
Na koniec zapisz posortowany plik. Może to chwilę potrwać, w zależności od komputera.
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).
Powodzenia
Pete
źródło
mywords
zajmie wieczność. Nawet zLIMIT
, zajmie to tyle samo czasu, ponieważ MySQL będzie musiał przejrzeć każdą pojedynczą wartośćmywords
i uporządkować je. Aby to naprawić, musisz wykonać następujące czynności po zakończeniuLOAD DATA
. Dodaj indeks domywords
. 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).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
sort
polecenie, 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ą-m
opcji ( 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:
(Na przykład sortowanie bąbelkowe jest najszybszym algorytmem dla już zamówionego pliku - dokładnie N - ale nie jest skuteczne w innych przypadkach).
źródło
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.
c1
jest skrótem dla kolumny 1.Możesz wykluczyć zduplikowane słowa za pomocą
i wyślij dane wyjściowe do innego pliku
źródło
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:
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.
źródło