Le moyen le plus rapide pour supprimer les duplicates dans la grande list de mots?

J'ai besoin de dédupliquer une grande list de mots. J'ai essayé plusieurs commands et fait des searchs ici et ici où ils expliquent que le moyen le plus rapide de dédupliquer une list de mots semble être awk.

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

Cependant, j'ai trouvé que cela semble être faux. Voici mes résultats de test:

sort -u input.txt -o output.txt 

réel 0m12.446s
user 0m11.347s
sys 0m0.906s

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

réel 0m47.221s
user 0m45.419s
sys 0m1.260s

Donc utiliser le sorting -u est 3,7 fois plus rapide. Pourquoi est-ce? Existe-t-il une méthode encore plus rapide pour la déduplication?

*********** Mettre à jour ********

Comme quelqu'un l'a souligné dans les commentaires, il se pourrait que ma list de mots ait déjà été sortingée dans une certaine mesure. Pour exclure cette possibilité, j'ai généré deux lists de mots en utilisant ce script python .

List1 = 7 Mo
List2 = 690 Mb

Résultats AWK:
List1
réel 0m1.643s
user 0m1.565s
sys 0m0.062s

List2
réel 2m6.918s
user 2m4.499s
sys 0m1.345s

Résultats TRIER:
List1
réel 0m0.724s
user 0m0.666s
sys 0m0.048s

List2
réel 1m27.254s
user 1m25.013s
sys 0m1.251s

Vous posez la mauvaise question ou posez la question à tort et dans la mauvaise stack, c'est une meilleure question à poser dans la programmation / stack-overflow pour que les gens vous donnent des réponses basées sur les algorithms utilisés dans awk et sorting.

PS: fais aussi le nécessaire avec nawk, mawk et gawk pour nous donner plus de détails pour "zone into";) et fais les runs comme un 100 fois chacun avec les min, max, avg et écart-type.

Tout cas de return à la question à scope de main, de CompSci 210, il s'agit des algorithms utilisés. Sort en utilise plusieurs, en fonction des tailles et des contraintes de memory pour sauvegarder les files sur le disque dans des files temporaires à merge, une fois qu'il manque de memory, et vous devrez regarder dans le code source pour voir ce que la command spécifique de sorting (1) utilise le operating system spécifique sur lequel vous l'exécutez, mais de l'expérience, elle charge en memory autant que possible, effectue un sorting rapide sur le disque, écrit sur le disque, répète le rinçage et fin, il fera une sorte de fusion des petits files sortingés. Vous avez donc ici O (n * log2 (N)) pour les parties, puis une opération de fusion approximative O (n * log (n))

awk: Le mécanisme x [$ 0] ++ est "suppose" d'utiliser le hachage. MAIS le problème avec le hachage, une opération de "search" supposée O (1), est les collisions et la gestion des collisions. Cela peut causer un problème lorsque datatables ne sont pas bien réparties, ni remplir les compartiments, etc. et dans les grandes lists, le hachage peut être un gros problème de memory si la manipulation des collisions n'est pas effectuée correctement ajuster les algorithms de hachage pour datatables attendues), puis vous devez regarder la performance des fonctions de hachage réelles et ensuite O (1) peut être plus proche d'un O (log (n)) pour les inserts (c'est-à-dire O (1) pour la première search, et si elle n'existe pas, ajoutez-la qui pourrait être O (log (n))), et alors le n * O (1) devient un * O (log (n)) = > O (n * log (n)), sans oublier que vous faites aussi des choses de manière "interprétée" 🙂

La différence de vitesse est due au fait que 'sort' est une command ( lien ), alors que 'awk' est un langage de programmation ( lien ).

la command 'sort' prend l'input et renvoie la sortie. Alors que 'awk' est un langage de programmation, qui interprète d'abord le code (command du terminal), puis commence à traiter dessus. Aussi simple que cela.