Le moyen le plus rapide de supprimer les doublons dans une grande liste de mots?

14

J'ai besoin de dédupliquer une grande liste de mots. J'ai essayé plusieurs commandes et fait des recherches ici et ici où elles expliquent que le moyen le plus rapide de dédupliquer une liste de mots semble utiliser awk.

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

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

sort -u input.txt -o output.txt 

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

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

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

L'utilisation de sort -u est donc 3,7 fois plus rapide. Pourquoi est-ce? existe-t-il une méthode encore plus rapide pour effectuer la déduplication?

*********** Mise à jour ********

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

Liste1 = 7 Mo
Liste2 = 690 Mo

Résultats AWK:
Liste1
réels 0m1.643s
utilisateur 0m1.565s
les 0m0.062s de

List2
réels 2m6.918s
2m4.499s utilisateur
de 0m1.345s de

Trier par :
Liste1
réels 0m0.724s
utilisateur 0m0.666s
0m0.048s sys

List2
réels 1m27.254s
1m25.013s utilisateur
de 0m1.251s de

karlpy
la source
Se pourrait-il que vos données d'entrée soient déjà triées?
iruvar
Je vais générer une liste aléatoire avec des nombres et vérifier juste pour m'assurer
karlpy
2
La notation Big O concerne ce qui se passe lorsque la longueur d'entrée approche de l'infini: elle vous indique qu'un algorithme évolue avec une grande entrée. Certains algorithmes fonctionnent mieux avec une petite taille d'entrée.
ctrl-alt-delor
1
Karlpy, dans quel ordre avez-vous exécuté, awk en premier ou tri? Cela peut faire une différence en raison de la mise en cache des fichiers
iruvar
1
@karlpy: "J'ai changé le nom du fichier ..." Si vous voulez dire que vous avez renommé le fichier, ce n'est pas suffisant. Renommer un fichier associe simplement un nouveau nom à l'ancien inode, qui pointe toujours vers les mêmes anciens blocs de données. S'ils ont été mis en cache, ils sont toujours mis en cache. ISTM qu'une meilleure technique serait (1) de faire une copie du fichier, puis (2) d'exécuter une commande sur un fichier et (3) d'exécuter l'autre commande sur l'autre fichier.
Scott

Réponses:

3

Vous posez la mauvaise question, ou posez la question à tort et dans la mauvaise pile, c'est une meilleure question à poser dans la programmation / débordement de pile pour que les gens vous donnent des réponses basées sur les algorithmes utilisés dans awk et sort.

PS: faites également le nécessaire avec nawk, mawk et gawk pour nous donner plus de détails sur la "zone dans";) et faites les courses comme 100 fois chacune avec les écarts min, max, avg et standard.

Dans tous les cas, revenons à la question posée, de CompSci 210, il s'agit des algorithmes utilisés. Trier utilise plusieurs, selon les tailles et les contraintes de mémoire qu'il a rencontrées pour enregistrer les fichiers sur le disque dans des fichiers temporaires à fusionner une fois qu'il n'a plus de mémoire, et vous devrez regarder dans le code source pour voir ce que la commande sort (1) spécifique utilise sur le système d'exploitation spécifique sur lequel vous l'exécutez, mais d'après l'expérience, elle se charge autant que possible en mémoire, effectuez un tri rapide dessus, écrivez sur le disque, répétez le rinçage et fin, il fera une fusion-tri des petits fichiers triés. Vous aurez donc ici l'O (n * log2 (N)) pour les pièces, puis une opération de fusion approximative O (n * log (n))

awk: Le mécanisme x [$ 0] ++ est "supposé" utiliser le hachage. MAIS le problème avec le hachage, une opération supposée de "recherche" O (1), ce sont les collisions et la gestion des collisions. Cela peut provoquer un problème lorsque les données ne sont pas bien réparties, ni remplir les compartiments, etc. et dans les grandes listes, le hachage peut être un gros problème de mémoire si la gestion des collisions n'est pas effectuée correctement (et vous devrez peut-être régler les algorithmes de hachage pour les données attendues), puis vous devez examiner les performances des fonctions de hachage réelles, puis le O (1) pourrait être plus proche d'un O (log (n)) pour les insertions (Ie. O (1) pour la première recherche, et s'il n'existe PAS vous l'ajoutez qui pourrait être O (log (n))), et que alors le n * O (1) devienne un * O (log (n)) = > O (n * log (n)), sans oublier que vous faites aussi les choses de manière "interprétée" :)

Hvisage
la source
-2

La différence de vitesse est due au fait que «sort» est une commande ( lien ), tandis que «awk» est un langage de programmation ( lien ).

La commande 'sort' prend les entrées et les sorties de retour. Alors que 'awk' est un langage de programmation, qui interprète d'abord le code (commande de terminal) puis commence le traitement dessus. Aussi simple que cela.

Zuhayer
la source