Partage
  • Partager sur Facebook
  • Partager sur Twitter

Optimisation d'algorithme

Lecture de fichier et distance minimale dans un tableau

Sujet résolu
    13 juin 2021 à 1:01:57

    Bonjour, 

    L'exercice que j'essaie de faire consiste en la lecture d'un fichier texte qui ne contient que des mots, espacés d'un point virgule, et non ordonnés (ex: "6;2;1;8"). Je dois identifier la distance minimale entre deux nombres de ce fichier (la plus petite valeur absolue obtenue en faisant une différence entre deux nombres), et donner ces deux nombres.

    Par exemple, si la suite de mots est 3;5;27;65;4;90 , le résultat de la distance est 1, et les deux nombres sont 3 et 4.

    L'algorithme que j'ai fait consiste à lire le fichier et tout stocker dans une liste gérée dynamiquement, puis trier cette liste avec qsort. Ensuite, je fais des différences successives entre deux nombres qui se suivent et je donne la plus petite trouvée. 

    Le code ci-dessous:

    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <time.h>
    #include <math.h>
    
    //Fonction de comparaison pour qsort
    int cmpInt (const void *a, const void *b){
      return ( *(int*)a - *(int*)b );
    }
    
    //Fonction principale
    void distanceMinimale(char* nomFichier){
        //Ouverture de fichier,initialisation des variables
        FILE* fichier = NULL;
    	fichier = fopen(nomFichier, "r");
    	assert(fichier!=NULL);
    
    	int nombreMots=0,a=0,min=-1,indice=0,res=1000;
    	int* tableau=NULL;
    
    
    	while(fgetc(fichier)!=EOF){
            //fgetc avance d'un caractère dans le fichier, donc je recule avant de lire
            fseek(fichier,-1,SEEK_CUR);
    
            //A chaque lecture, j'incrémente le nombre de mots et modifie le tableau
    	    nombreMots++;
            tableau = (int*)realloc(tableau,nombreMots*sizeof(int));
            assert(tableau!=NULL);
    
            fscanf(fichier,"%d;",&a);
            tableau[nombreMots-1]=a;
    
    	}
    
        //Tri du tableau
    	qsort(tableau,nombreMots,sizeof(int),cmpInt);
    
    	//On cherche la distance minimale
        for (int i = 1 ; i < nombreMots; i++){
            min= tableau[i]-tableau[i-1];
            if (min<res){
                indice=i;
                res=min;
            }
        }
        printf("La distance minimale trouvee est de %d, avec le couple(%d,%d)",res,tableau[indice-1],tableau[indice]);
    
    
    
    }
    
    
    int main(){
    
        clock_t start, end;
        double cpu_time_used;//Pour déterminer le temps de traitement
    
        start = clock();
        distanceMinimale("test.txt");
        end = clock();
    
        cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
        printf("\nTEMPS MIS: %lf",cpu_time_used);
    
    
    
    }
    

    Mon premier soucis concerne la lecture de fichier : existe t-il un moyen de savoir si le prochain caractère est, ou non, l'EOF, sans avoir à utiliser fgetc, ou une fonction qui déplace le parseur? J'avais utilisé un while(!feof(fichier)) au début, mais il ne détectait pas la fin et lisait le dernier chiffre du fichier deux fois. Mon résultat de distance minimale était toujours 0, du coup...

    Mon second souci  est d'optimiser cet algo afin de le rendre plus rapide (il est encore trop lent lorsque le fichier contient beaucoup de nombre...). Si vous avez des suggestions et/ou retours pour le rendre plus rapide, j'en serais très reconnaissante. Merci !!!

    -
    Edité par A_Ado_ 13 juin 2021 à 1:03:23

    • Partager sur Facebook
    • Partager sur Twitter
      13 juin 2021 à 1:48:02

      Bonsoir,

      alors il faut bien différencier deux choses : l'algorithme et l'implémentation.

      Le squelette de ton algorithme (lecture puis tri puis recherche) est à ma connaissance optimal en complexité temporelle (avec un algo de tri optimal). Si on utilise un tri classique (comme quicksort ou ce qui est implémenté via qsort) tu auras un algo en O(n log n).

      Ton implémentation souffre de nombreux défauts.

      • ton histoire de while (!feof(...)) est une erreur (normal pour un débutant). Ce n'est pas une bonne façon de faire .
        ton histoire avec les fgetc n'est pas une bonne idée non plus … trop lourd.
        le plus simple est de n'utiliser que fscanf (par exemple) :


        while (fscanf("%d;", &n)==1) {
           blablabla
        }
        je te laisse consulter la doc fscanf pour en comprendre un peu le fonctionnement ; la partie return value te sera utile ;

      • faire une reallocation à chaque lecture est une mauvaise idée (point de vue performances). Il vaut mieux utiliser (après l'avoir implémenté) un tableau à croissance dynamique qui permet d'avoir de bonnes performances en temps amorti. Le lien est l'un des premiers fourni avec une recherche google ;

      • il faut arrêter les assert ! assert ne doit s'utiliser que pour se prémunir d'une erreur d'utilisation d'API et non comme un check runtime. Au runtime on utilise des if ;

      • tu utilises mal realloc car si la réallocation échoue alors la fonction te renvoie NULL et ton précédent pointeur est perdu sans compter le gros crash qui va s'en suivre → il faut toujours vérifier si les allocations réussissent  (et pas avec assert). Cela signifie qu'il faut l'utiliser ainsi :

        if ( (tmp=realloc(array, new_size)) == NULL ) {
            la réallocation a échouée il faut traiter l'erreur
        } else {
           array=tmp;
        }
        
      • écrire et utiliser des fonctions c'est toujours mieux. Une indication : si tu es obligé d'écrire un commentaire alors c'est le signe que ton code est mal foutu et qu'il faut opter pour une granularité plus fine ;

      • utiliser des dénominations claires c'est sympa aussi. À moins que dans ton contexte mot signifie un nombre sur 2 octets, nombre est un vocable préférable ;

      • histoire d'être propre : à chaque allocation doit correspondre une libération et une seule ; je n'en vois aucune dans ton code ;

      Voilà quelques remarques sur ton code.

      En général si on essaye d'optimiser un code, on commence par faire un code fonctionnel puis on utilise un profiler (comme gprof par exemple) qui va te permettre d'identifier les goulets d'étranglements et par là même t'indiquer où une optimisation sera le plus efficace.

      Ensuite tu peux tester d'autres approches … d'un point de vue algorithmique :

      Au lieu d'insérer en fin de tableau pendant la lecture, tu pourrais essayer d'insérer au bon endroit pour obtenir dès la fin un tableau trié. Pourquoi ne pas essayer aussi d'autres structures de données comme des arbres de recherche équilibrés (que tu pourrais éventuellement implémenter sous forme de tableau en C) ?

      Cette approche te permettrait également de mettre fin au programme avant la lecture de tous les éléments dès la découverte du premier doublon.

      Avoir une idées des données te permettrait peut-être aussi d'adapter ton algo …

      Enfin bref, si tu as des questions ou si tu as besoin de plus de détails n'hésite pas.

      Edit :

      ah oui … j'oubliais …

      mais on y reviendra peut-être plus tard … tu peux demander au compilateur de créer une version optimisée pour le temps d'exécution … mais c'est une autre histoire.

      -
      Edité par White Crow 13 juin 2021 à 1:54:26

      • Partager sur Facebook
      • Partager sur Twitter
        13 juin 2021 à 2:22:39

        Salut, (White Crow m'a doublé ...)
        Si ton fichier est formé de plusieurs lignes et que tu sais la longueur de la ligne la plus longue, pourquoi ne pas utiliser fgets() plutôt que fgetc() ?
        Réserve-toi un tableau de char pour recevoir tes lignes.
        Tu convertis in-line avec fscanf, tu pourrais remplacer par sscanf sur la ligne lue à la position du premier caractère de chaque nombre.
        J'ai cru comprendre que tu fais un realloc pour chaque nombre trouvé. Ai-je bien compris?
        C'est très dur sur la mémoire dynamique et long à exécuter.
        Fais un malloc de 1024 mots (ou nombres) et vérifie ta limite, et fais un realloc de la longueur courante + 1024 quand tu atteint cette limite.
        Je dis 1024, mais ça pourrait être n'importe quel nombre assez grand sans être excessif.
        Si tu ne connais pas la longueur de chaque ligne ou si c'est une seule ligne immense, lis tout le fichier d'un seul coup.
        Tu fais un fseek() sur le EOF et un ftell() qui te dis la longueur. Puis un fseek() pour retourner au début.
        Tu réserve avec malloc l'espace pour tout le fichier et tu lis avec fread().
        Tu mets un '\0' à la fin (donc réserve de la place pour lui)
        Ensuite, tu avance dans le tableau à peu près comme tu le fais
        Le sscanf s'arrêtera au premier caractère non numérique.
        Quand tu sautes au suivant, tu dois t'arrêter au dela de ';' ou '\n' mais ne pas dépasser le '\0'
        Je ne sais pas quelle stratégie tu utiliseras, je t'ai donné quelques pistes.
        • Partager sur Facebook
        • Partager sur Twitter

        Le Tout est souvent plus grand que la somme de ses parties.

          13 juin 2021 à 9:22:51

          Salut,

          Quelques fonctions sur les tables dynamiques en français.

          Après, je ne me donnerais pas plus de mal que ça. J'allouerais direct un bon paquet dès le départ en mesurant la taille du fichier :

          size_t CEV_fileSize(FILE* file)
          {/*size of a file as bytes*/
          
              long pos = ftell(file),
                   size = 0;
          
              fseek(file, 0, SEEK_END);
          
              size = ftell(file);
          
              fseek(file, pos, SEEK_SET);
          
              return(size);
          }

          Globalement, tu malloc( fileSize(myFile) ) et tu devrais être bon. Comme un mot compte 2 octets et que le ficher alterne une valeur et un char inutile, tu devrais retomber sur tes pieds. Tu auras même un peu de gras alimenté par les nombres à plusieurs digits.

          Bonne continuation.

          PS : autre façon de faire qui évite de trier et tout ça. En fait, on se fiche complètement de stocker toutes les valeurs. On alloue direct 66Ko (un octet par valeur (65 536)) qu'on memset à 0 (on qu'on calloc(), mon préféré).

          Quand on lit une valeur, on passe l'index de la valeur lue à 1 du genre table[readValue()] = 1;

          Un fois fini, un rapide scan de la table permettra de compter les case vides consécutives nous donnant le plus petit écart trouvé. S'il y a des nombres négatifs, il suffit d'ajouter un offset de 0x8000 à l'index.

          C'est valable avec des mots, si ont passe à des volumes supérieurs, ça devient moins valable, on ne va pas allouer 4Go pour le faire avec des doubles mots, mais 65Ko est un volume tout à fait raisonnable. Aucun doute que sans un qsort, ce genre d'algo va terrasser le tiens en temps d'exécution.

          Re-edit : J'ai fait mon algo, avec une mesure au clock(), j'ai 0 avec un CLOCK_PER_SEC de 1000... donc moins d'une milliseconde, ouverture de fichier et allocation comprises.

          Le fichier :

          45;87;9;75;-21210;145;9999;-6621;21;1012;8457;875;-3214;666;1235;-7542;0;32767;-32768;-3215

          Le résultat :

          ecart mini de 1 entre -3215 et -3214
          demarre a 0, fini a 0 pour une duree de 0 ms
          
          Process returned 0 (0x0)   execution time : 0.038 s
          Press any key to continue.




          -
          Edité par drx 13 juin 2021 à 12:02:51

          • Partager sur Facebook
          • Partager sur Twitter

          Stringman devient Bonhomme !! | Jeux de plateforme : Nouvelle Démo. (màj : 24/04/2021)

            14 juin 2021 à 12:29:37

            Puisque c'était dans la question initiale de A_Ado_ : dans la bibliothèque standard il y a ungetc() qui est effectivement un moyen, de (re)mettre dans le tampon du flux de lecture un char qui sera lu au prochain appel à une fonction fgetc().

            https://www.cplusplus.com/reference/cstdio/ungetc/

            C'est dans le standard depuis l'origine, mais la plupart du temps on fait mieux en faisant autrement et c'est le cas aussi dans le cas présent, en s'inspirant des suggestions faites par les autres contributeurs.

            • Partager sur Facebook
            • Partager sur Twitter
              14 juin 2021 à 15:10:49

              Alors, je voudrais déja commencer par vous remercier infiniment ! Vous m'avez tous énormément aidé !!!

              Pour plus de précision le fichier est composé d'une seule longue ligne. Chaque nombre est suivi d'un point virgule, même le dernier.

              Du coup, pour un récapitulatif des modifications que je vais appliquer :

              - Je vais retirer les assert et les remplacer par des clauses if/else.

              - Utiliser plus de sous-fonctions et mettre des dénominations plus claires

              - J'utiliserai un unique fscanf pour la lecture des nombres successifs 

              - Pour le traitement dynamique, j'essaierai d'implémenter un tableau à croissance dynamique ( question : est-il "meilleur" qu'une liste chaînée ?). Pour éviter au max les realloc j'appliquerai la proposition de @PierrotLeFou en essayant de calculer le nombre de chiffres d'abord avec un fseek(), pour pouvoir créer un tableau avec une taille connue et une seule allocation, et le remplir ensuite.

              Les autres options consistent à faire une allocation pour un grand nombre de cases, et ensuite faire une reallocation lorsque nécessaire. Dans le pire des cas, on se retrouve quand même à en faire beaucoup, et je ne pense pas que lire le fichier deux fois soit plus "prenant" pour ma machine.

              Je libèrerai ensuite tout ce qui a été créé dynamiquement.

              - Quant à l'ordre de stockage, je vais implémenter les deux options (stocker les nombres comme lus, puis tri rapide ou placer le nombre à la bonne place en l'insérant) et ensuite choisir celle qui me semble la plus rapide. Je penche un peu plus pour la première quand même, parce que dans le second cas, je dois lire toute la partie remplie de mon tableau à chaque entrée.

              White Crow a écrit:

              En général si on essaye d'optimiser un code, on commence par faire un code fonctionnel puis on utilise un profiler (comme gprof par exemple) qui va te permettre d'identifier les goulets d'étranglements et par là même t'indiquer où une optimisation sera le plus efficace.

              Ca, je n'etais pas au courant... Ni pour le fait de demander au compilateur de créer une version optimisée; je vais "Googler" ça :)

              drx a écrit:

              PS : autre façon de faire qui évite de trier et tout ça. En fait, on se fiche complètement de stocker toutes les valeurs. On alloue direct 66Ko (un octet par valeur (65 536)) qu'on memset à 0 (on qu'on calloc(), mon préféré).

              Quand on lit une valeur, on passe l'index de la valeur lue à 1 du genre table[readValue()] = 1;

              Un fois fini, un rapide scan de la table permettra de compter les case vides consécutives nous donnant le plus petit écart trouvé. S'il y a des nombres négatifs, il suffit d'ajouter un offset de 0x8000 à l'index.

              C'est valable avec des mots, si ont passe à des volumes supérieurs, ça devient moins valable, on ne va pas allouer 4Go pour le faire avec des doubles mots, mais 65Ko est un volume tout à fait raisonnable. Aucun doute que sans un qsort, ce genre d'algo va terrasser le tiens en temps d'exécution.

              Re-edit : J'ai fait mon algo, avec une mesure au clock(), j'ai 0 avec un CLOCK_PER_SEC de 1000... donc moins d'une milliseconde, ouverture de fichier et allocation comprises.

              Merci, cette idée m'a l'air un peu plus dure pour mon niveau mais je vais l'essayer :) J'ai un fichier test d'un peu plus de 2200 Ko. Par contre, si j'ai bien compris, cette implémentation nécessite de savoir quel est le plus grand nombre du document, non ?

              Du coup, j'y vais améliorer mon code, et je reviendrai avec les résultats. Merci encore  !



              • Partager sur Facebook
              • Partager sur Twitter
                14 juin 2021 à 17:53:36

                Évites à tout prix les listes chaînées, elles sont lourdes à supporter en temps et en espace.
                Ce que je suggère est d'utiliser fseek pour trouver la longueur du fichier, pas le nombre de chiffres.
                Tu n'as pas besoin de lire le fichier deux fois. Lis-le en entier une fois.
                Tu peux le parcourir deux fois si tu veux connaître le nombre de chiffres et faire une seule allocation pour tous les chiffres.
                (j'utilise 'chiffre' car nombre de nombre sonne bizarre ...)
                Insérer le nombre à la bonne place suppose la construction d'un arbre de recherche binaire balancé, et ce n'est pas évident.
                Je suggère de garder ton squicksort.
                Le truc de drx suppose en effet que tu saches la grandeur du plus grand nombre et s'il y en a de négatifs.
                • Partager sur Facebook
                • Partager sur Twitter

                Le Tout est souvent plus grand que la somme de ses parties.

                  14 juin 2021 à 22:34:03

                  Salut,

                  Non, il n'est pas nécessaire de connaitre la plus grande valeur, ce sont des 16 bits, donc la plus grande valeur sera au pire 65535.

                  Tu dis optimiser mais pas optimiser quoi. En général, il faut choisir : rapide c'est utiliser de la mémoire, économiser de la mémoire est lent.

                  Pour faire rapide, J'alloue en masse, 65536 octets, ce n'est pas la mort non-plus, ça passerait même sur un CPC 6128.

                  J'ai obtenu 3ms (au clock() comme tu le fais) avec un fichier contenant 20 000 valeurs. Avec des négatifs, mais ça c'est un détail. Une translation est conservative, donc ajouter un offset à toutes les valeurs n'en change pas la différence, on est d'accord qu'il y a une différence de 3 entre 4 et 7 et que si j'ajoute 10, il y a toujours une différence de 3 entre 14 et 17. Traiter les valeur négatives, c'est faire un glissement de 32768 pour ramener la plus petite valeur possible à 0, qui est le premier index de la table.

                  Je te laisse faire ton exercice, puis je montrerai ce que j'ai fait.

                  Bonne continuation.

                  • Partager sur Facebook
                  • Partager sur Twitter

                  Stringman devient Bonhomme !! | Jeux de plateforme : Nouvelle Démo. (màj : 24/04/2021)

                    15 juin 2021 à 3:27:38

                    @drx:
                    Je n'ai vu nulle part que le nombre le plus grand n'avait que 16 bits. Bon, ce n'est pas si grave.
                    @A_ado_:
                    Je me suis mal exprimé quand j'ai dit qu'on pourrait lire le fichier deux fois.
                    Je voulais dire qu'on lit tout le fichier d'un seul coup. Si tu as 2200Kb, ce n'est pas la fin du monde.
                    Mais plutôt qu'on pouvait parcourir cet espace de mémoire deux fois si on souhaite connaître combien de nombres il y a, et quel est le plus grand.
                    Petites statistiques bêtes pour 2200Kb:
                    Nombre de 1 chiffre: 1126400 
                    Nombre de 2 chiffres: 750933 
                    Nombre de 3 chiffres: 563200 
                    Nombre de 4 chiffres: 450560 
                    Nombre de 5 chiffres: 375466 
                    Dans tous les cas, on peut s'attendre à plusieurs répéttitions.
                    • Partager sur Facebook
                    • Partager sur Twitter

                    Le Tout est souvent plus grand que la somme de ses parties.

                      15 juin 2021 à 9:16:57

                      Salut,

                      A_Ado_ a écrit:

                      [...] ne contient que des mots, espacés d'un point virgule[...]

                      Comme il dit "des mots" j'en conclu que le terme désigne des 16 bits (octet, mot, double mot, mot long). Je suppose qu'il aurait dit des "nombres" sinon, parce que ce ne sont clairement pas des "mots" du langage écrit.

                      • Partager sur Facebook
                      • Partager sur Twitter

                      Stringman devient Bonhomme !! | Jeux de plateforme : Nouvelle Démo. (màj : 24/04/2021)

                        15 juin 2021 à 17:51:30

                        De toute façon, sur un intervalle de 65536, avec un minimum de 375000 nombres, il y aura forcément beaucoup de répétitions.
                        On peut presque présumer à coup sûr que la distance minimale sera de 1.
                        Mais il faut faire son devoir correctement et le vérifier ...t

                        • Partager sur Facebook
                        • Partager sur Twitter

                        Le Tout est souvent plus grand que la somme de ses parties.

                          15 juin 2021 à 18:40:01

                          Si je rempli mon fichier de 30 000 valeurs random (~180Ko), l'écart mini mesuré alterne entre 1 et 2... Si on extrapole à la grosse, sont fichier faisant 2.2 Mo, on est effectivement pas loin des 360 000 valeurs. Le temps est variable vu que j'ai décidé de break la boucle de recherche quand je trouve 1 en écart, puisque c'est manifestement la plus petite valeur admissible.

                          S'il y a vraiment 375 000 valeurs parmi 65536, ça devient plus un problème de probabilités que de mesure, c'est certain. Les chances ne ne pas avoir 2 valeurs consécutives doivent être très faibles.

                          Sauf si le PO n'a pas utilisé le terme "mot" comme je l'entend (ce n'est pas que moi, c'est une convention), auquel cas la probabilité est moindre et mon algo n'est plus valable.

                          Mais bon, passer 300 000+ valeurs sans répétition au qsort, ça va couter un bras...

                          • Partager sur Facebook
                          • Partager sur Twitter

                          Stringman devient Bonhomme !! | Jeux de plateforme : Nouvelle Démo. (màj : 24/04/2021)

                            15 juin 2021 à 18:46:44

                            En supposant qu'on aurait plus de 300 mille valeurs différentes, tu as un truc plus rapide que le quicksort?
                            • Partager sur Facebook
                            • Partager sur Twitter

                            Le Tout est souvent plus grand que la somme de ses parties.

                              15 juin 2021 à 18:47:36

                              drx a écrit:

                              Si je rempli mon fichier de 30 000 valeurs random (~180Ko), l'écart mini mesuré alterne entre 1 et 2... Si on extrapole à la grosse, sont fichier faisant 2.2 Mo, on est effectivement pas loin des 360 000 valeurs. Le temps est variable vu que j'ai décidé de break la boucle de recherche quand je trouve 1 en écart, puisque c'est manifestement la plus petite valeur admissible.

                              Je comprends le sujet différemment, pour moi les valeurs sont quelconques (négatives ou positives) et rien n'interdit d'avoir plusieurs fois la même valeur.

                              drx a écrit:

                              [...]
                              S'il y a vraiment 375 000 valeurs parmi 65536, ça devient plus un problème de probabilités que de mesure, c'est certain. Les chances ne ne pas avoir 2 valeurs consécutives doivent être très faibles.

                              Nulles → principe du tiroir 375 000 valeurs parmi 65536 ça fait au moins une valeur présente au minimum 5 fois.

                              drx a écrit:

                              [..]

                              Sauf si le PO n'a pas utilisé le terme "mot" comme je l'entend (ce n'est pas que moi, c'est une convention), auquel cas la probabilité est moindre et mon algo n'est plus valable.

                              Mais bon, passer 300 000+ valeurs sans répétition au qsort, ça va couter un bras...

                              ouais je lui en faisais la remarque à mon premier message … mais a priori une machine moderne doit pouvoir avoir des temps plus que raisonnables pour trier 300 000+ valeurs.

                              • Partager sur Facebook
                              • Partager sur Twitter
                                15 juin 2021 à 19:28:57

                                Re,

                                Oui, j'ai vu que tu avais réagi au terme "mot", ça me conforte dans le fait qu'on est d'accord, et je suis parti là-dessus, même si le PO n'a pas relevé.. Mais j'ai bien précisé tout du long que c'est pour des valeurs 16 bits.

                                Qu'il y ait des valeurs négatives ou pas ne change rien dans mon algo : si ce sont vraiment des 16 bits, il n'y a quand-même qu'un nombre très limité de valeurs.

                                J'essayais juste de me passer du qsort en classant à la volée lors de la lecture. Pas de qsort me semble plus rapide qu'avec, même s'il performe, je n'ai besoin que de deux scans (remplir, relire) d'une table de 65536, pas de scans multiples d'une table de 360 000+...

                                • Partager sur Facebook
                                • Partager sur Twitter

                                Stringman devient Bonhomme !! | Jeux de plateforme : Nouvelle Démo. (màj : 24/04/2021)

                                  16 juin 2021 à 4:45:57

                                  Je me suis fait un petit test avec l'algo de drx et trouver l'intervalle minimum (qui est toujours 1). Ça  se fait en un temps ridicule, moins de 1 ms.
                                  J'utilise un tableau de char, après tout ce ne sont que des flags.
                                  Je remplis aléatoirement et je suis allé jusqu'à 10 millions en moins de 150 ms.
                                  • Partager sur Facebook
                                  • Partager sur Twitter

                                  Le Tout est souvent plus grand que la somme de ses parties.

                                    16 juin 2021 à 20:47:00

                                    Salut,

                                    Bon, pas de nouvelle du PO, je pense pouvoir poster :

                                    void testFct(void)
                                    {
                                        const bool useNegVal = true; //avec ou sans valeur négatives
                                        uint16_t offset = useNegVal? 0x8000u : 0;
                                    
                                    
                                        FILE *myFile = fopen("test.txt", "w");
                                    
                                        if(!myFile)
                                        {
                                            printf("could not create file %s.\n", strerror(errno));
                                            return;
                                        }
                                    
                                        srand(time(NULL));
                                    
                                        //création d'un fichier bidon...
                                        for(int i = 0; i < 30000; i++)
                                            fprintf(myFile, "%d;", rand() + rand() - offset);//RAND_MAX de 0x7FFF chez moi
                                    
                                        fclose(myFile);//je referme pour inclure l'ouverture dans le temps de traitement
                                    
                                        clock_t start = clock();
                                        myFile = fopen("test.txt", "r");
                                    
                                        if(!myFile)
                                        {
                                            printf("could not open file %s.\n", strerror(errno));
                                            return;
                                        }
                                    
                                        char *stock = calloc(MAXWORD + 1, 1);
                                    
                                        if(!stock)
                                        {
                                            printf("could not alloc %s.\n", strerror(errno));
                                            return;
                                        }
                                    
                                        int value;
                                    
                                        while(fscanf(myFile, "%d;", &value) == 1)
                                            stock[value + offset] = true; //+0x8000 si nombres négatifs dans la liste
                                    
                                        int last = 0;
                                        //on va à la première occurence d'une valeur existante
                                        while(!stock[last])
                                            last++;
                                    
                                        int dif = MAXWORD,
                                            min, max;
                                    
                                        for(int i = last+1; i <= MAXWORD; i++)
                                        {//à partie de là, on compte...
                                            if(stock[i])
                                            {
                                                if((i - last) < dif)
                                                {
                                                    min = last;
                                                    max = i;
                                                    dif = i - last;
                                                }
                                    
                                                last = i;
                                            }
                                    
                                            if(dif == 1)//il n'y aura pas plus petit que 1 de différence, on arrête de chercher
                                                break;
                                        }
                                    
                                        fclose(myFile);
                                    
                                        clock_t stop = clock();
                                        printf("ecart mini de %d entre %d et %d\n", dif, min-offset, max-offset);
                                        printf("demarre a %u, fini a %u pour une duree de %u ms\n", start, stop, stop-start);
                                    
                                    
                                    }


                                    Voilà voilà... pas très compliqué, j'ai peut-être peiné à m'expliquer clairement...

                                    Bonne continuation.

                                    -
                                    Edité par drx 16 juin 2021 à 20:47:48

                                    • Partager sur Facebook
                                    • Partager sur Twitter

                                    Stringman devient Bonhomme !! | Jeux de plateforme : Nouvelle Démo. (màj : 24/04/2021)

                                      16 juin 2021 à 23:59:58

                                      Rebonsoir !

                                      L'emploi du terme "mot" était une erreur, je confondais un peu cet exercice avec un autre de lecture de fichier de mots et c'est pour cela. Je ne savais pas qu'un mot désignait une donnée de 16 bits :')

                                      Du coup, j'ai modifié le code et maintenant, je parcours le fichier deux fois : une première fois pour compter le nombre de chiffres, et une seconde pour les lire un à un et les stocker dans un simple tableau créé par calloc.

                                      Grâce à vos conseils, j'ai quand même un gain de +90% en rapidité !!

                                      Voici la seconde version du code ( j'ai gardé le tri rapide):

                                      #include <stdio.h>
                                      #include <stdlib.h>
                                      #include <assert.h>
                                      #include <time.h>
                                      #include <math.h>
                                      
                                      //Fonction de comparaison pour qsort
                                      int cmpInt (const void *a, const void *b){
                                        return ( *(int*)a - *(int*)b );
                                      }
                                      
                                      int nombreChiffres(char* nomFichier){
                                          int compteur=0,n=0;
                                          FILE* fichier = NULL;
                                      	fichier = fopen(nomFichier, "r");
                                      	if(fichier==NULL){
                                              printf("Erreur ouverture fichier");
                                              exit(EXIT_FAILURE);
                                      	}
                                      	else{
                                      	    while(fscanf(fichier,"%d;",&n)==1){
                                                  compteur++;
                                      	    }
                                      	}
                                      	fclose(fichier);
                                      	return compteur;
                                      }
                                      
                                      
                                      int* creationTableau(char* nomFichier,int* nbChiffres){
                                      
                                          (*nbChiffres)=nombreChiffres(nomFichier);
                                          int* tableau=NULL;
                                          FILE* fichier = NULL;
                                      	fichier = fopen(nomFichier, "r");
                                      	if(fichier==NULL){
                                              printf("Erreur ouverture fichier");
                                              exit(EXIT_FAILURE);
                                      	}
                                      	else{
                                              int i=0,n;
                                              tableau = (int*)calloc((*nbChiffres),sizeof(int));
                                              if(tableau==NULL){
                                                  printf("Erreur allocation dynamique");
                                                  exit(EXIT_FAILURE);
                                              }
                                              else{
                                                  //rewind(fichier);
                                                  //printf("TEST");
                                                  while (fscanf(fichier,"%d;",&n)==1) {
                                      	        tableau[i]=n;
                                      	        i++;
                                                  }
                                              }
                                      
                                              //Tri du tableau
                                              qsort(tableau,(*nbChiffres),sizeof(int),cmpInt);
                                              fclose(fichier);
                                      
                                      	}
                                      	return tableau;
                                      }
                                      
                                      void rechercheDistanceMinimale(int* tableau,int tailleTableau){
                                          int res=1000,indice,min;
                                          for (int i = 1 ; i < tailleTableau; i++){
                                              min= tableau[i]-tableau[i-1];
                                              if (min<res){
                                                  indice=i;
                                                  res=min;
                                              }
                                          }
                                      
                                          printf("La distance minimale trouvee est de %d, avec le couple(%d,%d)",res,tableau[indice-1],tableau[indice]);
                                      
                                      
                                      }
                                      
                                      
                                      
                                      
                                      int main(){
                                      
                                          int nbChiffres;
                                          clock_t start, end;
                                          double cpu_time_used;
                                          start = clock();
                                      
                                          int* tab=creationTableau("numbers.txt",&nbChiffres);
                                          rechercheDistanceMinimale(tab,nbChiffres);
                                      
                                          end = clock();
                                          cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
                                          printf("\nTEMPS MIS: %lf\n",cpu_time_used);
                                      
                                          free(tab);
                                      
                                      
                                      
                                      }
                                      



                                      -
                                      Edité par A_Ado_ 17 juin 2021 à 0:00:41

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        17 juin 2021 à 2:35:25

                                        Je constate que tu as choisi de lire le fichier deux fois plutôt que de le lire une seule fois tout d'un coup.
                                        Tu disais qu'il avait 2200 Kb, soit 2.2 millions de caractères.
                                        Je ne sais pas ce que tu aurais gagné en temps cpu, mais le temps réel aurait passablement diminué.
                                        Le calloc que tu fais pour les nombres prend probablement plus de place.
                                        Si tu changes d'idée, drx a donné le truc pour trouver la longueur exacte du fichier (voir mon commentaire).
                                        Tu pourrait afficher le nombre le plus grand et le plus petit (positif ou négatif) et combien de nombres il y a dans le fichier.
                                        Il y a bien sûr quelques améliorations mineures que tu pourrais apporter, mais dans l'ensemble, c'est assez bien.
                                        + assert.h pourrait être éliminé.
                                        + si tu choisis d'ouvrir le fichier deux fois, pourquoi ne pas le faire dans une petite fonction (moins de code).
                                        Tu aurais intérêt à faire un rewind plutôt que de faire deux fopen / fclose
                                        + Initialisation inutile (il y en a quelques unes):
                                         FILE* fichier = NULL;
                                            fichier = fopen(nomFichier, "r");
                                        Peut être remplacé par:
                                         FILE* fichier = fopen(nomFichier, "r");
                                           + combiner deux instructions:
                                         tableau[i]=n;
                                                    i++;
                                        donne:
                                         tableau[i++]=n;
                                        + fais le fclose du fichier avant le qsort.
                                        + ici le else qui entoure le reste est inutile car tu sort en cas d'erreur:
                                         if(fichier==NULL){
                                                printf("Erreur ouverture fichier");
                                                exit(EXIT_FAILURE);
                                            }
                                            else{
                                                // tout le code ...
                                            }
                                        • Partager sur Facebook
                                        • Partager sur Twitter

                                        Le Tout est souvent plus grand que la somme de ses parties.

                                          17 juin 2021 à 19:03:31

                                          Salut,

                                          Ligne 65 tu initialises res à 1000, que se passe-t-il si l'écart minimum est de 1001 ?

                                          Ne t'embêtes pas trop à allouer au plus juste si la machine permet de voir large. Je sais que ça laisse un sentiment de boulot de sagouin, mais si tu es dans l'optique d'optimiser le temps de traitement, c'est le mieux à faire. Comme on dit avec Pierre, mesure la taille de ficher et alloues 2 fois ça. Au moins un octet sur 2 est pour un nombre, 4 octets par nombre -> 2 fois la taille de fichier. Ce n'est pas comme si tu allais devoir allouer 5Go. Même si tu fais un truc crado à la UBI en arrachant direct 10Mo, ce n'est pas tant que ça de nos jours... Le PC le plus moisi encore en état de marche à ma connaissance a encore 500Mo de RAM.

                                          Comme tu n'auras plus à te soucier de l'espace, tu pourras compter en même temps que tu lis le fichier, ça fera une lecture de moins, ce qui semble être le plus chronophage. avec un seule lecture, tu vas gagner au moins 20% du temps actuel. Je n'ai pas trop idée du temps que va prendre le tri.

                                          Je ne connais pas l'implémentation de scanf, mais comme c'est une fonction générique, tu pourrais peut-être (peut-être) gagner du temps à la remplacer par une fonction dédiée.

                                          Pareil pour remplacer Qsort, si tu fais une fonction dédiée, tu gagneras le temps d'appel de la fonction de comparaison. Faut voir comment ce sera optimisé par le compilo.

                                          Pour ces 2 derniers points, tu peux oublier pour l'instant, ce sont des pistes si vraiment tu as besoin de gratter encore du temps. As-tu une cible dans ton exercice ou est-ce juste pour toi ?

                                          Bonne continuation.

                                          -
                                          Edité par drx 17 juin 2021 à 19:05:34

                                          • Partager sur Facebook
                                          • Partager sur Twitter

                                          Stringman devient Bonhomme !! | Jeux de plateforme : Nouvelle Démo. (màj : 24/04/2021)

                                            17 juin 2021 à 19:41:19

                                            > Ne t'embêtes pas trop à allouer au plus juste si la machine permet de voir large.
                                            Pas sûr de comprendre ou d'être d'accord.
                                            @drx: tu as donné toi-même la façon de calculer la longueur du fichier. Aussi bien faire les choses correctement.
                                            Je suggère à nouveau de lire le fichier en entier d'un seul coup.
                                            OK Tu suggères de supposer que la quantité de nombres dans le fichier est la longueur divisée par deux et tu multiplie par 4: sizeof(int).
                                            Ce qui fait qu'on n'aura pas besoin de lire deux fois les nombres dans l'image du fichier.
                                            • Partager sur Facebook
                                            • Partager sur Twitter

                                            Le Tout est souvent plus grand que la somme de ses parties.

                                              17 juin 2021 à 19:56:40

                                              Effectivement, je gagne du temps en calculant la taille du Fichier et en allouant un grand espace d'abord. L'exercice est plus pour moi, ça fait bientôt un an que je code en C mais j'ai tendance à trouver les pires solutions aux exercices (en terme de complexité et performances). Donc j'essaie de travailler ça, pour me préparer à un entretien technique pour un stage!

                                              J'ai affecté à res la valeur INFINITY, c'est ce que j'ai trouvé en ligne.

                                              Version 3 du code :

                                              int* creationTableauv2(char* nomFichier,int* nbChiffres){
                                                  (*nbChiffres)=0;
                                                  int n;
                                              
                                                  FILE* fichier = fopen(nomFichier, "r");
                                              	if(fichier==NULL){
                                                      printf("Erreur ouverture fichier");
                                                      exit(EXIT_FAILURE);
                                              	}
                                              
                                              	fseek(fichier, 0, SEEK_END);
                                                  int tailleFichier = ftell(fichier);
                                                  int nbCases=(tailleFichier*2)/sizeof(int);
                                              
                                              	int* tableau = (int*)calloc(nbCases,sizeof(int));
                                              	if(tableau==NULL){
                                                          printf("Erreur allocation dynamique");
                                                          exit(EXIT_FAILURE);
                                                      }
                                              
                                              	rewind(fichier);
                                                  while(fscanf(fichier,"%d;",&n)==1){
                                                          tableau[(*nbChiffres)++]=n;
                                              	    }
                                              
                                              	fclose(fichier);
                                              	tableau = (int*)realloc(tableau,(*nbChiffres)*sizeof(int));
                                              	qsort(tableau,(*nbChiffres),sizeof(int),cmpInt);
                                              	return tableau;
                                              
                                              
                                              }
                                              
                                              
                                              int main(){
                                                  int nbChiffres;
                                                  clock_t start, end;
                                                  double cpu_time_used;
                                              
                                                  start = clock();
                                                  int* tab=creationTableauv2("numbers.txt",&nbChiffres);
                                                  rechercheDistanceMinimale(tab,nbChiffres);
                                                  end = clock();
                                                  cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
                                                  printf("\nTEMPS MIS 1: %lf\n",cpu_time_used);
                                              
                                                  free(tab);
                                              
                                              }
                                              



                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                17 juin 2021 à 20:35:56

                                                Bin admettons qu'il y ait 1384 valeurs dans son fichier, il s'acharne à vouloir allouer juste. Donc à moins d'avoir besoin des ressources de mémoire pour autre chose, dans le cas où il serait sur un machine limitée, je ne sais pas, un arduino ou un truc du genre, il est possible de voir large.

                                                Ok, il va peut-être se retrouver à allouer 4Mo quand 2 vont peut-être suffire, mais c'est le prix à payer si on veux gagner du temps. Et dans ce cas, même deux malheureux Mo en trop ne sont pas très cher payés s'il est sur un PC moderne, ce qui va être le cas à 98%.

                                                Oui, j'estime ça à la grosse, il vaut mieux être trop large que de manquer, sinon le programme va planter. Dans le pire des cas, il n'y a que des "1;" dans sont fichier. Donc un octet sur deux dans le fichier serait un nombre, on alloue tailleFichier/2*4 et on est certain d'être paré au pire des cas.

                                                Maintenant, si ça demandait d'allouer 4Go "larges" au lieu de 500Mo "juste" ce serait moins recommandable... En tout cas, je ne le ferais pas.

                                                En théorie le programmeur doit avoir une bonne idée de ce qui est probable ou non et envisager les sacrifices nécessaire à l'atteinte de l'objectif.

                                                Après, il y a moyen d'adapter pour "ajuster" les allocations quand-même moins couteuses que compter dans le fichier.

                                                Admettons que tu commences par allouer pour 1000 valeurs, comme tu comptes au moment de lire ton fichier, tu peux décider de placer un realloc pour 200 valeurs supplémentaires quand tu vois que tu vas être juste, ou par 500. Encore une fois c'est au programmeur de connaitre les ordres de grandeur.

                                                Par exemple dans un shoot'em up, j'ai une table dynamique pour gérer les tirs. Je pars avec une capacité de 16 instances et quand je vois que je suis juste, je realloc du double (32, 64, 128...). Je me le permet par que je sais qu'au max j'aurais une centaine d'instances. Maintenant, si on parlait en milliers d'instances (genre un gros manic shooter), je réallouerais peut-être que par lots de 100 au lieu de doubler la table.

                                                Avoir du rab sans se gaver...

                                                Dans tous les cas, réallouer par lots sera plus économique en temps que lire le fichier pour compter ou réallouer à l'unité.

                                                Bonne continuation.

                                                EDIT : Ok, bon les gens répondent pendant que je prend mon temps pour poster en faisant autre chose ^^.

                                                Inutile de realloc (ligne 27) pour réajuster ta table. C'est bon tu les as, si on te les a donnés ils ne manqueront plus à personne. Surtout si c'est pour les libérer 5 ms plus tard...

                                                Et du coup, combien de temps tu as gagné par rapport à ta version précédente ?

                                                -
                                                Edité par drx 17 juin 2021 à 20:49:02

                                                • Partager sur Facebook
                                                • Partager sur Twitter

                                                Stringman devient Bonhomme !! | Jeux de plateforme : Nouvelle Démo. (màj : 24/04/2021)

                                                  18 juin 2021 à 2:32:02

                                                  A_Ado_: > J'ai affecté à res la valeur INFINITY, c'est ce que j'ai trouvé en ligne.
                                                  Si ton tableau est trié, tu peux faire:
                                                      res = tableau[nbChiffres-1] - tableau[0] + 1;
                                                  Tu est certaine de ne pas dépasser cette valeur.
                                                  Tu fais:
                                                   int nbCases=(tailleFichier*2)/sizeof(int);
                                                  Il faut diviser par 2 seulement car tu utilises calloc ...
                                                  Tu vas réserver environ 4.4 Mb, pas plus.
                                                  Au total, tu auras réservé envirion 6.6 Mb, ce qui n'est pas énorme.
                                                  @drx: > Maintenant, si ça demandait d'allouer 4Go "larges" au lieu de 500Mo "juste" ce serait moins recommandable... En tout cas, je ne le ferais pas.
                                                  Je l'ai fait comme test avec 4 milliards, pas 4 Gb, et rien n'a sauté ...
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter

                                                  Le Tout est souvent plus grand que la somme de ses parties.

                                                    19 juin 2021 à 4:04:33

                                                    @drx : J'ai gagné 50 ms avec la dernière modif !

                                                    @PierrotLeFou : C'est fait .

                                                    Merci encore ! Le sujet est résolu pour moi :)

                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      19 juin 2021 à 7:46:36

                                                      t@A_Ado_:
                                                      Tu as fait un free() pour le tableau des nombres, mais tu ne l'as pas fait pour le tableau où tu lis le fichier. :)
                                                      Tu peux le faire juste après avoir écrit le dernier nombre avant le fclose().
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter

                                                      Le Tout est souvent plus grand que la somme de ses parties.

                                                        19 juin 2021 à 15:22:09

                                                        Si on craint d'allouer 2 fois trop (gaspiller 50%) à cause de la stratégie consistant à ré-allouer le double, il y a une solution simple : ré-allouer avec un facteur plus petit que 2.

                                                        Par exemple, si on veut limiter les pertes à 20% max, on multiplie par 1,25.

                                                        Ça marche aussi,  le coût moyen amorti d'une allocation sera toujours constant, mais la constante sera plus grande. Compromis temps / espace.

                                                        -
                                                        Edité par michelbillaud 19 juin 2021 à 19:59:27

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          19 juin 2021 à 19:36:39

                                                          En effet, il est peu vraisemblable qu'on n'aie que des nombres de 1 chiffres
                                                          Si je reprend mes petites statistiques:
                                                          Nombre de 2 chiffres: 750933 
                                                          Nombre de 3 chiffres: 563200 
                                                          Comme il y a toujours un ';' après chaque nombre, je dois diviser par N+1
                                                          Pour 2 chiffres, 2200/3*4 = 2933                                                                                       
                                                          Pour 3 chiffres, 2200/4*4 = 2200                                                                                       
                                                          Pour 4 chiffres, 2200/5*4 = 1760                                                                                       
                                                          Pour 5 chiffres, 2200/6*4 = 1466                                                                                       
                                                          Pour 6 chiffres, 2200/7*4 = 1257                                                                                        
                                                          Si je fais 2200 / 2 * 1.25 -> 1375
                                                          C'est ce que tu proposes?
                                                          Si on était certain de ne pas avoir de nombres de 5 ou 6 chiffres, on pourrait utiliser des short au lieu de int ...

                                                          • Partager sur Facebook
                                                          • Partager sur Twitter

                                                          Le Tout est souvent plus grand que la somme de ses parties.

                                                          Optimisation d'algorithme

                                                          × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                          • Editeur
                                                          • Markdown