J'ai un gros fichier texte (1,5 G),
Je veux savoir quel est l'outil le plus rapide et le plus fiable de Linux.
J'utilise habituellement:
awk '!x[$0]++' file.txt
Mais lorsque j'utilise la htop
commande, je constate que mon utilisation de la mémoire augmente.
Je veux savoir quel est le plus rapide et le plus fiable pour les fichiers volumineux.
uniq?
sort?
sed?
awk?
Pourquoi?
time
?Réponses:
Voyons comment fonctionne chaque solution.
uniq
Cela nécessite que le fichier soit déjà trié. Sinon, vous devez d'abord le dirigersort
, ce qui signifie que vous devezsort
lire le fichier entier en mémoire, le réorganiser (O(n log n)
), puis l'écrire dans le tuyau. Le travail deuniq
est très bon marché, car il n'a qu'à comparer les lignes adjacentes de son entrée.sort -u
Cela combine le travail desort | uniq
. Cela doit collecter toutes les entrées uniques en mémoire comme leawk
fait le script, mais cela gaspille également du temps à les trier avant de produire la sortie. C'estO(n log n)
, bien que dans ce cas,n
c'est le nombre d'éléments uniques, pas toutes les entrées. C'est donc mieux que la pipe.sed
Je ne sais pas pourquoi vous avez énuméré cela, car je ne vois pas du tout de bonne façon de le fairesed
. Peut-être que si vous le triez d'abord et que vous dirigez vers unsed
script, il existe un moyen de comparer les lignes adjacentes. Ilsed
s'agirait donc simplement de faire ce quiuniq
fait, et le faituniq
probablement aussi efficacement que possible.awk
C'est probablement le meilleur car il ne fait que la quantité minimale de travail nécessaire. En lisant chaque ligne, il effectue une recherche de hachage efficace pour voir si la ligne est déjà dans sa mémoire et ne stocke que les lignes uniques sous forme de clés de hachage et un compteur comme valeur. (Si la ligne n'était pas présente auparavant, la condition sera vraie, donc la ligne sera imprimée. Sinon, elle ne le sera pas.) Cela utilise leO(n)
temps et laO(uniq n)
mémoire.Chaque méthode utilisera une quantité considérable de mémoire, soit pour trier les entrées, soit pour garder une trace des entrées qui ont été vues afin de pouvoir supprimer les doublons.
la source
awk
explique également pourquoi il utilise des quantités croissantes de mémoire. Tout ce qui fait un tri finira également par le faire, seulement 1) il l'utilisera probablement tout à la fois, 2) il peut en utiliser un peu plus, selon le nombre de clés uniques par rapport aux clés dupliquées.sort
recourt à des fichiers temporaires (de manière intelligente) pour éviter de remplir la mémoire. Son utilisation de la mémoire est liée. La frontière est personnalisable avec certaines implémentations de tri. Il est plus efficace que de laisser le système échanger de la mémoire au hasard sur le disque (ce qui affecte également les applications sur le système).awk
mémoire est insuffisante, celasort
peut être la seule solution car il a été conçu pour y faire face. D'un autre côté, tout ce que la lecture et l'écriture sur le disque ralentira, donc cela prendra probablement beaucoup de temps. Si vous traitez de telles quantités de données, vous devriez probablement utiliser un SGBD plutôt que des fichiers texte.O(n log n)
? Ou tout simplement vous le savez d'ailleurs?J'ai trouvé que le tri semble être l'outil uniq le plus rapide comme indiqué ici -> Le moyen le plus rapide de supprimer les doublons dans une grande liste de mots?
la source
Je voulais juste souligner que le gnu
uniq
semble terriblement lent, même sur une liste triée.J'ai juste essayé d'obtenir une liste de préfixes de répertoire à partir d'une liste de noms de fichiers triés:
sort -u semble deux fois plus rapide que uniq, et c'est avec la lecture de tri depuis stdin et l'écriture vers stdout, donc je ne le vois pas encore faire de parallélisation. Je ne sais pas pourquoi uniq devrait être tellement plus lent que le tri, car il n'a pas à trier la liste ...
La sortie de cette commande est très petite (il y a beaucoup de doublons), seulement 264 ko et le tri se termine instantanément après que pv soit fait.
Les mêmes vitesses restent si vous inversez l'ordre des commandes, mon flux est limité par le temps de processeur ici, pas l'accès au disque et les caches (je n'ai que 8 Go de RAM et mon swap n'est pas utilisé)
J'exécute ceci sur une machine fedora 31 avec gnu coreutils sort et uniq et gnu awk; les paramètres régionaux sont définis sur en_US.UTF-8
MISE À JOUR , étant donné que cela m'a un peu intrigué, j'ai fait d'autres tests, supprimons la partie coupée et assurez-vous que le fichier est bien trié
cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test
Cela prend 8,4 minutes. le test fait maintenant 7,9 Go
exécutons ces outils sur le fichier plutôt que dans un tube, cela permettra à ces outils de faire un peu plus d'optimisation, comme le tri sera multi-thread. et aussi d'un ssd plus rapide.
Vous ne remarquerez peut-être pas que le tri prend également beaucoup de mémoire, car il fait des astuces intelligentes avec les fichiers temporaires dans / tmp qui pourraient être tmpfs et seront dans votre RAM (essayez de trier un fichier plus grand que / tmp, vous courrez dans l'espace problèmes, c'est pourquoi j'ai besoin du drapeau -T. dans la commande ci-dessus)
Il semble donc que votre solution awk soit la plus rapide de ces 3 et utilise en fait le moins de mémoire
update2 et maintenant avec une locale plus simple
Cette fois, uniq gagne la course ... comme le laisse entendre Stéphane Chazelas dans les commentaires, définir votre locale sur C accélère le tri et uniq tout un tas!
la source
sort
etuniq
? Quel lieu?