Tri alphabétique ultra rapide de chaines de caractères de longueur variable [Résolu]

Question

Posez votre question Signaler

Tri alphabétique ultra rapide de chaines de caractères de longueur variable [Résolu]

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

- 22 sept. 2009 à 21:43 - Dernière réponse : mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

- 2 févr. 2010 à 21:19

C Posez votre question Signaler

-- Bonjour,

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 ?

Merci --

Afficher la suite

A voir également:

20/33 réponses

Signaler Commenter la réponse de mslider

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

24 sept. 2009 à 10:24

3

Merci

--
Hum, j'en doute et je demande à voir.
--

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 194 internautes nous ont dit merci ce mois-ci

Signaler Commenter la réponse de mezaya

mezaya

Messages postés: 203
Date d'inscription: dimanche 18 mai 2003
Statut: Membre
Dernière intervention: 6 mars 2010

27 sept. 2009 à 14:26

3

Merci

défi relevé, met à disposition ton fichier source (avec les mots à trier) et je pense que l'on peut faire mieux en C.

Voili,Voilou

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 194 internautes nous ont dit merci ce mois-ci

Signaler Commenter la réponse de cs_rt15

cs_rt15

Messages postés: 3982
Date d'inscription: mardi 8 mars 2005
Statut: Modérateur
Dernière intervention: 7 novembre 2014

9 28 sept. 2009 à 14:03

3

Merci

Ah oui au fait... Mon code ci-dessus ne fonctionne que si le fichier en entrée se termine par un retour à la ligne.

...
GGGGATGTAGCTCAGATCGTATGCCGTCTTCTGCT[\n]
GGGGATGTAGCTCAGATCGTATGCCGTCTTCTGCT[\n]
GGGGATGTAGCTCAGATCGTATGCCGTCTTCTGCT[\n]

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 194 internautes nous ont dit merci ce mois-ci

Signaler Commenter la réponse de nickydaquick

nickydaquick

Messages postés: 417
Date d'inscription: vendredi 31 janvier 2003
Statut: Membre
Dernière intervention: 19 décembre 2013

1 23 sept. 2009 à 16:15

0

Merci

Salut,

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 ...!

Signaler Commenter la réponse de cs_Lucky92

cs_Lucky92

Messages postés: 180
Date d'inscription: mercredi 22 décembre 2004
Statut: Membre
Dernière intervention: 16 août 2012

2 27 sept. 2009 à 21:18

0

Merci

Salut mslider,

Je suis très impressionné par ta vitesse !
Quelles sont les caractéristiques de ta machine ( architecure cpu, vitesse, mémoire,... ) ?

Cordialement.

Signaler Commenter la réponse de cs_rt15

cs_rt15

Messages postés: 3982
Date d'inscription: mardi 8 mars 2005
Statut: Modérateur
Dernière intervention: 7 novembre 2014

9 28 sept. 2009 à 12:11

0

Merci

Salut,

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;
}

Signaler Commenter la réponse de mslider

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

28 sept. 2009 à 12:33

0

Merci

-- Oui salut rt15 et les autres,

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 ?

slider --

Signaler Commenter la réponse de cs_rt15

cs_rt15

Messages postés: 3982
Date d'inscription: mardi 8 mars 2005
Statut: Modérateur
Dernière intervention: 7 novembre 2014

9 28 sept. 2009 à 13:59

0

Merci

tri à bulles -> Gné ? Il est très facile à implémenté, mais il est très lent.

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.

Signaler Commenter la réponse de cs_rt15

cs_rt15

Messages postés: 3982
Date d'inscription: mardi 8 mars 2005
Statut: Modérateur
Dernière intervention: 7 novembre 2014

9 28 sept. 2009 à 14:04

0

Merci

Au fait aussi, quel résultat par rapport au pascal sur ta machine ?

Signaler Commenter la réponse de mslider

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

28 sept. 2009 à 14:23

0

Merci

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.

Signaler Commenter la réponse de mslider

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

28 sept. 2009 à 14:30

0

Merci

encore mieux: 5s

compilé sous Windows avec Code::Blocks v1.0, sur mon PC de bureautique (Intel Bi-core 3Ghz, 4Go de RAM).

Signaler Commenter la réponse de cs_rt15

cs_rt15

Messages postés: 3982
Date d'inscription: mardi 8 mars 2005
Statut: Modérateur
Dernière intervention: 7 novembre 2014

9 28 sept. 2009 à 14:32

0

Merci

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.

Signaler Commenter la réponse de mslider

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

28 sept. 2009 à 14:45

0

Merci

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.

Signaler Commenter la réponse de mslider

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

29 sept. 2009 à 15:08

0

Merci

oui je m'en suis aperçu qd j'ai vu ta fonction compare.

Au fait il marche pour 4 millions de lignes, mais pour 80 millions de lignes:

Debut de lecture : 14:56:07
Fin de lecture : 14:56:31
Nombre de lignes : 82332600
Fin de tri : 14:58:59
Unable to allocate output buffer

il passe l'étape du tri, mais après ya un probleme d'allocation mémoire pour envoyer la sortie.
il renvoit pas de segmentation fault.

Signaler Commenter la réponse de cs_rt15

cs_rt15

Messages postés: 3982
Date d'inscription: mardi 8 mars 2005
Statut: Modérateur
Dernière intervention: 7 novembre 2014

9 29 sept. 2009 à 15:28

0

Merci

il renvoit pas de segmentation fault.

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.

Signaler Commenter la réponse de mslider

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

29 sept. 2009 à 18:01

0

Merci

--
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.
--

Signaler Commenter la réponse de mslider

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

29 sept. 2009 à 18:06

0

Merci

--
pour info en perl:

#!/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é

--

Signaler Commenter la réponse de mslider

mslider

Messages postés: 109
Date d'inscription: jeudi 21 octobre 2004
Statut: Membre
Dernière intervention: 7 mars 2010

29 sept. 2009 à 18:37

0

Merci

adresse du fichier source: http://dl.free.fr/vvV6ngwWR

Signaler Commenter la réponse de cs_Dobel

cs_Dobel

Messages postés: 333
Date d'inscription: dimanche 25 mai 2003
Statut: Membre
Dernière intervention: 23 novembre 2009

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;
}

et le code utilisé pour les derniers essais : http://pastebin.com/f1fceff27

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]

Répondre Posez votre question

1 2 Suivant

mslider · Accepted Answer · 2009-09-23T10:22:45+0200

- 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.

Tri alphabétique ultra rapide de chaines de caractères de longueur variable [Résolu]

Votre réponse