Trier un Fichier

Version imprimable

29/04/2008, 10h34
djibril

Trier un Fichier
J'essaye de trouver un module à tester pour trier un fichier text (2 colonnes numériques) de 2 Go (et 130 millions de ligne).
sous linux en console, un sort -n me le fait en 4 minutes
sous perl, j'ai testé File::Sort, j'ai lancé le script mais ça fait plus d'une heure que ça dure 8O et toujours rien
Code:

1 2 3 4 5 6 7 use File::Sort qw(sort_file); my %option_sort = ( I => "sort.txt", o => "sorted.txt", n => 1, # ); sort_file(\%option_sort);
29/04/2008, 14h04
knarf87

Cela peut paraître idiot mais pourquoi ne lance-tu pas la commande shell de tri via ton script Perl? Si ca ne te prend que 4 minutes sur un fichier aussi gros, je doute que cela prenne moins de temps avec l'interpréteur perl...
En ce qui concerne ton problème.. c'est étrange. Je n'ai pas encore installer la lib pour la tester mais.. ca devrait marcher :roll:
Voili voilou
FX
29/04/2008, 14h43
djibril

je sais bien évidemment qu'en lançant une commande system ça fonctionnera :mouarf:.
Je veux juste tester une solution pure perl par curiosité. Et puis on ne sais jamais, on travail pas toujours sous linux, donc question portabilité, c'est mieux.

voilà
05/05/2008, 10h48
djibril

personne n'a l'air inspiré par ce module
06/05/2008, 10h29
knarf87

Citation:

Envoyé par djibril

personne n'a l'air inspiré par ce module

Perso je m'y suis un peu pencher et je n'arrive pas à comprendre pourquoi cela ne marche pas.
Le problème étant en fait de savoir par quelle méthode le fichier est trié. En effet si il s'agit d'un quick sort, ca ne devrait pas saturer comme ca a l'air de le faire chez toi.
Le mieux que tu puisse faire à mon avis est reprendre le code du sort à la linux et d'essayer d'en faire un a ta sauce en perl étant donné que le module ne semble pas marcher.
Une petite question, est-ce que la fonction de tri fonctionne sur des fichiers moins gros?
Si c'est le cas je pense que c'est l'interpréteur perl qui ne doit pas réussir à gérer des fichier aussi gros (si il fonctionne par recopie on se retrouve avec le même problème que sur ton post )
Sinon, ben c'est tout simplement que le module ne marche pas ou qu'il te manque quelque chose. Mais je doute que cette option soit envisageable compte tenu de la maitrise de perl dont tu fait preuve.
Voili Voulou
FX
06/05/2008, 10h59
djibril

Le module fonctionne sur de petits fichiers. C'est uniquement sur ce gros fichier qu'il merdouille.
Ou puis trouver le code source de sort (linux)? car /usr/bin/sort est un binaire.

Merci
06/05/2008, 11h22
knarf87

Ben ta qu'à faire du reverse engineering ^^.
Plus sérieusement le gros problème est d'avoir accès à ton fichier sans avoir a en faire de recopie. Le meilleur moyen serait d'avoir deux pointeurs sur ton fichier qui pointerais chacun un élément et d'appliquer n'importe quel algorithme de tri en comparant la valeur pointé.
Par contre je ne sais pas si c'est possible de manipuler les pointeurs comme on pourrais le faire en C.
Si tu trouve un moyen d'avoir deux pointeurs en simultané sur le même fichier, de pouvoir les incrémenter à chaque fois que tu souhaite échanger deux valeurs, tu devrait t'en sortir.
Après encore une fois je n'ai pas le même niveau de connaissance de Perl que toi mais si ca peut aider c'est déjà ca.
En ce qui concerne les algo j'ai trouver ça je ne sais pas si ca peut t'aider.
Voili, Voilou.
FX
02/08/2009, 20h31
djibril

Je relance le sujet.
L'idéal serait de trouver un algorithm permettant de trier un fichier tabulé quelconque.

Exemple : Nous avons un fichier à tirer de plusieurs Go contenant une centaine de colonnes non numérique. Ce fichier ferait environ 10 millions de lignes. Nous sommes sous Windows, ou bien sous linux et nous n'utilisons pas l'utilitaire sort de linux.
Comment tirer ce fichier en fonctionne de la colonne 2.

Citation:

colonne1 colonne2 colonne3 ...
data11 data12 data13 ...
data21 data22 data23 ...
...

Sous Excel, il est impossible de trier ce fichier car Excel limite le nombre de lignes et de colonnes.
En Perl, la première idée serait de mettre en mémoire le fichier puis d'utiliser sort. Mais là, ce serait de la folie et un jolie out of memory devrait surgir.
Alors avez vous une idée d'algorithm?

Je pensais à ceci :
- Lire le fichier en question ligne à ligne
- Créer un fichier par ligne
- stocker dans un hash le numéro de la ligne en clé et en valeur la colonne à prendre en considération pour le tri.
- Lire le hash via sort de la colonne puis créer le fichier trié.

Question :
1- La création de millions de fichiers a t il un coup énorme niveau performance ?
2- Il faut gérer le faite de la limitation du nombre de fichiers par répertoire (2^32 -1), soit 4 milliards pour un disque ntfs je crois. Donc Il faudrait peut être créer des sous répertoires.
3- Je doute que le hash supporte un nombre de clés si important. Exemple:

Code:

my %LimitHash = map { $_ => 'DataColumn' } (1..50_000_000);

Engendre un Out of memory sur un PC Vista de 2Go de ram.

Merci
02/08/2009, 21h41
iblis

J'ai bien l'impression :oops: que ton idée est vouée à l'échec, comme tu le dis toi même : tu ne pourras pas avoir toutes les clés en mémoire si elles sont trop nombreuses ; et de plus tu devras compter que tout OS gère l'accès à un grand nombre de fichiers, ce qui est paradoxal si on veut que ce soit portable.

Ma première idée a été Tie::File, bien sûr (je ne crois pas que Tie::File::AsHash puisse gérer une telle quantité : il a été fait pour traiter des fichiers de password après tout :)). Mais que faire pour la gestion du hash (ou du tableau de tableau, pour un tri comme dans une transformée de Schwartz) une fois de plus ?

Avec un tampon ? Par exemple comme dans Sort::External. Et d'ailleurs pourquoi pas utiliser Sort::External puisqu'il est fait pour ça.

Donc Tie::File et Sort::External, peut être ? Qu'en dis-tu ?

J'essaie dès que j'ai du temps.
02/08/2009, 21h41
Jedai

Ta solution est parfaitement impraticable !! Tu vas faire péter ton pauvre FS comme ça, quant aux performances... :aie:

Pour avoir une idée des algorithmes, tu peux chercher "external sort", généralement on utilise du merge sort, avec éventuellement une solution en RAM pour trier les portions initiales du fichier.
Néanmoins, il me semble que le CPAN devrait contenir une bonne solution pour toi, je ne vois pas trop de raison... Tu as essayé File::Sort avec des "petits" fichiers pour voir (je suis un peu surpris qu'il mette tant de temps). Sinon tu as Sort::External, et File::MergeSort ou Sort::Merge avec un peu d'huile de coude.

--
Jedaï
02/08/2009, 21h46
djibril

C'est sûr que mon idée est voué à l'echec :aie:.
Tie::File est pas adapté, je me rappelle d'avoir eu un out of memory avec.
Sort::External : je vais voir, faut il encore comprendre comment il fonctionne :aie:
Je vais jeter un coup d'oeil à Sort::External, File::MergeSort et Sort::Merge.

Merci

Voici un script utilisant Sort::External. Reste à le tester sur un très gros fichier

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#!/usr/bin/perl
use strict;
use warnings;
use Carp;
 
use Sort::External;
 
my $Fichier = 'C:\gros_fichier.txt';
 
open (BIG, '>',  $Fichier);
for(150_000_000..1) {
  print BIG "$_\t$_\n";
}
close(BIG);
 
unlink 'sorted.txt';
 
my $sortscheme = sub { 
  (split(/\t/, $Sort::External::a))[2] cmp (split(/\t/, $Sort::External::b))[2] 
};
my $sortex = Sort::External->new( 
  mem_threshold => 1024**2 * 16,
  sortsub         => $sortscheme,
);
open ( HUGEFILE , '<', $Fichier);
    while (<HUGEFILE>) {
        $sortex->feed($_);
    }
    $sortex->finish(outfile => 'sorted.txt',);
#    while ( defined( $_ = $sortex->fetch ) ) {
#        do_stuff_with($_);
#    }
close(HUGEFILE);

Le fichier gros_fichier.txt fait environ 2Go7 et ça fait plus d'une heure qu'il tourne

Bonjour.

J'ai fait un petit test ce matin avec le café (bon, le café a duré autant que le script tournait mais c'est les vacances, non :aie:).

Fichier de 1.7 GB, produit comme ça :

Code:

perl -e 'for (1..10**8) { printf "%08d\t%08d\n", $_, rand(10**8) }' > bigfile
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #!/usr/bin/env perl use strict; use warnings; use Sort::External; open my $fh , '<', 'bigfile' or die "$!\n"; my $sortex = Sort::External->new( mem_threshold => 1024**2 * 1024, sortsub => sub { (split(/\t/, $Sort::External::a))[1] cmp (split(/\t/, $Sort::External::b))[1] } ); while (<$fh>) { $sortex->feed($_) } $sortex->finish(outfile => 'sorted');
Avec un cache très gros, comme dans le code ci-dessus, ça prend 53 mn sur un Intel 2 core 1.5 GHz, 4 GB DDR2 RAM et Perl 5.8.8.

Avec un cache de 16 MB, cela prend 101 mn.

J'aurais dû tester avec Perl 5.10 mais ce n'est pas mon Perl par défaut sur cette machine.

03/08/2009, 12h57
djibril

:ccool:, je vais le relancer sur un PC Vista de 2Go Ram avec Perl 5.10 et je vais voir ce que ça donne. Si mes souvenirs sont bon, la fonction sort a été optimisé dans Perl 5.10. Je test ton code et vous tien au courant de la durée.
03/08/2009, 14h13
djibril

Bon au bout d'une heure, j'ai obtenu ce message d'erreur :

Citation:

Out of memory!
Out of memory!
Callback called exit at C:/Perl/site/lib/Sort/External.pm line 219.
Attempt to free unreferenced scalar: SV 0x3099914, Perl interpreter: 0x23a0bd4 during global destruction.

une idée.
03/08/2009, 14h38
iblis

Quelle taille de cache as-tu passé à Sort::External ? (et quelle est ta RAM totale disponible ?).

J'avais fixé un cache très élevé pour voir quelles seraient les perfs max sur ma machine. Et j'ai oublié de dire que le process perl consommait alors 2.5 GB de RAM 8O !

Fixe-le à 256 MB, peut être sinon. (avec cache valeur défaut 16 MB, prenait le double de temps chez moi)
03/08/2009, 15h12
djibril

pourtant tu avais choisi 1024**2 * 1024 ce qui correspond à 1Go, non ? Or tu me dis que Perl consommait 2Go5, peut tu expliquer ?

Moi j'ai relancé en choisissant 1024**2 * 512 => donc 512 Mo. Ca tourne pour l'instant sur un PC de 2Go de Ram.
03/08/2009, 16h03
iblis

Citation:

Envoyé par djibril

pourtant tu avais choisi 1024**2 * 1024 ce qui correspond à 1Go, non ? Or tu me dis que Perl consommait 2Go5, peut tu expliquer ?

J'ai pas trop d'idée. Bien sûr 1Go c'est la taille maximale du cache de tri, ça ne veut pas dire que Perl n'a pas besoin de plus pour le tratiement :mrgreen:.

Voulais le faire tourner sous Perl 5.10 pour voir mais veux pas toucher au serveur à cet'heure 8-).

J'ai obtenu quelque chose comme 40min avec 400Mo de RAM occupé avec le programme suivant :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/perl
use strict;
use warnings;
use Carp;
use v5.10.0;
 
use Sort::External;
 
my $filename = 'gros_fichier.txt';
 
open my ($bigfile), '>',  $filename
  or die "$filename : $!\n";
 
for(my $i = 150_000_000; $i; $i--) {
  print {$bigfile} "$i\t$i\n";
}
close($bigfile);
 
my $time = time();
 
my $sortex = Sort::External->new( 
  mem_threshold => 1024**2 * 128,
  # sortsub         => $sortscheme,
);
open my($hugefile) , '<', $filename
  or die "write $filename : $!\n";
while (<$hugefile>) {
  $sortex->feed(pack('N',(split /\t/)[1]) . $_);
}
close($hugefile);
$sortex->finish();
 
open my($sortedfile), '>', 'sorted.txt'
  or die "sorted.txt :$!\n";
while( defined (my $line = $sortex->fetch()) ){
  print {$sortedfile} (substr $line, 4);
}
close $sortedfile;
 
say +(time() - $time) , " secondes";

--
Jedaï