Il y a beaucoup de discussions sur le Web sur le thème du tri d'énormes fichiers sur UNIX lorsque les données ne vont pas entrer dans la mémoire. Généralement à l'aide de fusorts et de variantes.
Hoewever, si supposez, il y avait suffisamment de mémoire pour s'adapter à l'ensemble des données, ce qui pourrait être le moyen le plus efficace / le plus rapide du tri? Les fichiers CSV sont ~ 50 Go (> 1 milliard de lignes) et il y a suffisamment de mémoire (5x la taille de données) pour contenir toutes les données.
Je peux utiliser le type Unix, mais cela prend toujours> 1 heure. Je peux utiliser n'importe quelle langue nécessaire, mais ce que je cherche principalement est la vitesse. Je comprends que nous pouvons charger les données à dire, une table DB de type colonnaire et trier, mais c'est un effort unique, donc à la recherche de quelque chose de plus agile ...
Merci d'avance.
3 Réponses :
Qu'en est-il de Quicksort? As-tu essayé? STD :: Trier est généralement implémenté par QuickSort (plus précisément Introsort, qui passe à Heapsort si les performances Quicksort seraient mauvaises) afin que vous puissiez essayer avec elle. Quicksort est généralement l'option la plus rapide (bien que la plus grande complexité des cas est O (n ^ 2), mais dans des cas habituels, il bat tous les autres algorithmes de tri).
La complexité spatiale de QuickSort ne doit pas être trop mauvaise, elle nécessite un espace de pile de log2 (n) d'environ 30 cadres de pile pendant 1 milliard d'articles.
Cependant, il s'agit d'un algorithme de tri instable (l'ordre des éléments «égaux» n'est pas préservé), cela dépend donc de cela.
BTW. Unix Tricole semble être mis en œuvre par le tri de la fusion, ce qui n'est généralement pas l'option la plus rapide du tri en RAM.
Utilisez des algorithmes de tri parallèle pour d'énormes données.
Sujet utile: quel algorithme de tri parallèle a la meilleure performance de cas moyenne? < / a>
Je sais que c'est vieux mais je pense que je trompais avec ce que je viens de comprendre dans l'espoir que cela pourrait aider quelqu'un d'autre à l'avenir.
gnu trier comme vous savez peut-être déjà assez vite. Couple qui avec de nombreux cœurs CPU et beaucoup de RAM et lorsque vous passez dans des drapeaux spéciaux à la sorte de GNU et le rendez-le extrêmement rapide. P>
* Payez une attention particulière au drapeau "Taille tampon" . La taille du tampon est la principale raison de cette rapidité. ive a utilisé le drapeau parallèle avant et ce n'était pas aussi rapide par lui-même. em> p> J'ai utilisé une boucle pour gérer tous les fichiers du dossier et trier d'énormes fichiers CSV, par la deuxième touche, avec une virgule Delim, en gardant uniquement unique unique. Valeurs, avec les résultats suivants: P> tr trits --parallel = 32-Taille = 40G -U -T, -K2 - o $ file.csv dossier code> p> for file in $(ls -p | grep -v -E "[0-4/]");
do
time sort --parallel=32 --buffer-size=40G -u -t, -k2 -o $file.sorted.csv $file;
done
real 0m36.041s
user 1m53.291s
sys 0m32.007s
real 0m52.449s
user 1m52.812s
sys 0m38.202s
real 0m50.133s
user 1m41.124s
sys 0m38.595s
real 0m41.948s
user 1m41.080s
sys 0m35.949s
real 0m47.387s
user 1m39.998s
sys 0m34.076s
Que contiennent les fichiers?
Ram = 5x50gb? Vraiment? 250 Go de RAM. C'est un quincaillerie sérieux que vous devez jouer avec. Est-ce qu'ils embauchent :-)
:-) ... c'est un serveur de taille standard pour la plupart des banques d'investissement, cela a une mémoire modeste en comparaison. Il est principalement de prendre en charge KDB + (voir kx.com).
@Nawaz, ce sont des fichiers CSV avec des combinaisons de chaînes, d'INTS, des dates de chaque rangée.
"... CVS Fichiers ...> 1 milliard de lignes ...": oubliez le tri. Vous avez un problème beaucoup plus grave à résoudre, un élément fondateur / architectural. Vous avez perdu la guerre lorsque votre architecture vous a mis dans la position de traitement au hasard d'un milliard d'enregistrements à partir d'un fichier de longueur d'enregistrement variable. Vous devez revenir en arrière et repenser votre processus entier.
Cela ressemble à quelque chose digne de quelques expériences. Si
Trier n'est pas assez rapide, j'essaieraissqlite suivant. (1) Chargez les données sur une table sans index, (2) Ajouter un index, (3) Requête la table triée pour tous les enregistrements. SQLite devrait pouvoir charger les données de CSV. Si vous pouvez utiliser un vrai RDBM au lieu de SQLite, cela pourrait valoir la peine de scinder l'importation CSV en plusieurs processus.Nous n'avons pas créé les fichiers. C'est le format dans lequel ils sont livrés de l'extérieur.
Avez-vous essayé d'utiliser le coreTils
trier avec le format défini sur, dites, le nombre de fichiers d'entrée (ou éventuellement environ la moitié)?@Euro, ce que je cherche que je cherche si vous aviez la puissance informatique de l'attaquer, quelle est la méthode la plus rapide ...
@Hasturkan, pas encore ...
Si la puissance de calcul était supposée être impliquée (250 Go, XD), une variante de trier de godets pour les fichiers CSV serait la meilleure, je crois (comme ils sont théoriquement O (n)))
En outre, Retour à
Trier , Tri GNUTRY a- Parallel = N et- TAILLE DE BATCH = NMERGE Options.@wilx, va essayer ça. Ce que je pense pourrait être le plus efficace, c'est si vous pouvez lire cela directement dans la mémoire contiguë, trier la mémoire et écrire sur le disque, ...
@XBSD: ("... livré de l'extérieur ..."): C'est la source. Alors quoi? Qu'est ce que tu fais avec? Vous devez être capable de regarder le problème «entier». A-t-il vraiment besoin d'être trié? Allez-vous charger les données dans une base de données? Allez-vous la partitionner? Avez-vous besoin de trier uniquement une projection des données? Si c'est une offre unique que vous l'avez décrite et que vous avez trouvée, cela prend simplement des heures via le type de Unix, pouvez-vous vivre avec cela?
@Euro, trouver les lignes distinctes est le but ultime. Qui réduit la taille globale des données. Il est chargé dans un système dans lequel un ensemble de données plus petit peut être manipulé plus efficacement que la taille d'origine ...
Si vous avez vraiment besoin de trier le fichier entier, la meilleure méthode de tri est ... "Cela dépend", sur la distribution des données autour des critères de tri. Le critère de tri est-il une colonne unique? Contigu? Clairsemé? Connaissez-vous la portée A priori? combien savez-vous? Exemple: Disons que les critères de tri sont (ou peuvent être mappés) une séquence contiguë de nombres uniques avec peu ou zéro de la monnaie et que vous connaissez la gamme, la longueur d'enregistrement max et compter à l'avance. Le tri le plus rapide consiste à pré-allouer un fichier de maxreclen * RECCNT, lisez le fichier en séquence et vider chaque enregistrement sur son emplacement approprié.
Basé sur votre dernier commentaire, je pourrais essayer de jeter / fusionner des enregistrements à la volée lorsque vous les chargez à la base de données (avec index en ligne). Lorsque vous trouvez un duplicata, gérez-le. Cela pourrait ou pourrait ne pas fonctionner, car l'insertion d'un milliard d'enregistrements avec des indices en ligne est extrêmement coûteux. Ou cela pourrait fonctionner si le jeu de données final n'est que quelques millions d'enregistrements. Je ne sais pas. Le point est qu'il s'agit d'un cas très spécifique avec des conditions extrêmes, et une réponse générique "la plus rapide de faire x" n'est pas liée à résoudre votre problème. La meilleure réponse à votre problème dépend fortement de la distribution de vos données.
Ce peut être de l'aide.
@Euro, ce n'est pas des données clairsemées, totales 6 colonnes (entiers et champs de date)