Tri alphabétique ultra rapide de chaines de caractères de longueur variable [Résolu]
mslider109
Messages postés jeudi 21 octobre 2004Date d'inscription
7 mars 2010
Dernière intervention
-
22 sept. 2009 à 21:43 - Dernière réponse : mslider109
Messages postés jeudi 21 octobre 2004Date d'inscription
7 mars 2010
Dernière intervention
- 2 févr. 2010 à 21:19
je sais que c'est un forum dédié au C mais je vais parler de pascal.
En effet je connais bien ce langage et je l'ai utilisé pour trier alphabétiquement un fichier texte comportant 4 millions de chaines de caractères(en gros 4 millions de mots en colonne).
J'ai été surpris de la rapidité de mon code: 9 secondes pour lire le fichier, le trier et envoyer le résultat dans un autre fichier.
Je voudrais savoir si il existe un programme écrit en C qui serait plus rapide que celui que j'ai écris en pascal objet sous linux ?
- Oui pour info en utilisant la commande SORT sous Unix, le temps de traitement = 20s !
Exemple de fichier en entrée:
TCGTATGCCGTCTTCTGCTTGAAAAAAAAAAAAAA
TCGGACCAGGCTTCATTCCCCTCGTATGCCGTCTT
TCCCAAATGTAGACAAAGCATCGTATGCCGTCTTC
GGGGATGTAGCTCAGATCGTATGCCGTCTTCTGCT
TCGGACCAGGCTTCATCCCCCTCGTATGCCGTCTT
GGCGGATGTAGCCAAGTGGATCGTATGCCGTCTTC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
GGGGATGTAGCTCAAATCGTATGCCGTCTTCTGCT
TTGACAGAAGAAAGAGAGCACTCGTATGCCGTCTT
GTATGCCGTCTTCTGCTTGAAAAAAAAAAAAAAAA
AGGGAGAGAACTGATCGCCGGTGATCGTATGCCGT
TCGCTTGGTGCAGGTCGGGAATCGTATGCCGTCTT
TTGACAGAAGATAGAGAGCACTCGTATGCCGTCTT
TTTGGATTGAAGGGAGCTCTATCGTATGCCGTCTT
AGGACTGTGTATTACGGAGAGCATTCGTATGCCGT
TGACAGAAGAAAGAGAGCACTCGTATGCCGTCTTC
ATTGGAGGACACGAGGCAAGTATCTCGTATGCCGT
GGGGGTGTAGCTCATATCGTATGCCGTCTTCTGCT
AATCGTATGCCGTCTTCTGCTTGAAAAAAAAAAAA
TGACAGAAGAGAGTGAGCACTCGTATGCCGTCTTC
.../...
le code en turbo pascal(Delphi) écrit sous environnement Lazarus (Linux):
program ltrieuse;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}{$IFDEF UseCThreads}
cthreads,
{$ENDIF}{$ENDIF}
Classes, SysUtils, CustApp
{ you can add units after this };
type
{ TMyApplication }
TMyApplication = class(TCustomApplication)
protected
procedure DoRun; override;
public
constructor Create(TheOwner: TComponent); override;
destructor Destroy; override;
procedure WriteHelp; virtual;
end;
{ TMyApplication }
procedure TMyApplication.DoRun;
var
ErrorMsg: String;
Liste1 : TStringList; // l'objet liste
Infile, // nom du fichier entree
Outfile : string; // nom du fichier sortie
begin
// quick check parameters
ErrorMsg:=CheckOptions('h','help');
if ErrorMsg<>'' then begin
ShowException(Exception.Create(ErrorMsg));
Halt;
end;
// parse parameters
if HasOption('h','help') then begin
WriteHelp;
Halt;
end;
{ add your program here }
if ParamCount < 1 then writeln ('Un fichier en entree SVP');
if ParamCount >= 1 then
begin
Infile := ExtractFileName(ParamStr(1)); // recupere le nom du fichier entree
writeln(' Fichier en entree : ', Infile); // ecrit sur la console
writeln (' Debut de lecture : ',TimeToStr(Time));
If paramcount = 2
then
Outfile := ExtractFileName(ParamStr(2)) // recupere le nom fichier sortie
else Outfile := 'TRI'+Infile; // oubien le cree
Liste1 := TStringList.Create; //construire l'objet liste
try // utilisation de la liste dans un bloc d'interception des erreurs
Liste1.LoadFromFile(infile); // ici on lit le fichier d'entree dans la liste
writeln (' Fin de lecture : ',TimeToStr(Time));
writeln (' mombre de lignes : ',IntToStr(Liste1.count));
Liste1.Sort; // on trie la liste
writeln (' Fin de tri : ',TimeToStr(Time));
Liste1.SaveToFile(Outfile); // et on la sauve dans le fichier de sortie
finally // fin du bloc
Liste1.free; // liberer la liste
writeln (' Fichier de sortie : ', outfile);
writeln (' Fin ecriture : ',TimeToStr(Time));
end;
end;
// stop program loop
Terminate;
end;
constructor TMyApplication.Create(TheOwner: TComponent);
begin
inherited Create(TheOwner);
StopOnException:=True;
end;
destructor TMyApplication.Destroy;
begin
inherited Destroy;
end;
procedure TMyApplication.WriteHelp;
begin
{ add your help code here }
writeln('Usage: ',ExeName,' -h');
end;
var
Application: TMyApplication;
begin
Application:=TMyApplication.Create(nil);
Application.Title:='Ltrieusue';
Application.Run;
Application.Free;
end.
Je suis presque sur qu'un programme en C qui lit les chaines de caracteres dans un void* et les cast en int* pour les comparaisons dans un quicksort(insertionsortpour des portions de tableau inferieur a 200 en longueur) serait aussi rapide (sinon plus) que ton programme
http://liveplayaz.com je suis heureux de faire partie d'une grande famille ...!
nickydaquick -> Je ne sais pas si Lazarus fait de même que Delphi, mais je suppose que c'est comme pour Delphi, à savoir que les tris sont implémentés en quicksort.
Une des paticularités du code ci-dessus est que la TStringList est, au sens C, un tableau de char* (char**). Donc, lors du tri, il compare les chaîne mais ne fait que déplacer les pointeurs sur elles à l'intérieur du tableau.
Concernant le cast en int*, c'est un peu plus compliqué à cause du little-endian : on ne peut pas trier des chaines comme des entiers !
Il faut donc par exemple utiliser l'instruction asm bswap pour inverser avant de comparer, comme ça avait été fait lors d'un benchs inter-langages qui a eu lieu sur ce site (Mais les résultats n'ont pas pu être exploités à cause d'un défaut dans l'énoncé).
mslider -> Ah tiens mais je t'ai déjà croisé toi !
En fait du point de vue du programmeur C, ta question peut paraître trollesque, amusante, fatigante voir même absurde...
En effet, le C, comme le Delphi (Je vais parler ici de Delphi car je n'ai essayé Lazarus qu'une ou deux fois), sont compilés en code machine.
Donc un exécutable Delphi ressemble énormément à un exécutable C. Le code machine dépend du processeur, pas du langage.
Ainsi lorsque tu compare la vitesse de deux exécutables, tu juges de la qualité du code machine généré, que ce soit sur le plan de :
1) L'algorithmie.
2) L'optimisation fine avec des combinaison d'instruction qui font la même chose mais un peu plus rapidement.
3) La quantité d'accès disque qu'il va engendrer (Variable d'une exécution à l'autre car il y a des accès explicites et d'autres qui le sont moins...).
4) La mémoire : il faut essayer de travailler au maximum dans le cache processeur, c'est à dire utiliser le minimum de mémoire et toujours la même.
5) Le multi-threading s'il peut aider, ce qui n'est pas toujours le cas.
6) La quantité d'appels au système d'exploitation.
7) ...
On sait maintenant que les performances de l'application dépendent du code machine, donc de la combinaison d'instruction processeur.
Comment est généré ce code machine ?
1) Par compilation de source.
2) Par utilisation de librairies déjà compilées.
La performance de l'application finale dépend donc de trois facteurs :
1) De la qualité de la compilation, donc du compilateur.
2) De la qualité du source (Du point de vue des performances) : les compilateurs sont stupides, et ne feront jamais du bon boulot si le source est merdique.
3) De la qualité des librairies utilisées, autrement dit de la qualité de leurs sources
et du compilateur utilisé pour les générer.
1) Tout d'abord intéressons nous aux compilateur.
On ne peut pas dire qu'il n'y a pas de différence d'un compilo à l'autre, mais elle sont cependant peu importantes.
A partir du moment ou les développeurs du compilateur ont pas trop mal fait leur boulot...
Ainsi, les différences de performance s'expliquent beaucoup plus par les différences dans l'implémentation des librairies standards fournies avec le compilo que par la génération de code.
Une instruction for génère globalement le même code que ce soit en Delphi ou en C.
Bien sûr il y a des variations et des optimisations, mais globalement, les performances vont rester proches.
2) Voyons la qualité du source.
La qualité du source dépend du développeur... Mais pas seulement. Elle dépend aussi du langage!
Par exemple, il est clair que le Java, même doté du meilleur compilateur en langage machine du monde (Je parle ici d'un compilo style gcj, pas d'un compilo vers du byte code), ne pourra égaliser les performances du C.
De même, un langage faiblement typé, genre PHP, donne beaucoup de travail au compilateur, qui va donc générer du code machine de piètre qualité (Dans l'hypothèse là aussi de faire un vrai compilo code machine pour PHP, et non de l'interprété).
Bref, des langages sont plus lents de part leurs syntaxes, qui ne permettent pas au développeurs de générer un code machine optimal.
On ne fait pas ce que l'on veut : le langage est de trop haut niveau.
Par exemple en Java, on ne peut pas manipuler directement les adresses des objets, car ceux-ci n'ont pas d'adresse fixe.
En ce qui concerne le Delphi on peut écrire du Delphi qui ressemble beaucoup à du C (Pas d'utilisation d'objets, pas d'utilisation de String...)...
Donc le Delphi n'est pas du tout limitant : il permet de produire les mêmes combinaisons d'instructions processeur que le C.
Pour ce qui est du développeur... Disons que ce n'est pas le sujet !
Mais quand même. Le développeur doit avant tout soigner ses algos, savoir ce qui coûte, mettre en place des caches si nécessaire...
Il doit donc aussi bien connaître les librairies qu'il utilise et globalement les actions que celle-i va réaliser.
Par exemple que TStringList.Sort fasse fasse un tri de tableau de pointeur à l'aide d'un quicksort.
Inutile me diras-tu ? Oui et non !
Si on cherche les performances, on peut s'apercevoir que c'est pas forcément idéal dans le cas où l'on se trouve.
Par exemple ici, Sort devrait relativement bien faire son boulot : vu la taille de tes lignes (Une trentaine de caractères), il peut être préférable d'utiliser des pointeurs plutôt que de déplacer les caractères.
Par contre, une TStringList
de 4 millions d'éléments... 4 millions de String... C'est plutôt lourd.
3) Et finalement intéressons nous aux librairies.
Un point important qui fait différer le C de la plupart des langages (Y compris du C++), c'est sa séparation claire entre le langage et les librairies.
En effet, les instructions (if, for, switch...) et les opérateurs (+, -, =, ...) du C n'utilisent jamais de librairies. Ils sont directement transformés en langage machine.
On peut donc écrire un code C qui n'utilise AUCUNE librairie. Si le source est court, l'exécutable sera minuscule (De l'ordre de quelques ko).
Mais on peut aussi faire des applications complètes ainsi, en faisant des appels à l'OS.
L'important est que la runtime (La bibliothèque standard C), qui permet par exemple la comparaison de chaîne, l'allocation dynamique... est parfaitement optionnelle et remplaçable !
On peut donc générer des exécutables dont les performances ne dépendent pas des librairies utilisées, car ils n'en utilisent pas !
Et avec un rien d'entrainement, on est capable de deviner approximativement quel séquence d'instruction assembleur vont être générées à partir d'une portion de code C.
Et c'est là que la toute puissance du C s'exprime.
On explique par exemple souvent que le C est plus lent que le java en ce qui concerne une allocation dynamique, car un garbage collector (Ils sont implémentés sous forme de pile) est plus rapide qu'un tas lors des allocations.
Mais rien n'empèche de faire un pseudo garbage collector en C !
Par contre on ne peut pas faire une allocation classique en java... C'est pour cela que certains développeurs considère le C comme la liberté et le java comme une prison.
On est donc théoriquement capable en C de générer des fichier exécutable ressemblant comme deux gouttes d'eau à des fichiers exécutables générés à l'aide d'autres langages (Assembleur excepté).
C'est pour cela qu'il est pratiquement impossible de battre les performances du C. Il suffit de réécrire TStringList.Sort en C avec le même algo que celui en Delphi pour tomber sur des performances similaires.
Ce principe des instructions/opérateurs générant des uniquement des instructions processeurs ne s'applique pas du tout au VB6 par exemple, ou une boucle for un peu compliqué va générer des appels à la "librairie standard" VB6.
Il ne s'applique pas non plus au Delphi. L'unité "System" est incluse implicitement dans les uses, et on ne peut pas s'en passer.
Et le compilateur va inclure dans l'exécutable résultant du code machine de cette librairie, code que l'on ne peut pas contrôler.
De même, ça se voit bien au niveau des instruction : on peut faire une comparaison de chaîne avec =. Mais en fait le compilateur va traduire ça par un appel à une fonction : LStrCmp.
C'est un appel caché à une fonction d'une librairie ! Inconcevable en C où comme je l'ai expliqué tout est explicite.
Cependant, en connaissant suffisamment la façon dont est compilée le Delphi, on peut coder de manière à ce que celui-ci ne fasse jamais d'appel à des fonctions de l'unité System.
Bien sûr cela impose de nombreuses restrictions, par exemple on ne peut pas travailler en orienté objet, ou utiliser String.
Autre bémol, l'exécutable reste quand même de taille supérieure à ce qu'on pourrait espérer.
Mais le fait que ce soit possible est un signe majeur dans la qualité du langage : beaucoup d'autres n'offrent pas cette possibilité !
Toutefois, on n'est pas au niveau de contrôle du C.
Ma conclusion est que le pascal et le C sont de performance similaire quand ils sont utilisés par un même développeur, connaissant bien la façon dont sont compilé ces deux langages, et le fonctionnement d'un processeur.
Le C ne peut pas battre le pascal à pleine couture, et inversement : avec le même algo ils se tiennent dans un mouchoir de poche.
Ces deux langages peuvent donc être utilisés indifféremment lors de l'écriture d'une application qui se doit d'être performante.
Le C garantit plus de contrôle.
Mais l'avantage le pascal permet de faire beaucoup de chose avec très peu de code à l'aide d'une "librairies standard" très polyvalente et cependant très performante.
Voilà donc un code C qui est plus rapide que ton pascal. Du moins sur ma machine...
Pascal -> 46 secondes.
C -> 8 secondes.
Mais j'aurais appliqué le même algo en Pascal, j'aurais eu un résultat similaire.
Et je pourrais faire mieux en Pascal, par exemple en multi-threadant le tri.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
char* GetTime(char* lpBuffer, long nSize)
{
time_t nCurrentTime;
struct tm* timeInfo;
time(&nCurrentTime);
timeInfo = localtime(&nCurrentTime);
strftime(lpBuffer, nSize, "%H:%M:%S", timeInfo);
return lpBuffer;
}
FILE *SafeOpenFile(char *lpFileName, char *lpMode, FILE **lpFile)
{
*lpFile = fopen(lpFileName, lpMode);
if (! *lpFile)
printf("Cannot open file: "%s"\n", lpFileName);
return *lpFile;
}
long GetSizeOfFile(FILE* lpFile)
{
long nCurrentPos;
long nResult;
nCurrentPos = ftell(lpFile);
fseek(lpFile, 0, SEEK_END);
nResult = ftell(lpFile);
fseek(lpFile, nCurrentPos, SEEK_SET);
return nResult;
}
void** SetSize(void** lpArray, long nTypeSize, long nSize)
{
long* lpLongArray;
long nCapacity;
lpLongArray = (long*)*lpArray;
if (! nSize)
{
if (lpLongArray)
{
free(&lpLongArray[-2]);
lpLongArray = NULL;
}
}
else
{
if (! lpLongArray)
{
lpLongArray = (long*)malloc(2 * sizeof(long) + nTypeSize * nSize);
if (lpLongArray)
{
lpLongArray[0] = nSize;
lpLongArray[1] = nSize;
lpLongArray = &lpLongArray[2];
}
}
else
{
/* Si agrandissement */
if (lpLongArray[-1] <= nSize)
{
/* Si la capacité est suffisante */
if (lpLongArray[-2] >= nSize)
lpLongArray[-1] = nSize;
else
{
/* On double la capacité et on vérifie que c'est suffisant */
nCapacity = 2 * lpLongArray[-2];
if (nCapacity < nSize)
nCapacity = nSize;
lpLongArray = (long*)malloc(2 * sizeof(long) + nCapacity * nTypeSize);
if (lpLongArray)
{
lpLongArray[0] = nCapacity;
lpLongArray[1] = nSize;
lpLongArray = &lpLongArray[2];
memcpy(lpLongArray, *lpArray, ((long*)(*lpArray))[-1] * nTypeSize);
free(&((long*)(*lpArray))[-2]);
}
}
}
else
{
/* On ne désalloue que si c'est vraiment utile */
if (nSize * 2 > lpLongArray[-2])
lpLongArray[-1] = nSize;
else
{
/* Allocation d'un espace plus petit et recopie du début */
lpLongArray = (long*)malloc(2 * sizeof(long) + nSize * nTypeSize);
if (lpLongArray)
{
lpLongArray[0] = nSize;
lpLongArray[1] = nSize;
lpLongArray = &lpLongArray[2];
memcpy(lpLongArray, *lpArray, nSize * nTypeSize);
free(&((long*)(*lpArray))[-2]);
}
}
}
}
}
*lpArray = lpLongArray;
return lpArray;
}
long GetSize(void* lpArray)
{
long* lpLongArray;
long nResult;
nResult = 0;
lpLongArray = (long*)lpArray;
if (lpLongArray)
nResult = lpLongArray[-1];
return nResult;
}
int Compare(const void* a, const void* b)
{
char* lpStr1;
char* lpStr2;
long nI;
lpStr1 = *(char**)a;
lpStr2 = *(char**)b;
nI = 0;
while ((lpStr1[nI] != '\n') &&
(lpStr1[nI] != '\r') &&
(lpStr2[nI] != '\n') &&
(lpStr2[nI] != '\r') &&
(lpStr1[nI] == lpStr2[nI])) nI++;
return lpStr1[nI] - lpStr2[nI];
}
int main()
{
FILE* lpInputFile;
FILE* lpOutputFile;
long nInputSize;
char* lpFileContent;
char* lpResultContent;
char** lpSortingArray;
char lpTime[20];
int bWasCrOrLf;
long nI;
long nJ;
long nK;
int nResult;
nResult = 1;
printf("Debut de lecture : %s\n", GetTime(lpTime, 20));
if (! SafeOpenFile("Input.txt", "rb", &lpInputFile)) goto the_end;
if (! SafeOpenFile("TRIinput.txt", "wb", &lpOutputFile)) goto close_input;
nInputSize = GetSizeOfFile(lpInputFile);
lpFileContent = (char*)malloc(nInputSize + 1);
if (! lpFileContent)
{
printf("Unable to allocate input buffer\n");
goto close_output;
}
if (fread(lpFileContent, 1, nInputSize, lpInputFile) != nInputSize)
{
printf("Unable to read input file\n");
goto free_content;
}
lpFileContent[nInputSize] = 0;
/* Remplissage d'un tableau de pointeur sur les chaînes */
lpSortingArray = NULL;
bWasCrOrLf = 1;
for (nI = 0; nI < nInputSize; nI++)
{
if ((lpFileContent[nI] != '\n') && (lpFileContent[nI] != '\r'))
{
if (bWasCrOrLf)
{
SetSize((void**)&lpSortingArray, 4, GetSize(lpSortingArray) + 1);
lpSortingArray[GetSize(lpSortingArray) - 1] = &lpFileContent[nI];
bWasCrOrLf = 0;
}
}
else
bWasCrOrLf = 1;
}
printf("Fin de lecture : %s\n", GetTime(lpTime, 20));
printf("Nombre de lignes : %ld\n", GetSize(lpSortingArray));
/* Tri */
qsort(lpSortingArray, GetSize(lpSortingArray), sizeof(char*), Compare);
printf("Fin de tri : %s\n", GetTime(lpTime, 20));
/* Génération du fichier de sortie en mémoire */
lpResultContent = (char*)malloc(nInputSize + 1);
if (! lpResultContent)
{
printf("Unable to allocate output buffer\n");
goto free_content;
}
nK = 0;
for (nI = 0; nI < GetSize(lpSortingArray); nI++)
{
bWasCrOrLf = 0;
nJ = 0;
while (1)
{
if ((lpSortingArray[nI][nJ] == '\r') ||
(lpSortingArray[nI][nJ] == '\n'))
bWasCrOrLf = 1;
else if (bWasCrOrLf)
break;
lpResultContent[nK] = lpSortingArray[nI][nJ];
nK++;
nJ++;
}
}
lpResultContent[nInputSize] = 0;
if (fwrite(lpResultContent, 1, nInputSize, lpOutputFile) != nInputSize)
{
printf("Unable to write output file\n");
goto free_result;
}
printf("Fin ecriture : %s\n", GetTime(lpTime, 20));
nResult = 0;
free_result:
free(lpResultContent);
free_content:
free(lpFileContent);
close_output:
fclose(lpOutputFile);
close_input:
fclose(lpInputFile);
the_end:
return nResult;
}
rt15 --> pour info oui on s'est déjà vu sur un autre post !
mon programme pascal en question a été compilé sur un DELL PowerEdger 2600 bi-processeurs (Intel Xeon 3Ghz, 3Go RAM, disque SCSI).
Le fichier de test à trier comporte exactement 3388634 lignes.
J'ai bien utilisé un Quicksort mais j'ai hésité sur un tri à bulles, peut être que les performances auraient été meilleures,
à voir.
Je vais déjà essayer de le compiler sur une machine 64 bits pour voir la difference.
Mon fichier source à trier gzippé fait ~ 21 Mo. Comment vous le faire passer, par mail ?
Le quicksort est souvent le meilleur.
Il n'y a guère que le tri par dénombrement qui peut faire mieux, mai on ne peut le mettre en place que dans certains cas particuliers.
Pour le fichier, tu peux le mettre sur dl.free.fr, et mettre le lien pour le télécharger ici.
6 secondes au lieu de 9.
je pense qu'on peut aller plus vite en utilisant un cache et en l'executant sur une machine 64 bits.
A titre indicatif je l'ai compilé en 32 bits sur une machine 64 bits qui a 16 processeurs(Opteron 2.8Ghz) et 16Go de RAM.
résultat: 10s.
En tout cas çà vérifie bien ce que tu disais dans ton précédent message: le code machine généré par le compilateur C est mieux
optimisé que par le compilateur Delphi.
Aaaaarrrrh ! Mais non ! Ce n'est pas ce que j'ai dit !
J'aurais pu écrire le même code que celui que j'ai posté, mais en pascal, et il aurai mis 7 secondes. Ou 5. Si tu le traduis mot pour mot en pascal tu auras le même résultat.
Ce n'est pas parce que ton code est un quicksort et le mien aussi que c'est le même algo. C'est ressemblant mais ce n'est pas le même.
c'est pas possible, un compilateur pascal ne peut pas faire appel aux memes jeu d'instructions système avec la même chronologie
et le même ordonnancement qu'un compilateur C.
Donc écrire le même code en pascal que celui que tu as écris en C, je veux bien essayer mais je suis à peu près sur que le temps d'exécution sera different.
Et oui comme quoi des fois c'est pas inutile de tester le retour des mallocs, surtout quand ils sont gros. Et de sortir proprement en libérant les ressources en cas de problème, et à ce niveau, les gotos c'est vraiment sympa pour conserver une indentation raisonnable.
lpResultContent = (char*)malloc(nInputSize + 1);
if (! lpResultContent)
{
printf("Unable to allocate output buffer\n");
goto free_content;
}
Le malloc demande la taille du fichier + 1... Ca doit faire dans les 2Go consécutifs pour une fichier de 80 millions de lignes. Normal qu'il ait du mal... A l'inverse de ton code qui alloue un peu plus, mais qui fait une petite allocation par ligne de fichier.
--
oui c vrai ton code est plus propre.
le mien renvoit un segmentation fault.
Bon il me reste plus qu'à acheter des barettes de RAM (j'ai que 4Go de RAM).
En effet le fichier de 80 millions de lignes fait 1,5 Go. C'était juste un test juste pour le
fun pour voir si çà passait.
--
#!/bin/perl
use strict;
use warnings;
my $input='/tmp/Input.txt';
my $output='output.txt';
my $time = localtime();
print "Début de lecture : $time\n";
open(F, "<$input") or die "can't open file $input\n";
my @tags;
my $n=0;
while (<F>) {
chomp;
push @tags, $_;
$n++;
}
$time = localtime();
print "Fin de lecture : $time\n";
print "Nombre de lignes :$n\n";
open(FO, ">$output") or die "can't write in file $output";
foreach (sort @tags) {
print FO $_,"\n";
}
$time = localtime();
print "Fin d'écriture : $time\n";
temps d'exécution = 8s
pas mal pour un langage interprété
cs_Dobel333
Messages postés dimanche 25 mai 2003Date d'inscription
23 novembre 2009
Dernière intervention -30 sept. 2009 à 00:35
0
Merci
@ rt15
Tu ferais bien de remplacer ton '4' par un sizeof(char *)... ça peut faire des étincelles sur certains systèmes sinon :)
Je copie un code tout simple et comparable au tien pour les perfs. Celui là perd du temps à la lecture car un malloc/ligne (puis en free à la fin...), mais j'ai fait au plus simple pour pouvoir trier aussi ce qui arrive sur stdin.
Je test sur un fichier de 4000000 de lignes de 35 caractères (144000000 octets).
C'est un gcc 4.3, les flags d'optim sont les mêmes pour tous les exécutables (y compris pour la commande sort).
Le fichier de données est dans le cache de l'OS, et le fichier de sortie est /dev/null pour ne pas fausser les tests avec les I/O.
déjà, la commande sort en référence, en lui donnant un buffer suffisant pour qu'ils n'utilise pas de fichier temporaire sur le disque dur
# time nice -n -20 sort -S500M toto -o /dev/null
real 0m45.331s
user 0m44.763s
sys 0m0.488s
ensuite celui de rt15,
# time nice -n -20 ./cs
Debut de lecture : 00:02:33
Fin de lecture : 00:02:34
Nombre de lignes : 4000000
Fin de tri : 00:02:41
Fin ecriture : 00:02:42
real 0m9.009s
user 0m8.409s
sys 0m0.512s
Mon premier programme.
# time nice -n -20 ./sortfile_simple toto /dev/null
real 0m9.127s
user 0m8.737s
sys 0m0.360s
Pas mal pour une lecture bourrine comme ça :) Mais on peut faire bien mieux :)
Quelques pistes d'optim que j'ai utilisé pour un autre programme :
- Lecture
Là, je recopie le fichier dans la mémoire du process, ligne par ligne. C'est bien pour une lecture sur stdin, mais pas terrible sinon. D'autant plus que le fichier est peut-être déjà dans le cache de l'OS. Déjà, faire une lecture en une fois dans un gros buffer améliore bien, mais on peut parfois faire encore mieux.
Si dans le fichier de données, les lignes sont séparées par \0 au lieu de \n, alors plus besoin de faire une copie du fichier. On peut l'ouvrir avec mmap et faire pointer le tableau directement sur le mapping (en faisant attention à la dernière ligne si elle n'est pas terminée quand même).
- Tri
Quicksort se parallélise naturellement. Par contre, je n'ai vraiment pas envie d'écrire ça :). Donc une solution intermédiaire bâtarde:
Si on veut utiliser t threads
- trouver t-1 pivots, par exemple en prenant les 1000 premières lignes, en les triant, et en prenant les pivots espacés régulièrement (ça suppose que les données soient uniformes).
- utiliser juste l'algo de partition du quicksort pour placer ces pivots et construire une partition ...p1.....p2 ..... pt-1 ....
- plus qu'à trier en parallèle chaque sous partie
Ça tient la route pour un petit nombre de threads
Si on utilise tout ça (je copie pas le code ici, ça commence à grossir un peu...) :
Sans thread, fichier toujours terminé par \n, juste une lecture plus propre :
# time nice -n -20 ./sortfile -v toto /dev/null
Reading from 'toto'...
Read 4000000 lines.
Sorting...
Writting output to '/dev/null'...
Stats:
comparisons: 82698297
read time: 0.870s
sort time: 5.761s
write time: 1.528s
Cleaning...
real 0m8.195s
user 0m7.768s
sys 0m0.364s
1s de moins déjà :)
Avec 2 threads :
# time nice -n -20 ./sortfile -vt2 toto /dev/null
Reading from 'toto'...
Read 4000000 lines.
Sorting with 2 threads...
Writting output to '/dev/null'...
Stats:
comparisons: 84705684
read time: 0.885s
sort time: 3.464s
write time: 1.669s
Cleaning...
real 0m6.051s
user 0m8.789s
sys 0m0.384s
Enfin, 2 threads toujours, mais le même fichier avec les \n remplacés par des \0
# time nice -n -20 ./sortfile --zero --mmap -vt2 toto0 /dev/null
Reading from 'toto0'...
Read 4000000 lines.
Sorting with 2 threads...
Writting output to '/dev/null'...
Stats:
comparisons: 84705684
read time: 0.731s
sort time: 3.497s
write time: 1.681s
Cleaning...
real 0m5.930s
user 0m8.957s
sys 0m0.124s
La commande sort peut aller se cacher :)
Le code du programme simple :
#ifndef _GNU_SOURCE
# define _GNU_SOURCE
#endif
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include
#include <getopt.h>
#include <string.h>
static int verbose = 0;
/* The string comparison function */
int (*str_compare)(const char *, const char *) = strcmp;
static char ** read_lines(FILE *in, size_t *length) {
char **lines, **tmp_lines;
size_t nlines = 0;
char *buf = NULL, *buf_cpy;
size_t buflen = 0;
size_t i;
ssize_t r;
if (*length < 1)
*length = 1000;
lines = malloc(*length * sizeof(char *));
if (lines == NULL) {
perror("malloc");
return NULL;
}
while (1) {
r = getline(&buf, &buflen, in);
if (r >= 0) {
// Remove the trailing \n or \r\n
if (r >2 && buf[r - 2] '\r' && buf[r - 1] == '\n') {
buf[r - 2] = '\0';
r -= 2;
}
else if (r >1 && buf[r - 1] '\n') {
buf[r - 1] = '\0';
r--;
}
if (r == 0) {
continue;
}
// Expand the array
if (*length == nlines) {
*length += 1000;
tmp_lines = realloc(lines, *length * sizeof(char *));
if (tmp_lines == NULL) {
perror("realloc");
for (i = 0; i < nlines; i++) {
free(lines[i]);
}
free(lines);
free(buf);
return NULL;
}
lines = tmp_lines;
}
// Copy the line from the getline buffer
buf_cpy = malloc(r + 1);
if (buf_cpy == NULL) {
perror("malloc");
for (i = 0; i < nlines; i++) {
free(lines[i]);
}
free(lines);
free(buf);
return NULL;
}
memcpy(buf_cpy, buf, r + 1);
lines[nlines] = buf_cpy;
nlines++;
}
else {
break;
}
}
*length = nlines;
free(buf);
return lines;
}
static void free_lines(char **lines, size_t len) {
size_t i;
for (i = 0; i < len; i++) {
free(lines[i]);
}
free(lines);
}
static int write_lines(FILE *out, char **lines, size_t len) {
size_t i;
int r;
for (i = 0; i < len; i++) {
r = fprintf(out, "%s\n", lines[i]);
if (r < 0) {
perror("fprintf");
return -1;
}
}
return 0;
}
// Basic comparison with str_compare
static int cmp_lines(const void *p1, const void *p2) {
return str_compare(*(char * const *) p1, *(char * const *) p2);
}
static void usage(const char *name) {
fprintf(stderr, "Usage: %s [OPTION]... input_file output_file\n\n", name);
fprintf(stderr, "Options:\n");
fprintf(stderr, " -h, --help "
"this help message\n");
fprintf(stderr, " -c, --coll "
"use 'strcoll' to order the lines\n");
fprintf(stderr, " -V, --vers "
"use 'strverscmp' to order the lines\n");
fprintf(stderr, " -v, --verbose "
"print progress messages to stderr\n\n");
fprintf(stderr, "Use "-" instead of the input or output file to use "
"respectively stdin or stdout.\n");
fprintf(stderr, "The default comparison function is 'strcmp'.\n");
}
int main(int argc, char *argv[]) {
int exit_status = EXIT_SUCCESS;
int opt;
const char *in_filename, *out_filename;
FILE *in_file, *out_file;
char ** lines;
size_t lines_length = 0;
const char *prog_name = argv[0];
struct option long_options[] = { { "help", 0, NULL, 'h' }, { "verbose", 0,
NULL, 'v' }, { "coll", 0, NULL, 'c' },
{ "vers", 0, NULL, 'V' }, { 0, 0, 0, 0 } };
while ((opt = getopt_long(argc, argv, "hcVv", long_options, NULL)) >= 0) {
switch (opt) {
case 'v':
verbose = 1;
break;
case 'h':
usage(prog_name);
exit(EXIT_SUCCESS);
break;
case 'c':
str_compare = strcoll;
break;
case 'V':
str_compare = strverscmp;
default:
usage(prog_name);
exit(EXIT_FAILURE);
break;
}
}
argv += optind;
argc -= optind;
if (argc != 2) {
usage(prog_name);
exit(EXIT_FAILURE);
}
in_filename = argv[0];
out_filename = argv[1];
if (strcmp(in_filename, "-") != 0) {
in_file = fopen(in_filename, "r");
if (in_file == NULL) {
perror("fopen");
exit(EXIT_FAILURE);
}
}
else {
in_file = stdin;
in_filename = "stdin";
}
if (strcmp(out_filename, "-") != 0) {
out_file = fopen(out_filename, "w");
if (out_file == NULL) {
perror("fopen");
exit(EXIT_FAILURE);
}
}
else {
out_file = stdout;
out_filename = "stdout";
}
if (verbose)
fprintf(stderr, "Reading from '%s'...\n", in_filename);
lines = read_lines(in_file, &lines_length);
if (lines == NULL) {
exit_status = EXIT_FAILURE;
goto close_end;
}
if (verbose) {
fprintf(stderr, " Read %zd lines.\n", lines_length);
}
if (verbose)
fprintf(stderr, "Sorting...\n");
qsort(lines, lines_length, sizeof(char *), cmp_lines);
if (verbose)
fprintf(stderr, "Writting output to '%s'...\n", out_filename);
if (write_lines(out_file, lines, lines_length) < 0) {
exit_status = EXIT_FAILURE;
goto free_end;
}
free_end:
if (verbose)
fprintf(stderr, "Cleaning...\n");
free_lines(lines, lines_length);
close_end:
fclose(in_file);
fclose(out_file);
return exit_status;
}
Dobel
[Une fois rien, c'est rien; deux fois rien, ce n'est pas beaucoup, mais pour trois fois rien, on peut déjà s'acheter quelque chose, et pour pas cher]
a aidé 98 internautes ce mois-ci