L'outil `uniq` le plus rapide de linux

8

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 htopcommande, 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?

MLSC
la source
Avez-vous essayé de les exécuter, éventuellement avec time?
choroba
le temps est important ainsi que l'utilisation et la fiabilité de la mémoire (je veux dire lequel fait son travail avec précision)
MLSC
Pas encore ... Mais j'ai fait quelques tests avant ... et demande quelque part, certains gars m'ont dit que awk est le meilleur ... mais dans htop ... Je vois que l'utilisation de la mémoire augmente
MLSC
3
@MortezaLSC: C'est un compromis. Plus le programme est rapide, plus la mémoire est utilisée.
cuonglm

Réponses:

16

Voyons comment fonctionne chaque solution.

  • uniqCela nécessite que le fichier soit déjà trié. Sinon, vous devez d'abord le diriger sort, ce qui signifie que vous devez sortlire le fichier entier en mémoire, le réorganiser ( O(n log n)), puis l'écrire dans le tuyau. Le travail de uniqest très bon marché, car il n'a qu'à comparer les lignes adjacentes de son entrée.

  • sort -uCela combine le travail de sort | uniq. Cela doit collecter toutes les entrées uniques en mémoire comme le awkfait le script, mais cela gaspille également du temps à les trier avant de produire la sortie. C'est O(n log n), bien que dans ce cas, nc'est le nombre d'éléments uniques, pas toutes les entrées. C'est donc mieux que la pipe.

  • sedJe ne sais pas pourquoi vous avez énuméré cela, car je ne vois pas du tout de bonne façon de le faire sed. Peut-être que si vous le triez d'abord et que vous dirigez vers un sedscript, il existe un moyen de comparer les lignes adjacentes. Il seds'agirait donc simplement de faire ce qui uniqfait, et le fait uniqprobablement aussi efficacement que possible.

  • awkC'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 le O(n)temps et la O(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.

Barmar
la source
1
+1 L'explication concernant awkexplique é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.
goldilocks
@Barmar pardon, Mais quand j'ai un gros fichier (16 G) avec une capacité de mémoire 8G, alors que va-t-il se passer avec ma mémoire?
MLSC
8
@goldilocks, sortrecourt à 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).
Stéphane Chazelas
C'est vrai. Donc, si vous rencontrez un cas où la awkmémoire est insuffisante, cela sortpeut ê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.
Barmar
@Barmar Comment avez-vous déduit que le temps de réorganisation augmente O(n log n)? Ou tout simplement vous le savez d'ailleurs?
jimmij
0

Je voulais juste souligner que le gnu uniqsemble 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:

$ pv all_files | cut -d '/' -f 1,2,3,4 | uniq > all_prefixes

36.7GiB 0:07:41 [81.4MiB/s]

$ pv all_files | cut -d '/' -f 1,2,3,4 | sort -u > all_prefixes2

36.7GiB 0:03:14 [ 193MiB/s]

$ pv all_files  | cut -d '/' -f 1,2,3,4 | awk '!x[$0]++' > all_prefixes3                                        
36.7GiB 0:02:18 [ 270MiB/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)

$ time sort -u test > /dev/null
339.24user 3.54system 1:28.87elapsed 385%CPU (0avgtext+0avgdata 2365856maxresident)k
9555544inputs+0outputs (0major+591298minor)pagefaults 0swaps

$ time awk '!x[$0]++' test > /dev/null                                                                                                                             
51.15user 1.55system 0:52.94elapsed 99%CPU (0avgtext+0avgdata 10976maxresident)k
0inputs+0outputs (0major+1923minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                  
421.89user 2.76system 7:06.63elapsed 99%CPU (0avgtext+0avgdata 1980maxresident)k
52712inputs+0outputs (0major+79minor)pagefaults 0swaps

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

$ export LC_ALL=c
$ time sort -u test > /dev/null                                                                                                                                             1.2m ? Tue Apr 21 17:09:22 2020
119.18user 3.64system 0:38.24elapsed 321%CPU (0avgtext+0avgdata 2013472maxresident)k

$ time awk '!x[$0]++' test > /dev/null                                                                                                                                1161ms ? Tue Apr 21 17:07:31 2020
67.23user 2.50system 1:10.16elapsed 99%CPU (0avgtext+0avgdata 10480maxresident)k
7187520inputs+0outputs (0major+1912minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                               
22.05user 2.02system 0:24.24elapsed 99%CPU (0avgtext+0avgdata 1488maxresident)k
2959648inputs+0outputs (1major+72minor)pagefaults 0swaps

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!

Jens Timmerman
la source
Quelle implémentation de sortet uniq? Quel lieu?
Stéphane Chazelas