J'ai un fichier texte de 500 Go avec environ 10 lignes de milliards à trier dans l'ordre alphabétique. Quel est le meilleur algorithme à utiliser? Mon implémentation et ma configuration peuvent-elles être améliorées?
Pour l'instant, j'utilise la commande CARUETILS TRY: P>
LANG=C sort -k2,2 --field-separator=',' --buffer-size=(80% RAM) --temporary-directory=/volatile BigFile
3 Réponses :
L'avantage de Quicksort sur Mergesort n'est pas une mémoire supplémentaire. L'avantage de Mergesort est le moment de l'exécution de O (N journal N) garanti, où peut être beaucoup pire en cas d'échantillonnage de points de pivot médiocre. Si vous n'avez aucune raison de vous préoccuper de l'utilisation de la mémoire, ne changez pas. Si vous le faites, assurez-vous simplement de choisir une implémentation QuicksTort qui fait un échantillonnage de pivot solide.
Je ne pense pas que cela aiderait de manière spectaculaire à recompiler Sort.c. Cela pourrait être, sur une échelle de micro-optimisation. Mais votre goulot d'étranglement sera une vitesse de mémoire / disque, pas de quantité de processeur disponible. Mon intuition serait que 8 threads allumeront déjà votre débit d'E / S, et vous ne verriez aucune amélioration de la performance, mais cela dépendrait certainement de votre configuration spécifique.
En outre, vous pouvez obtenir des augmentations de performances significatives en tirant parti de la distribution de vos données. Par exemple, des données réparties uniformément peuvent être triples très rapidement par une seule passe de tri de godets, puis utilisez Mergesort pour trier les godets. Cela a également un avantage supplémentaire de la diminution de la mémoire de mémoire totale de Mergesort. Si la composition de la mémoire de Mergesort est O (n) et que vous pouvez séparer vos données en kaux K, votre nouvelle mémoire de mémoire est O (N / K).
Merci Chris. Le plus utile.
juste une idée:
Je suppose que le contenu du fichier est généré pour une grande quantité de temps. Ecrivez une application (script?) Qui déplacierait périodiquement le fichier généré ultérieurement à un emplacement différent, appendez son contenu dans un autre fichier, effectuez une sorte de tri sur ce fichier différent et répétez jusqu'à ce que toutes les données soient recueillies.
De cette façon, votre système passerait plus de temps à trier de temps,
Merci. J'aime ça. Cela diminue à ce que mes objectifs sont les suivants: la vitesse globale (analyse + résultats de tri) vs coût total (je vais avoir besoin de plus de machines pour effectuer le tri continu). Gardera cela à l'esprit quand je vais passer à la version 2.0 de ce projet
Je pense que vous avez besoin d'exécuter ce genre en 2 étapes:
C'est exemple.
Imaginez, vous avez la limite de seau 2 lignes seulement et votre fichier d'entrée est:
infile: 0000 0001 0002 0003 5 53 52 7000
sur la 1ère itération, vous lisez votre fichier d'entrée "Super-godet, avec préfixe vide" et divisé selon la 1ère lettre.
Il y aurait 3 fichiers de sortie:
0: 000 001 002 003
5: (vide) 3 2
7: 000
Comme vous le voyez, le godet avec le nom de fichier / préfixe 7 ne contient qu'un enregistrement 000, qui est "7000", écarté à 7 - nom de fichier, et 000 - queue de la chaîne. Comme il s'agit d'un seul disque, il n'a plus besoin de diviser ce fichier. Mais, les fichiers "0" et "5" contiennent 4 et 3 enregistrements, ce qui est plus que la limite 2. Ainsi, il faut donc diviser à nouveau. Après scission:
00: 01 02 03
5: (vide)
52: (vide)
53: (vide)
7: 000
Comme vous le voyez, fichiers avec préfixe "5" et "7" déjà écarté. Ainsi, il faut juste diviser le fichier "00".
Comme vous le voyez, après avoir fractionné, vous aurez un ensemble de petits fichiers relativement. Par la suite, exécuté 2ème étape:
Triez les noms de fichiers et traitez des noms de fichiers selon l'ordre trié. Trier chaque fichier et ajouter à la sortie à la sortie, avec l'ajout de nom de fichier à la chaîne de sortie.
Vous n'avez pas besoin de plus de threads si le disque est saturé. Les disques sont-ils à 100% pendant le tri? Le plus grand "potentiel" de rentabilité viendra de connaître vos données. Toutes les lignes sont-elles de même longueur, est-ce que tout communité entre les lignes successives, ...?
Merci - les disques ne sont pas saturés. La plupart du temps est effectivement dépensé pour le tri. Il y a peu d'E / S attendre. Les lignes ont la même structure (fichier CSV) mais pas de longueur identique.
Hors de curiosité: Y a-t-il un suivi de cette question? Qu'avez-vous finalement fait?
Il existe Tri externe algorithmes pour de tels ensembles de données énormes qui ne correspondent pas à la RAM. Bien qu'ils soient généralement plus lents, ils sont beaucoup plus rapides pour ce cas particulier.