Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Concours de performances Discussion :

Première partie du concours : tri


Sujet :

Concours de performances

  1. #41
    Rédacteur/Modérateur

    pour te donner une idée... je l'ai insérer dans mon code, donc les mêmes IO

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    real    0m0.710s
    user    0m0.664s
    sys     0m0.042s

    donc légérement mieux que le mien...
    [EDIT]j'avais oublié le static [/EDIT]



    @Jean-Marc.Bourguet: j'ai aussi joué avec qprof

    pour davcha
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    read_vect                                                        34     (  3%)
    write_vect                                                       16     (  2%)
    triR                                                             193    ( 19%)
    libc.so.6                                                        20     (  2%)
    libc.so.6(strtoull)                                              317    ( 32%)
    libc.so.6(_IO_vfprintf)                                          129    ( 13%)
    libc.so.6(fprintf)                                               22     (  2%)
    libc.so.6(fgets)                                                 57     (  6%)
    libc.so.6(_IO_getline_info)                                      26     (  3%)
    libc.so.6(_IO_file_xsputn)                                       50     (  5%)
    libc.so.6(memchr)                                                40     (  4%)
    libc.so.6(memcpy)                                                34     (  3%)

    pour moi
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    quicksort(_mcleanup)                                             292    ( 28%)
    libc.so.6(__strtoull_internal)                                   297    ( 29%)
    libc.so.6(_IO_vfprintf)                                          163    ( 16%)
    libc.so.6(fprintf)                                               25     (  2%)
    libc.so.6(fgets)                                                 42     (  4%)
    libc.so.6(_IO_getline)                                           8      (  1%)
    libc.so.6(_IO_getline_info)                                      23     (  2%)
    libc.so.6(_IO_file_xsputn)                                       55     (  5%)
    libc.so.6(memchr)                                                23     (  2%)
    libc.so.6(memcpy)                                                41     (  4%)
    et je ne vois pas comment économiser sur strtoull et les IO... sans faire de l'asm

    et sachant que je suis meilleur que le quicksort de gcc


    [EDIT2]
    à défaut de pouvoir écrire plus vite, j'ai décidé d'écrire des plus gros morceaux avec fputs... plus bourin

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    quicksort(_mcleanup)                                             305    ( 25%)
    libc.so.6(__strtoull_internal)                                   366    ( 30%)
    libc.so.6(_IO_vfprintf)                                          86     (  7%)
    libc.so.6(sprintf)                                               11     (  1%)
    libc.so.6(fgets)                                                 91     (  8%)
    libc.so.6(_IO_getline)                                           16     (  1%)
    libc.so.6(_IO_getline_info)                                      63     (  5%)
    libc.so.6(_IO_default_xsputn)                                    53     (  4%)
    libc.so.6(memchr)                                                44     (  4%)
    libc.so.6(mempcpy)                                               11     (  1%)
    libc.so.6(memcpy)                                                65     (  5%)
    les pourcentages s'améliorent peu, mais se disperse dans stdio... et je gagne peu

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    real    0m0.867s
    user    0m0.816s
    sys     0m0.045s

    [EDIT] mes temps...
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    real    0m0.854s
    user    0m0.816s
    sys     0m0.037s
    les sources au passage
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  2. #42
    Rédacteur/Modérateur

    @davcha: en fait, ton programme plante dès que les entiers sont trop grands... mais moins vite que mon tri par dénombrement
    mon premier jeu t'était trop favorable...
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  3. #43
    Membre expérimenté
    C'est quoi "trop grand" exactement ?

  4. #44
    Rédacteur/Modérateur

    Citation Envoyé par davcha
    C'est quoi "trop grand" exactement ?

    dès que je dépasse les 100 millions...
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  5. #45
    Membre expérimenté
    Bizarre... Ca marche chez moi.

  6. #46
    Rédacteur/Modérateur

    Citation Envoyé par davcha
    Bizarre... Ca marche chez moi.

    très bizarre... perso, je suis sur une machine avec 2Go de Ram
    à moins que tu n'es plus


    sinon as-tu au moins une limite chez toi ?
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  7. #47
    Membre expérimenté
    Euh... Tu parles des éléments du tableau qui sont trop grands ou de la taille du tableau qui est trop grande ?

    J'ai 1gig de ram moi, et effectivement, ça a tendance à planter quand on essaie de trier une très grande quantité d'éléments.

  8. #48
    Rédacteur/Modérateur

    Citation Envoyé par davcha
    Euh... Tu parles des éléments du tableau qui sont trop grands ou de la taille du tableau qui est trop grande ?

    J'ai 1gig de ram moi, et effectivement, ça a tendance à planter quand on essaie de trier une très grande quantité d'éléments.

    lorsque les entiers à traiter sont trop grands... je ne vois pas trop pourquoi mais bon
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  9. #49
    Membre expérimenté
    Y'a pas tellement de raison effectivement, dans la mesure où mon algo travaille surtout sur quelque chose de la taille d'1 octet... Donc bon...

  10. #50
    Membre éprouvé
    Quelqu'un a-t-il essayé d'utiliser Flex (ou Lex) pour engendrer une fonction "propre" permettant de déchiffrer les entiers contenus dans le fichier texte ?
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  11. #51
    Rédacteur/Modérateur

    Citation Envoyé par InOCamlWeTrust
    Quelqu'un a-t-il essayé d'utiliser Flex (ou Lex) pour engendrer une fonction "propre" permettant de déchiffrer les entiers contenus dans le fichier texte ?

    perso, non...
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  12. #52
    Membre éprouvé
    Et pourquoi, non ? Faire des sscanf et des trucs dans le même genre... ça craint un peu, non, quand on a un super outil comme celui-là ?
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  13. #53
    Expert éminent
    Citation Envoyé par InOCamlWeTrust
    Quelqu'un a-t-il essayé d'utiliser Flex (ou Lex) pour engendrer une fonction "propre" permettant de déchiffrer les entiers contenus dans le fichier texte ?
    Pourquoi prendre un marteau pilon pour tuer une mouche. J'ai écris une fonction à la main comme un grand (elle fait à tout casser 10 lignes). La fonction d'écriture est un plus complexe.

    (Je sais on m'a demandé des mesures... c'est toujours en vue sur ma liste mais il y a des choses qui ne cessent de s'intercaler avant).
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  14. #54
    Membre éprouvé
    Citation Envoyé par Jean-Marc.Bourguet
    Pourquoi prendre un marteau pilon pour tuer une mouche...
    Je ne suis pas sûr que placer une ou deux petites expressions rationnelles, à savoir [1-9]+ pour récupérer les nombres et [' ' '\n]+ pour manger les blancs (désolé, je ne connais pas précisément la syntaxe Lex, étant donné que j'utilise surtout ocamllex), dans un fichier Lex soit très lourd. Je me posais simplement la question, étant donné, qu'en général, c'est ce que l'on utilise lorsque l'on veut découper un fichier en unités lexicales.
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  15. #55
    Expert éminent
    Citation Envoyé par InOCamlWeTrust
    Je ne suis pas sûr que placer une ou deux petites expressions rationnelles, à savoir [1-9]+
    Passons

    pour récupérer les nombres et [' ' '\n]+ pour manger les blancs (désolé, je ne connais pas précisément la syntaxe Lex, étant donné que j'utilise surtout ocamllex), dans un fichier Lex soit très lourd. Je me posais simplement la question, étant donné, qu'en général, c'est ce que l'on utilise lorsque l'on veut découper un fichier en unités lexicales.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
          while (isspace((unsigned char)*endptr))
            ++endptr;
    et
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
      while (isdigit(*ptr)) {
        data = 10*data + *ptr - '0';
        ++ptr;
      }
    sont à coup sûr moins lourd que faire intervenir un programme extérieur dans la compilation. Surtout que la deuxième boucle sera de toute façon nécessaire, lex n'évaluant pas. Sans parler naturellement du fait que le sujet du défi est les perfs et que, jusqu'à nouvel ordre, les IO sont la partie critique du bazard (et si je ne veux pas écrire la deuxième boucle, j'ai toujours strtoull sous la main, mais on perd du temps avec la gestion des bases). Je connais bien lex (j'en ai écrit trois variantes) et yacc (j'en ai écrit deux variantes), mais je continue à penser que ce sont des moyens disproportionnés au problème.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  16. #56
    Membre éprouvé
    Citation Envoyé par Jean-Marc.Bourguet
    Sans parler naturellement du fait que le sujet du défi est les perfs et que, jusqu'à nouvel ordre, les IO sont la partie critique du bazard
    C'est pourquoi je trouve que ce concours est biaisé. Il faudrait se mettre d'accord sur une interface avec les entrées-sorties et ne comparer que les temps alloués au tri... enfin, c'est ce que je pense.

    Ou alors, lancer le tri peut-être une centaine de fois sur le même tableau pour pouvoir juger un peu mieux des performances du tri en question.
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  17. #57
    Expert éminent
    Citation Envoyé par InOCamlWeTrust
    C'est pourquoi je trouve que ce concours est biaisé.
    Le titre est un piège, c'est tout. Et l'objectif caché de l'exercise est

    - d'une part de montrer les tris en mémoire ne sont généralement pas un problème, les IO ou le temps de fabrication des données dominant largement

    - d'autre part de rappeler qu'une complexité linéaire peut dominer une complexité N log N si les constantes multiplicatives le veulent.

    C'est un objectifs louable que de remettre un peu de pragmatisme dans la tête des étudiants gavés de théorie.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  18. #58
    Membre éprouvé
    Citation Envoyé par Jean-Marc.Bourguet
    Le titre est un piège, c'est tout. Et l'objectif caché de l'exercise est

    - d'une part de montrer les tris en mémoire ne sont généralement pas un problème, les IO ou le temps de fabrication des données dominant largement

    - d'autre part de rappeler qu'une complexité linéaire peut dominer une complexité N log N si les constantes multiplicatives le veulent.

    C'est un objectifs louable que de remettre un peu de pragmatisme dans la tête des étudiants gavés de théorie.
    Ne t'inquiète pas, pour ma part je sais tout ça.

    Ce que je voulais dire, c'est qu'il est dommage que l'on ne juge pas de la vraie valeur des tris, car programer un vrai bon tri requiert une programmation fine et précise.

    Sinon, on peut se passer allègrement des conversions et faire comme j'ai fait chez moi : trier en ASCII ! Je suis, au niveau des temps, plus ou moins dans ce qui a été publié plus haut, même si les temps et les performances peuvent beaucoup varier d'un ordinateur à un autre.

    L'avantage, c'est d'économiser environ entre 5 000 000 et 10 000 000 de multiplications (si les nombres ont entre 5 et 10 chiffres) ! Par contre, le tri en lui-même est plus lent car les données sont plus lourdes à déplacer (comme on pouvait s'y attendre).
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  19. #59
    Expert éminent
    Citation Envoyé par InOCamlWeTrust
    Ne t'inquiète pas, pour ma part je sais tout ça.

    Ce que je voulais dire, c'est qu'il est dommage que l'on ne juge pas de la vraie valeur des tris, car programer un vrai bon tri requiert une programmation fine et précise.
    Pourquoi si de toute manière on ne gagne quelque pourcent sur une tache qui prend quelque pourcent du temps total.

    En ce qui concerne le tri d'1M nombre, il est possible de mesurer quel est le meilleur algo mais il faut le faire avec précautions. J'ai des variations de temps pour un même algo qui sont souvent plus importantes que les variations de temps entre algo (et ça en ne mesurant que le temps du tri). J'ai pas encore trouvé la cause, mais je me demande si elle n'est pas liée aux changements de contexte.

    Sinon, on peut se passer allègrement des conversions et faire comme j'ai fait chez moi : trier en ASCII ! Je suis, au niveau des temps, plus ou moins dans ce qui a été publié plus haut, même si les temps et les performances peuvent beaucoup varier d'un ordinateur à un autre.
    J'ai essayé, mais j'étais nettement plus lent qu'en faisant les conversions. Mais je m'y suis peut-être mal pris, il y a deux ou trois variations que j'ai pas encore essayé.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  20. #60
    Membre éprouvé
    Tout à fait d'accord : pour comparer deux algorithmes de tri il faut soit les lancer sur des données beaucoup plus grandes (au moins dix millions), soit les réitérer plusieurs fois.
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.