Classifique o conteúdo de um arquivo de texto extremamente grande (800 GB) no Windows

Question

Eu tenho um arquivo texto com uma palavra em cada linha, o tamanho do arquivo é 800GB. Eu preciso classificar as palavras em ordem alfabética.

Eu tentei usar o programa Windows sort usando:

sort.exe input.txt /o output.txt

que dá o erro: Não há memória principal suficiente para completar o tipo.

Tenho 32GB de RAM , por isso, quando tento especificar 10GB de memória para a classificação usando:

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

Eu recebo:

Warning: the specifed memory size is being reduced to the available paging memory.

Input record exceeds maximum length. Specify larger maximum.

Quais são minhas opções?

    

Answer 1

Quais são minhas opções?

Tente Utilitário de classificação de linha de comando do Freeware CMSort .

Ele usa vários arquivos temporários e os mescla no final.

CMsort is reading records of an input file until the adjusted memory is reached. Then the records are sorted and written to a temporary file. This will be repeated until all records are processed. Finally, all temporary files are merged into the output file. If the available memory is sufficient, no temporary files are written and no merging is needed.

Um usuário relata um arquivo de 130.000.000 bytes.

Se você quiser ajustar algum código, também há Classificando arquivos de texto enormes - CodeProject - "Algoritmo de linhas de classificação em tamanho de arquivos de texto que excede a memória disponível"

    

Answer 2

Uma outra opção é carregar o arquivo em um banco de dados. E.G MySQL e MySQL Workbench. Os bancos de dados são candidatos perfeitos para trabalhar com arquivos grandes

Se o seu arquivo de entrada contiver apenas palavras separadas por uma nova linha, isso não deve ser difícil.

Depois de instalar o banco de dados e o MySQL Workbench, isso é o que você precisa fazer.
Primeiro, crie o esquema (isso pressupõe que as palavras não terão mais que 255 caracteres, embora você possa alterar isso aumentando o valor do argumento). A primeira coluna "idwords" é uma chave primária.

CREATE SCHEMA 'tmp' ;

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

Em segundo lugar, importe os dados: EG Isso importará todas as palavras para a tabela (essa etapa pode demorar um pouco para ser concluída. Meu conselho seria executar um teste com um arquivo de palavras pequenas primeiro e depois de ter certeza de que o formato é o mesmo que o maior (truncar) a tabela .. IE Limpe e carregue o conjunto de dados completo).

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

Esse link pode ajudar a obter o formato correto para o carregamento. link
E.G Se você precisasse pular a primeira linha, faria o seguinte.

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

Finalmente, salve o arquivo classificado. Isso pode demorar um pouco, dependendo do seu PC.

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

Você também pode pesquisar os dados à vontade como quiser. E.G Isso lhe dará as primeiras 50 palavras em ordem crescente (a partir da 0ª ou primeira palavra).

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

Boa sorte
Pete

    

Answer 3

sort

Existem muitos algoritmos usados para classificar arquivos ordenados e não ordenados ^{[ 1 ]} .
Como todos esses algoritmos já estão implementados, escolha um programa já testado.

Em coreutils (do Linux, mas também disponível para windows ^{[ 2 ]} ), existe o comando sort capaz de rodar em paralelo em processadores multi-core: geralmente é o suficiente.

Se o seu arquivo for tão grande , você pode ajudar a divisão do processamento ( split -l ), o arquivo em alguns fragmentos, possivelmente usando a opção paralela ( --parallel ) e classificando o resultado < em> ordered-chunks com a opção -m ( merge sort ).
Uma das muitas maneiras de fazer isso é explicada aqui (arquivo dividido, ordem pedaços únicos, mesclar pedaços ordenados, excluir arquivos temporários ).

Notas:

• No Windows 10, existe o chamado Windows Subsystem para Linux , no qual todo o exemplo do Linux parecerá mais natural.
• A classificação com diferentes algoritmos tem tempos de execução diferentes que são dimensionados em função do número de entradas de dados a serem classificadas (O (n ^m ), O (nlogn) ...).
• A eficiência do algoritmo depende da ordem que já está presente no arquivo original.
  (Por exemplo, um bubble sort é o algoritmo mais rápido para um arquivo já ordenado - exatamente N -, mas não é eficiente em outros casos).

Answer 4

Para oferecer uma solução alternativa para Peter H, existe um programa q que permite comandos de estilo SQL em arquivos de texto. O comando abaixo faria o mesmo (executado a partir do prompt de comando no mesmo diretório que o arquivo), sem a necessidade de instalar o SQL Workbench ou criar tabelas.

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

c1 é um atalho para a coluna 1.

Você pode excluir palavras duplicadas com

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

e envia a saída para outro arquivo

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

    

Answer 5

Você pode classificar os muitos arquivos enormes (o resultado classificado pode ser terabytes e maiores) com ZZZServer ele é gratuito para não uso comercial:

ZZZServer -sortinit -sort file1.txt
ZZZServer -sort file2.txt
ZZZServer -sort file3.txt
...
ZZZServer -sortsave sorted.txt

Após a classificação, o resultado é salvo em

sorted.txt

P.S. Seus arquivos de entrada devem ser codificados no formato UTF-8 ou ASCII!

O ZZZServer usando cerca de 1MB de RAM na classificação de arquivos grandes!

O ZZZServer usa um novo tipo de algoritmo de ordenação que pode ordenar dados com complexidade O (N).