Trier le contenu d'un fichier texte extrêmement volumineux (800 Go) sous Windows

25

J'ai un fichier texte avec un mot dans chaque ligne, la taille du fichier est de 800 Go. J'ai besoin de trier les mots par ordre alphabétique.

J'ai essayé d'utiliser le programme de tri Windows en utilisant:

sort.exe input.txt /o output.txt

ce qui donne l'erreur: Pas assez de mémoire principale pour terminer le tri.

J'ai 32 Go de RAM, donc lorsque j'essaie de spécifier 10 Go de mémoire pour le tri en utilisant:

sort.exe input.txt /o output.txt /M 10000000

Je reçois:

Avertissement: la taille de mémoire spécifiée est réduite à la mémoire de pagination disponible.

L'enregistrement d'entrée dépasse la longueur maximale. Spécifiez un maximum plus grand.

Quelles sont mes options?

windows sorting MaYaN
la source
2
Merci de ne pas crosspost. Voir La publication croisée d'une question sur plusieurs sites Stack Exchange est-elle autorisée si la question est sur le sujet pour chaque site?
DavidPostill
10
Ce n'est pas un cross-post, je ne suis pas une machine donc poster ceci et supprimer l'autre prend quelques minutes!
MaYaN
3
À l'avenir, permettez à la communauté de migrer votre question
Ramhound
4
Avec Linux, vous pouvez appliquer cette méthode . Avec des fichiers de 100 Mo, cela ne devrait pas être un gros problème.
Eric Duminil
3
Quelle version de Windows utilisez-vous? Le sort.exe avec le plutôt ancien Windows Server 2012 R2 prétend pouvoir effectuer un tri de fusion externe avec l'utilisation d'un fichier temporaire sur le disque (sans documenter une limite de taille). Essayez d'utiliser / T pour spécifier un disque avec 800 Go d'espace libre pour le fichier temporaire. Et le message sur "l'enregistrement d'entrée dépasse la longueur maximale" ne semble pas lié à l'espace - regardez l'option / REC et réfléchissez à la terminaison de votre ligne.
davidbak

Réponses:

16

Quelles sont mes options?

Essayez Freeware Command Line Sort Utility CMSort .

Il utilise plusieurs fichiers temporaires, puis les fusionne à la fin.

CMsort lit les enregistrements d'un fichier d'entrée jusqu'à ce que la mémoire ajustée soit atteinte. Les enregistrements sont ensuite triés et écrits dans un fichier temporaire. Cette opération sera répétée jusqu'à ce que tous les enregistrements soient traités. Enfin, tous les fichiers temporaires sont fusionnés dans le fichier de sortie. Si la mémoire disponible est suffisante, aucun fichier temporaire n'est écrit et aucune fusion n'est nécessaire.

Un utilisateur signale qu'il a trié un fichier de 130 000 000 octets.

Si vous souhaitez modifier vous-même du code, il existe également Tri de fichiers texte volumineux - CodeProject - "Algorithme de tri des lignes dans les fichiers texte dont la taille dépasse la mémoire disponible"

DavidPostill
la source
26
Wow, 130 mégaoctets !!! +1
David Foerster
3
@DavidPostill Êtes-vous sûr que le tri à partir de coreutils pour Windows n'est pas plus efficace ( --paralleloption si vous avez plusieurs cœurs ...)?
Hastur
23

Une autre option consiste à charger le fichier dans une base de données. EG MySQL et MySQL Workbench.
Les bases de données sont des candidats parfaits pour travailler avec des fichiers volumineux

Si votre fichier d'entrée ne contient que des mots séparés par une nouvelle ligne, cela ne devrait pas être trop difficile.

Après avoir installé la base de données et MySQL Workbench, voici ce que vous devez faire.
Créez d'abord le schéma (cela suppose que les mots ne dépasseront pas 255 caractères, bien que vous puissiez modifier cela en augmentant la valeur de l'argument). La première colonne "idwords" est une clé primaire.

CREATE SCHEMA `tmp` ;

CREATE TABLE `tmp`.`words` (
  `idwords` INT NOT NULL AUTO_INCREMENT,
  `mywords` VARCHAR(255) NULL,
  PRIMARY KEY (`idwords`));

Ensuite, importez les données: EG Cela importera tous les mots dans le tableau (cette étape peut prendre un certain temps. Mon conseil serait de lancer un test avec un petit fichier de mots d'abord et une fois que vous êtes sûr que le format est le même que le plus grand (tronquez le tableau .. IE Effacez-le et chargez l'ensemble de données complet).

LOAD DATA LOCAL INFILE "C:\\words.txt" INTO TABLE tmp.words
LINES TERMINATED BY '\r\n'
(mywords);


Ce lien peut aider à obtenir le bon format pour la charge. https://dev.mysql.com/doc/refman/5.7/en/load-data.html
EG Si vous aviez besoin de sauter la première ligne, vous feriez ce qui suit.

LOAD DATA LOCAL INFILE "H:\\words.txt" INTO TABLE tmp.words
-- FIELDS TERMINATED BY ','
LINES TERMINATED BY '\r\n'
IGNORE 1 LINES
(mywords);

Enfin, enregistrez le fichier trié. Cela peut prendre un certain temps en fonction de votre ordinateur.

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
INTO OUTFILE 'C:\\sorted_words.csv';

Vous pouvez également rechercher les données à votre guise. EG Cela vous donnera les 50 premiers mots dans l'ordre croissant (à partir du 0e ou du premier mot).

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
LIMIT 0, 50 ;

Bonne chance
Pete

Peter H
la source
2
C'EST la réponse correcte par une marge considérable.
MonkeyZeus
1
Cette approche sera certainement plus flexible, surtout si vous découvrez que vous devez réexécuter le tri avec un ordre différent, par exemple.
barbecue
Je ne me soucie pas de la vitesse à laquelle votre instance de MySQL , MariaDB ou de tout autre SGBD est, elle ne se rapprochera pas des performances d'insertion de SQLite fonctionnant sur la même machine. Même avec quelque chose d'aussi rapide que SQLite, cette quantité de données est trop (et lente) à traiter (croyez-moi, j'ai d'abord essayé!), La meilleure solution consiste donc à trier et à supprimer les doublons en premier, puis à les insérer dans une base de données telle que SQLite . Donc, bien que cette solution puisse être valable dans certains cas, elle ne l'est certainement pas pour ce que j'essaie de faire. Merci d'avoir pris le temps de poster ça quand même.
MaYaN
Commander par mywordsprendra une éternité. Même avec le LIMIT, cela prendra aussi longtemps que le tout, car MySQL devra passer par chaque valeur mywordset les commander. Pour résoudre ce problème, vous devez effectuer les opérations suivantes après avoir terminé LOAD DATA. Ajoutez un index à mywords. Maintenant, vous pouvez commander par cette colonne et ne pas le faire prendre un millénaire. Et il est préférable d'ajouter l'index après le chargement des données plutôt qu'au moment où vous avez créé la table (chargement des données beaucoup plus rapide).
Buttle Butkus
7

sort

Il existe de nombreux algorithmes utilisés pour trier les fichiers ordonnés et non ordonnés [ 1 ] .
Puisque tous ces algorithmes sont déjà implémentés, choisissez un programme déjà testé.

Dans coreutils (à partir de Linux mais également disponible pour Windows [ 2 ] ), il existe la sortcommande capable de s'exécuter en parallèle sous des processeurs multi-cœurs: généralement c'est suffisant.

Si votre fichier est si volumineux, vous pouvez aider au traitement du fractionnement ( split -l), du fichier dans certains morceaux, en utilisant éventuellement l'option parallèle ( --parallel), et en triant les morceaux ordonnés résultants avec l' -moption ( tri par fusion ).
Une des nombreuses façons de le faire est expliquée ici (fichier divisé, commander des morceaux simples, fusionner des morceaux ordonnés, supprimer des fichiers temporaires).

Remarques:

  • Dans Windows 10, il existe ce qu'on appelle le sous-système Windows pour Linux dans lequel tout l'exemple Linux semblera plus naturel.
  • Le tri avec différents algorithmes a des temps d'exécution différents qui évoluent en fonction du nombre d'entrées à trier (O (n m ), O (nlogn) ...).
  • L'efficacité de l'algorithme dépend de l'ordre déjà présent dans le fichier d'origine.
    (Par exemple, un tri à bulles est l'algorithme le plus rapide pour un fichier déjà ordonné - exactement N -, mais il n'est pas efficace dans d'autres cas).
Hastur
la source
2

Pour offrir une solution alternative à Peter H, il existe un programme q qui autorise les commandes de style SQL contre les fichiers texte. La commande ci-dessous ferait de même (exécutée à partir de l'invite de commande dans le même répertoire que le fichier), sans avoir besoin d'installer SQL Workbench ou de créer des tables.

q "select * from words.txt order by c1"

c1 est un raccourci pour la colonne 1.

Vous pouvez exclure les mots en double avec

q "select distinct c1 from words.txt order by c1"

et envoyer la sortie vers un autre fichier

q "select distinct c1 from words.txt order by c1" > sorted.txt
Brian
la source
Une idée si cela résoudra un fichier de 800 gig?
Rawling
1
Je ne suis pas sûr à 100% - j'ai testé ce qui précède avec un fichier de 1200 lignes (9 Ko). La page des développeurs a une page "limitations" qui ne mentionne rien sur une taille de fichier maximale. Un gros fichier peut toujours rencontrer un problème de mémoire.
Brian
3
q ne peut pas traiter cette quantité de données rappelez-vous que q utilise SQLite en arrière-plan si je ne pouvais pas charger les données directement dans SQLite qu'est-ce qui vous fait penser q peut?
MaYaN
2

Si les mots de chaque ligne proviennent d'un vocabulaire limité (comme l'anglais), vous pouvez trier la liste en O (n + m log m) en utilisant une TreeMap et en comptant les enregistrements (où m est le nombre de valeurs uniques).

Sinon, vous pouvez utiliser le grand trieur de la bibliothèque java . Il divise l'entrée en fichiers intermédiaires triés et les fusionne efficacement (O global (nlogn)). Pour trier votre fichier ressemble à ceci:

Sorter.serializerTextUtf8()
      .input(inputFile)
      .output(outputFile)
      .loggerStdOut() // display some progress
      .sort();

J'ai créé un fichier de 1,7 Go (100 m de lignes) avec des mots de 16 caractères générés de manière aléatoire et trié comme ci-dessus en 142 secondes et en fonction de la complexité de calcul O (n log n) de la méthode que j'utilise, j'estime que 800 Go de mots de 16 caractères seraient prendre environ 24 heures pour trier un seul thread sur mon ordinateur portable i5 2,3 GHz avec SSD.

Dave Moten
la source