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

25

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

Eu tentei usar o programa de classificação do Windows usando:

sort.exe input.txt /o output.txt

que fornece o erro: Não há memória principal suficiente para concluir a classificação.

Eu tenho 32 GB de RAM; portanto, quando tento especificar 10 GB de memória para o tipo usando:

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

Eu recebo:

Aviso: o tamanho da memória especificada 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 as minhas opções?

windows sorting MaYaN
fonte
2
Por favor, não cruze. Consulte A postagem cruzada de uma pergunta em vários sites do Stack Exchange é permitida se a pergunta estiver no tópico de cada site?
DavidPostill
10
Esta não é uma publicação cruzada, não sou uma máquina, portanto, postar isso e excluir o outro leva alguns minutos!
May
3
No futuro permitir que a comunidade de migrar a sua pergunta
Ramhound
4
Com o Linux, você pode aplicar esse método . Com arquivos de 100Mb, não deve ser um grande problema.
Eric Duminil
3
Qual versão do windows você está usando? O sort.exe com o antigo Windows Server 2012 R2 alega poder fazer a classificação de mesclagem externa com o uso de um arquivo temporário no disco (sem documentar um limite de tamanho). Tente usar / T para especificar um disco com 800 GB livre para o arquivo temporário. E a mensagem sobre "registro de entrada excede o tamanho máximo" parece não estar relacionada ao espaço - observe a opção / REC e considere qual é o seu terminador de linha.
Davidbak 4/03

Respostas:

16

Quais são as minhas opções?

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

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

O 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. Por fim, 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.000.000 bytes.

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

DavidPostill
fonte
26
Uau, 130 megabytes !!! +1
David Foerster
3
@DavidPostill Tem certeza de que a classificação de coreutils para Windows não é mais eficiente ( --parallelopção se você tiver mais de um núcleo ...)?
Hastur
23

Uma outra opção é carregar o arquivo em um banco de dados. EG 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 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 alterá-lo 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-o 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. https://dev.mysql.com/doc/refman/5.7/en/load-data.html
EG Se você precisou 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);

Por fim, 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 conforme desejar. Por exemplo, as 50 primeiras palavras serão exibidas em ordem crescente (a partir da 0ª ou da primeira palavra).

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

Boa sorte
Pete

Peter H
fonte
2
Esta é a resposta correta por uma margem considerável.
precisa saber é o seguinte
11
Essa abordagem será definitivamente mais flexível, especialmente se você descobrir que precisa executar novamente a classificação com uma ordem diferente, por exemplo.
churrasco
Eu não me importo com a rapidez com que sua instância do MySQL , MariaDB ou qualquer outro DBMS seja, ela não chegará nem perto do desempenho de inserção do SQLite em execução na mesma máquina. Mesmo com algo tão rápido quanto o SQLite, essa quantidade de dados é muito (e lenta) para processar (confie em mim, tentei primeiro!), Portanto, a melhor solução é classificar e remover as duplicatas primeiro e depois inserir em um banco de dados como SQLite . Portanto, embora essa solução possa ser válida para alguns casos, certamente não é para o que estou tentando fazer. Obrigado por reservar um tempo para publicá-lo de qualquer maneira.
May
Ordenação por mywordslevará uma eternidade. Mesmo com o LIMIT, levará o tempo todo, porque o MySQL terá que passar por todos os valores mywordse ordená-los. Para corrigir isso, você deve fazer o seguinte depois de fazer LOAD DATA. Adicione um índice a mywords. Agora você pode solicitar por essa coluna e não levar um milênio. E é melhor adicionar o índice após o carregamento dos dados, e não no momento em que você criou a tabela (carregamento de dados muito mais rápido).
Buttle Butkus
7

sort

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

No coreutils (do Linux, mas também disponível para Windows [ 2 ] ), existe o sortcomando capaz de executar em paralelo sob processadores com vários núcleos: geralmente é o suficiente.

Se o seu arquivo for tão grande, você poderá ajudar na divisão do processamento ( split -l), o arquivo em alguns trechos, possivelmente usando a opção paralela ( --parallel) e classificando os trechos ordenados resultantes com a -mopção ( classificação por mesclagem ).
Uma das muitas maneiras de fazer isso é explicada aqui (arquivo dividido, ordenar pedaços únicos, mesclar pedaços ordenados, excluir arquivos temporários).

Notas:

  • No Windows 10, existe o chamado Subsistema Windows para Linux, no qual todo o exemplo do Linux parecerá mais natural.
  • A classificação com algoritmos diferentes tem diferentes tempos de execução 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, uma classificação de bolha é o algoritmo mais rápido para um arquivo já solicitado - exatamente N -, mas não é eficiente em outros casos).
Hastur
fonte
2

Para oferecer uma solução alternativa ao Peter H, existe um programa q que permite comandos no estilo SQL em arquivos de texto. O comando abaixo faria o mesmo (executado no 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 envie a saída para outro arquivo

q "select distinct c1 from words.txt order by c1" > sorted.txt
Brian
fonte
Alguma idéia se isso vai lidar com um arquivo de 800 GB?
Rawling
11
Não tenho 100% de certeza - testei o acima com um arquivo de 1200 linhas (9 KB). A página de desenvolvedores tem uma página de "limitações" que não menciona nada sobre o tamanho máximo do arquivo. Um arquivo grande ainda pode se deparar com um problema de memória.
187 Brian
3
q não pode processar essa quantidade de dados lembre-se que q usa o SQLite nos bastidores, se eu não pudesse carregar os dados diretamente no SQLite, o que faz você pensar q pode?
May
2

Se as palavras em cada linha são de um vocabulário limitado (como o inglês), você pode classificar a lista em O (n + m log m) usando um TreeMap e as contagens de gravação (onde m é o número de valores únicos).

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

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

Criei um arquivo de 1,7 GB (linhas de 100 m) com 16 palavras 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, calculo que 800 GB de 16 palavras seria demore cerca de 24 horas para classificar uma thread no meu laptop i5 de 2,3 GHz com SSD.

Dave Moten
fonte