Comment trier les gros fichiers?

35

J'ai un PC équipé d'un processeur Intel (R) Pentium (CPU) G640 à 2,80 GHz et de 8 Go de RAM. J'utilise Scientific Linux 6.5 avec le système de fichiers EXT3.

Sur cette configuration, quel est le moyen le plus rapide de créer sort -uun fichier de 200 gigaoctets?

Dois-je diviser le fichier en fichiers plus petits (moins de 8 Go), sort -ules assembler, puis les diviser à nouveau dans une taille différente sort -u, etc.? Ou existe-t-il des scripts de tri, des programmes capables de gérer des fichiers aussi gros avec ma quantité limitée de RAM?

evachristine
la source
6
S'il vous plaît modifier votre question et expliquer ce qui se passe lorsque vous essayez la commande que vous avez affichée. Êtes-vous à court d'espace disque? La commande devrait fonctionner aussi longtemps que vous avez suffisamment d’espace libre /tmp.
terdon
1
La réponse choisie dit en gros ce que @terdon dit, mais vérifiez aussi celui-ci - stackoverflow.com/a/13025731/2801913 . Vous aurez besoin de GNU parallelpour cela, je pense, plutôt que de moreutils parallelqui est installé par défaut sur certains systèmes.
Graeme
1
Vous pouvez télécharger le fichier sur Amazon S3, puis lancer un travail Elastic Map Reduce avec quelques centaines de nœuds pour le trier!
Alan Shutko
2
sort(1)pourrait manquer d'espace sur /tmp; Si tel est le cas, vous pouvez désigner une autre zone pour les fichiers temporaires avec la variable d'environnement TMPDIR, ou -T=<tmpdir>
signaler

Réponses:

46

GNU sort(qui est la valeur par défaut sur la plupart des systèmes Linux) a une --paralleloption. De http://www.gnu.org/software/coreutils/manual/html_node/sort-invocation.html :

'--parallel = n'

Définissez le nombre de tris en parallèle sur n. Par défaut, n est défini sur le nombre de processeurs disponibles, mais il est limité à 8, car les gains de performance diminuent par la suite. Notez également que l'utilisation de n threads augmente l'utilisation de la mémoire d'un facteur de log n. Voir aussi invocation nproc.

Puisque votre cpu a 2 cœurs, vous pourriez faire:

sort --parallel=2 -uo list-sorted.txt list.txt

Il est préférable de spécifier le nombre réel de cœurs car cela peut sembler être davantage dû au fait que le processeur possède un hyper-threading .

Vous pouvez également essayer niced’influencer la priorité d’ordonnancement du processeur et ioniced’ordonnancement des E / S. Vous pouvez augmenter la priorité par rapport à d'autres processus tels que celui-ci. Je ne pense pas que cela vous permettra de réaliser d'importantes économies car ils sont généralement mieux adaptés pour garantir qu'un processus d'arrière-plan n'utilise pas trop de ressources. Néanmoins, vous pouvez les combiner avec quelque chose comme:

nice -n -20 ionice -c2 -n7 sort --parallel=2 -uo list-sorted.txt list.txt

Notez également que, comme l'a commenté Gilles , l'utilisation d'une seule commande de tri GNU sera plus rapide que toute autre méthode permettant de décomposer le tri car l'algorithme est déjà optimisé pour gérer des fichiers volumineux. Tout le reste va probablement ralentir les choses.

Graeme
la source
10
Et vous devriez noter que téléphoner sortdirectement est mieux que tout ce que vous pourriez bricoler. Le tri GNU est conçu pour bien gérer les fichiers beaucoup plus volumineux que la RAM.
Gilles 'SO- arrête d'être méchant'
L'option de tri --parallel ne fonctionne pas sur mes serveurs RH6.5. Sort --version pense que cela vient de Coreutils 8.4. De quelle version ai-je besoin de la version parallèle?
markus_b
3
Voir aussi superuser.com/questions/938558/sort-parallel-isnt-parallelizing - vous devrez peut-être spécifier un paramètre tel que -S512M si vous remarquez qu'il ne s'agit pas d'une parallélisation.
Unhammer
46

L'utilisation de la sortcommande sera probablement l'option la plus rapide.

Mais vous voudrez probablement fixer les paramètres régionaux à C.

sort -une rapporte pas de lignes uniques, mais une de chaque série de lignes qui trient de la même manière. Dans les paramètres régionaux C, deux lignes différentes ne trient pas nécessairement de la même façon, mais ce n'est pas le cas dans la plupart des paramètres régionaux basés sur UTF-8 sur les systèmes GNU.

De plus, l'utilisation de la locale C évite les coûts supplémentaires liés à l'analyse du format UTF-8 et au traitement des ordres de tri complexes, ce qui améliorerait considérablement les performances.

Alors:

LC_ALL=C sort -u file

Vous pouvez également améliorer les performances en utilisant un lecteur plus rapide (ou un lecteur différent de celui où se trouvent les fichiers d'entrée et / ou de sortie) des fichiers temporaires (à l'aide de -Tou$TMPDIR variable d'environnement), ou en jouant avec l' -Soption prise en charge par certainssort implémentations) .

Pour certains types d'entrée ou pour un stockage lent, l'utilisation de l' --compress-programoption GNU sort(avec, par exemple lzop) peut améliorer les performances en plus de l'utilisation du stockage.


Maintenant, juste une note pour ceux qui objectent (à juste titre dans une certaine mesure) que ce ne sera pas le bon ordre :

Je conviens qu'en tant qu'être humain, j'aimerais voir Stéphane faire le tri entre Stefan et Stéphanie , mais:

  • Un ordinateur voudrait que Stéphane trie après é(au moins sous la forme U + 00E9) sous forme de caractère ou que les octets de son codage UTF-8 soient triés après (en termes de nombre de points ou de points de code). C'est un ordre de tri très simple à mettre en œuvre, un ordre total strict et sans surprise.
  • L'ordre de tri de vos paramètres régionaux ne sera probablement pas satisfaisant dans de nombreux cas, même pour un humain. Par exemple, sur mon système avec les paramètres régionaux en_GB.utf8 par défaut:

    • Stéphane et Stéphane (l'un avec U + 00E9, l'autre avec eU + 0301) ne font pas le même tri:

      $ printf '%b\n' 'Ste\u0301phane' 'St\u00e9phane' | sort -u
      Stéphane
      Stéphane
      
    • mais ③, ①, ② sont tous identiques (il s'agit évidemment d'un bogue dans ces définitions de paramètres régionaux):

      $ printf '%s\n' ③ ① ② | sort -u
      ③
      

      Ici, c'est, mais ça aurait tout aussi bien pu être ou

Donc, IMO, il y a de fortes chances que vous souhaitiez toujours utiliser sort -uLC_ALL = C si vous voulez des lignes uniques. Et si vous souhaitez que la liste résultante soit triée dans l'ordre de tri de l'utilisateur, redirigez-la à sortnouveau:

LC_ALL=C sort -u | sort

LC_ALL=C sort | LC_ALL=C uniq -c | sort -k2
Stéphane Chazelas
la source
8
+1 pour la localisation: cela peut avoir un impact énorme sur les performances
Adrian Pronk
1
Oui. triant le fichier avec 250000 lignes le LC_ALL accélère les choses 8 fois.
Jan Vlcinsky
-1

Voici un script bash prêt à l’emploi permettant de trier les données d’échelle TB sur une machine standard avec quelques Go de mémoire vive: http://sgolconda.blogspot.com/2015/11/sort-very-large-dataset.html Il vérifie le nombre de Noyaux de votre machine comme et utilise tous les noyaux. Peut trier, fichiers numériques ou chaînes. Peut être utilisé pour trouver des enregistrements uniques dans les données d’échelle TB.

utilisateur213743
la source
Ce n'est pas une bonne suggestion. Le script est extrêmement gonflé et divise le fichier d'entrée pour trier les parties pour lesquelles la réponse acceptée indique que ce n'est pas nécessaire avec le tri GNU.
Thorbjørn Ravn Andersen