A maneira mais rápida de excluir duplicatas em uma grande lista de palavras?

14

Eu preciso deduplicar uma lista de palavras grande. Tentei vários comandos e fiz algumas pesquisas aqui e aqui, onde explicam que a maneira mais rápida de desduplicar uma lista de palavras parece estar usando o awk.

awk -> O (n)? ordenar -> O (n log n)?

No entanto, descobri que isso parece não ser verdade. Aqui estão meus resultados de teste:

sort -u input.txt -o output.txt 


usuário 0m12.446s real 0m11.347s
sys 0m0.906s

awk '!x[$0]++' input.txt > output.txt


usuário 0m47.221s real 0m45.419s
sys 0m1.260s

Portanto, usar sort -u é 3,7 vezes mais rápido. Por que é isso? existe um método ainda mais rápido para desduplicar?

*********** Atualização ********

Como alguém apontou nos comentários, pode ser que minha lista de palavras já tenha sido classificada até certo ponto. Para excluir essa possibilidade, gerei duas listas de palavras usando esse script python .

Lista1 = 7 Mb
Lista2 = 690 Mb

Resultados awk:
Lista1
reais 0m1.643s
usuário 0m1.565s
sys 0m0.062s

List2
real 2m6.918s
usuário 2m4.499s
sys 0m1.345s

ORDEM de resultados:
List1
real 0m0.724s
usuário 0m0.666s
sys 0m0.048s

List2
real 1m27.254s
usuário 1m25.013s
sys 0m1.251s

karlpy
fonte
Será que seus dados de entrada já estão classificados?
iruvar 27/08/2015
I vai gerar uma lista aleatória com números e verificar apenas para se certificar
karlpy
2
A notação Big O é sobre o que acontece quando o comprimento da entrada se aproxima do infinito: indica que um algoritmo é escalonado com grande entrada. Alguns algoritmos funcionam melhor em tamanho de entrada pequeno.
Ctrl-alt-delor 27/08/15
1
Karlpy, em que ordem você executou, despertou primeiro ou classificou? Isso pode fazer a diferença devido ao cache de arquivos
Iruvar
1
@karlpy: "Alterei o nome do arquivo ..." Se você quer dizer que renomeou o arquivo, isso não é suficiente. Renomear um arquivo apenas associa um novo nome ao inode antigo, que ainda aponta para os mesmos blocos de dados antigos. Se eles foram armazenados em cache, ainda estão em cache. ISTM que uma técnica muito melhor seria a de (1) fazer uma cópia do arquivo e, em seguida, (2) executar um comando em um arquivo e (3) executar outro comando no outro arquivo.
Scott

Respostas:

3

Você está fazendo a pergunta errada, ou a pergunta incorretamente e na pilha errada. Essa é uma pergunta melhor a ser feita na programação / estouro de pilha para as pessoas fornecerem respostas com base nos algoritmos usados ​​no awk and sort.

PS: faça também o necessário com nawk, mawk e gawk para nos dar mais detalhes para "entrar em zona";) e faça as execuções 100 vezes cada uma com os desvios mínimo, máximo, médio e médio.

Qualquer que seja o caso da questão em questão, do CompSci 210, trata-se dos algoritmos usados. A classificação utiliza várias, dependendo dos tamanhos e restrições de memória encontradas para salvar arquivos em disco em arquivos temporários para serem mesclados depois que a memória acabar, e você terá que procurar no código-fonte para ver o que o comando sort específico (1) usa no SO específico em que o está executando, mas, por experiência, ele está carregando na memória o máximo possível, faça uma ordenação rápida, grave no disco, enxágüe a repetição e, em seguida, final, ele fará uma mesclagem dos pequenos arquivos classificados. Então, aqui você terá o O (n * log2 (N)) para as peças e, em seguida, uma operação aproximada de O (n * log (n))

awk: O mecanismo x [$ 0] ++ é "suposto" usar hash. MAS o problema do hash, uma suposta operação de "pesquisa" de O (1), são colisões e o manuseio de colisões. Isso pode causar um problema quando os dados não são bem distribuídos, nem encher os baldes etc., e em listas grandes, o hash pode ser um grande problema de memória se o manuseio das colisões não for feito corretamente (e você pode precisar ajuste os algoritmos de hash para os dados esperados) e, em seguida, você precisará observar o desempenho das funções de hash reais e, em seguida, o O (1) poderá estar mais próximo de um O (log (n)) para as inserções (ou seja, O (1) para a primeira pesquisa, e se NÃO existir, adicione-o que pode ser O (log (n))) e que então n * O (1) se torne um * O (log (n)) = > O (n * log (n)), sem mencionar que você também está fazendo as coisas de maneira "interpretada" :)

Hvisage
fonte
-2

A diferença de velocidade é porque 'sort' é um comando ( link ), enquanto 'awk' é uma linguagem de programação ( link ).

O comando 'sort' é recebe e retorna a saída. Enquanto 'awk' é uma linguagem de programação, que primeiro interpreta o código (comando terminal) e depois inicia o processamento nele. Simples assim.

Zuhayer
fonte