A maneira mais rápida de apagar duplicatas em grandes listas de palavras?

Question

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

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

No entanto, descobri que isso parece não ser verdade. Aqui estão os resultados dos meus testes:

sort -u input.txt -o output.txt 

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

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

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

Então, usando sort -u é 3,7 vezes mais rápido. Por que é isso? Existe um método ainda mais rápido para fazer deduplicação?

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

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

List1 = 7 Mb
List2 = 690 Mb

Resultados AWK:
List1
real 0m1.643s
usuário 0m1.565s
sys 0m0.062s

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

Resultados SORT:
Lista1
0m0.724s real
usuário 0m0.666s
sys 0m0.048s

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

    

Answer 1

Você está fazendo a pergunta errada, ou fazendo a pergunta errada e na pilha errada, esta é uma pergunta melhor para perguntar na programação / estouro de pilha para as pessoas darem respostas baseadas nos algoritmos usados dentro do awk e do tipo .

PS: também faça o necessário com nawk, mawk e gawk para nos dar mais detalhes para "zone into";) e faça as execuções como 100 vezes cada com o min, max, avg e desvio padrão.

Qualquer caso de volta para a questão em questão, do CompSci 210, é sobre os algoritmos usados. Sort faz uso de vários, dependendo dos tamanhos, e restrições de memória para salvar arquivos no disco em arquivos temporários para serem mesclados, uma vez que ele ficou sem memória, e você terá que olhar para o código-fonte para ver o que o comando específico sort (1) usa no SO específico em que você está rodando, mas por experiência ele está carregando na memória o máximo que pode, faz algum tipo de classificação rápida, grava no disco, limpa a repetição e No final, ele fará uma mesclagem dos pequenos arquivos classificados. Então aqui você terá o O (n * log2 (N)) para as partes, e então uma operação de mesclagem O (n * log (n)) aproximada

awk: O mecanismo x [$ 0] ++ é "suponha" usar hashing. Mas o problema com hashing, uma suposta operação de "lookup" de O (1), são colisões e o tratamento de colisões. Isso pode causar um problema quando os dados não são bem distribuídos, nem o preenchimento dos buckets, etc., e em listas grandes, o hash pode ser um grande problema de memória se o tratamento das colisões não for feito corretamente (e talvez seja necessário ajustar os algoritmos de hash para os dados esperados), e então você precisa olhar para o desempenho das funções de hashing reais e então o O (1) pode estar mais perto de um O (log (n)) para as inserções (Ie O (1) para a primeira pesquisa, e se ela não existir, você a adiciona, que pode ser O (log (n))), e então o n * O (1) se torna um * O (log (n)) = > O (n * log (n)), para não mencionar que você também está fazendo as coisas de uma maneira "interpretada":)

    

Answer 2

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

O comando

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