☰

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

tag-icon • tag-icon windows sorting
Classifique o conteúdo de um arquivo de texto extremamente grande (800 GB) no Windows

eu tenho umtextoarquivo com uma palavra em cada linha, o tamanho do arquivo é 800 GB. Preciso classificar as palavras em ordem alfabética.

Eu tentei usar ojanelas organizarprograma usando:

sort.exe input.txt /o output.txt

o que dá o erro:Memória principal insuficiente para concluir a classificação.

Eu tenho 32 GB deBATERentão, quando tento especificar 10 GB de memória para a classificação usando:

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

Eu recebo:

Aviso: o tamanho da memória especificado está sendo reduzido para a memória de paginação disponível.

O registro de entrada excede o comprimento máximo. Especifique um máximo maior.

Quais são minhas opções?

Responder1

Quais são minhas opções?

TentarUtilitário de classificação de linha de comando freeware CMSort.

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

CMsort está lendo registros de um arquivo de entrada até que a memória ajustada seja atingida. Em seguida, os registros são classificados e gravados em um arquivo temporário. Isso será repetido até que todos os registros sejam processados. Finalmente, todos os arquivos temporários são mesclados no arquivo de saída. Se a memória disponível for suficiente, nenhum arquivo temporário será gravado e nenhuma mesclagem será necessária.

Um usuário relata que classificou um arquivo de 130 milhões de bytes.

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

Responder2

Uma outra opção é carregar o arquivo em um banco de dados. Por exemplo, 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 deverá ser muito difícil.

Depois de instalar o banco de dados e o MySQL Workbench, é isso que você precisa fazer.

Primeiro, crie o esquema (isso pressupõe que as palavras não terão mais de 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.
Por exemplo, isto importará todas as palavras para a tabela; esta etapa pode demorar um pouco para ser concluída. Meu conselho seria executar primeiro um teste com um arquivo menor e quando você tiver certeza de que o formato é igual ao maior (truncar a tabela... ou seja, limpá-la e carregar o conjunto de dados completo).

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

Este link pode ajudar a obter o formato correto para o carregamento. https://dev.mysql.com/doc/refman/5.7/en/load-data.html

Por exemplo, 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 desejar.
Por exemplo, isso lhe dará as primeiras 50 palavras em ordem crescente (começando na posição zero ou na primeira palavra).

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

Responder3

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.

Emcoreutils (no Linux, mas disponível também para Windows [2] ), existe um sortcomando capaz de rodar em paralelo em processadores multi-core: normalmente é suficiente.

Se o seu arquivo fortão grandevocê pode ajudar no processamento dividindo ( split -l), o arquivo em alguns pedaços, possivelmente usando a opção paralela ( --parallel), e classificando o resultadopedaços ordenadoscom a -mopção (classificação por mesclagem).
Uma das muitas maneiras de fazer isso é explicadaaqui(dividir arquivo, ordenar pedaços únicos, mesclar pedaços ordenados, excluir arquivos temporários).

Notas:

  • No Windows 10 existe o chamadoSubsistema Windows para Linuxem que todo o exemplo do Linux parecerá mais natural.
  • A classificação com diferentes algoritmos possui diferentes tempos de execução que são escalonados 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 umTipo de bolhaé o algoritmo mais rápido para um arquivo já ordenado -- exatamente N --, mas não é eficiente em outros casos).

Responder4

Se as palavras em cada linha forem de um vocabulário limitado (como inglês), você poderá classificar a lista em tempo O (n + m log m) usando um TreeMap e registrando contagens (onde m é o número de valores exclusivos).

Caso contrário, você pode usar a biblioteca javagrande classificador. Ele divide a entrada em arquivos intermediários classificados e os mescla de forma eficiente (O (nlogn) geral). Para classificar seu arquivo fica assim:

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

Eu criei um arquivo de 1,7 GB (100 milhões de linhas) com palavras de 16 caracteres geradas aleatoriamente e classifiquei-o como acima em 142s e com base na complexidade computacional O (n log n) do método que estou usando, estimo que 800 GB de palavras de 16 caracteres seriam demoro cerca de 24 horas para classificar o thread único no meu laptop i5 de 2,3 GHz com SSD.

informação relacionada