Question concernant la mesure

Plusieurs raisons possibles.

• [^]Re: Plusieurs raisons possibles.

  Posté par Obsidian () le 24/06/2005 à 10:59. (lien). Évalué à 4.

  J'ajouterais qu'après une brève recherche, je n'ai pas été capable de retrouver par Google le ou les algorithmes utilisés par sort. Un logiciel dédié à cette opération effectuera je crois un rapide contrôle du contenu du fichier et choisira l'algo le plus adapté en conséquence.

  • [^]Re: Plusieurs raisons possibles.

    Posté par Lana () le 24/06/2005 à 11:59. (lien). Évalué à 6.

    Ce qui serait intéressant, c'est de voir la rapidité de celle algo en fonction des données et le comparer avec sort. Si la différence est toujours d'un facteur 3, c'est qu''il n'y a pas vraiment de révolution dans l'algo utilisé, mais simplement des optimisations sur le calcul (ou autre... enfin, je pense), les deux ayant la même complexité.

    • [^]Re: Plusieurs raisons possibles.

      Posté par Khanh-Dang (page perso, ) le 25/06/2005 à 08:16. (lien). Évalué à 2.

      Je pense que ce qui serait encore plus interessant, c'est de regarder les temps d'execution des deux algos utilises.
      
      Il faudrait regarder pour un fichier deux fois plus gros. Si synsort est toujours 3 fois plus rapide, c'est que les deux algorithmes sont aussi efficaces l'un que l'autre en theorie. Si ce ratio de 3 n'est pas respecte, c'est que synsort est reellement plus rapide.
      
      PS: Desole pour les accents. J'utilise presentement Firebird 0.6 (ca nous rajeunit :-) avec un clavier qwerty sous Irix et les accents ne passent pas pour une raison inconnue.

      • [^]Re: Plusieurs raisons possibles.

        Posté par Lana () le 25/06/2005 à 11:04. (lien). Évalué à 2.

        Je me suis peut être mal exprimé, mais c'est ce que je voulais dire. En tous cas, tu fais très bien de le préciser parce que je m'étais tout de même rendu compte que ce n'était pas très clair.

Hum

• [^]Re: Hum

  Posté par qstone () le 24/06/2005 à 12:07. (lien). Évalué à 3.

  Pour l'algo, vu le genre de fichier de test et les perfs, ça me rappelle le "count sort", le tri le + rapide du monde sur des entiers pas trop gros...
  
  Beaucoup d'algos de tris prennent les valeurs 1 à 1, et mettent à jour un tableau de résultat avec. Le count sort c'est : "je trie des entiers. Plutot que d'avoir un tableau de résultats triés, je vais passer les éléments 1 à 1 et compter le nombre de 0, de 1, de 2...". Ca bouffe une quantité de RAM pas possible (1 compteur par valeur possible), mais en 2 passes (compter-compiler) c'est fini !
  
  Si ton synsort utilise ça, et que la commande sort prend un algo plus "général", ça explique les écarts. Ca vaudrait le coup de refaire ton test avec des choses plus complexes que des nombres entiers (genre de réels ou des chaines de caractères)

• [^]Re: Hum

  Posté par Carla Winter () le 24/06/2005 à 12:13. (lien). Évalué à 2.

  Si y'a un pro de l'algo ici il me reprendra mais y'a pas un truc qui dit que le tri doit se réaliser en un nombre minimum d'opérations (genre de l'ordre de ln(n)) ?
  Donc après c'est "plus que" de l'optimisation sur la lecture et l'écriture dans les fichiers et l'optimisation des opérations de base qui sont faites.
  
  Non?
  
  2 cents ;)

  • [^]Re: Hum

    Posté par x0ra () le 24/06/2005 à 13:13. (lien). Évalué à 1.

    ouaip, la complexité minimale d'un algo de tri est de n * log(n) (log == log base 2)
    
    Dans le cas présent, il faudait voir comment les deux programmes se comportent au niveau mémoire et gestion des I/O.

    • [^]Re: Hum

      Posté par fmaz fmaz () le 27/06/2005 à 12:06. (lien). Évalué à 3.

      Allez, je me lance pour faire la démo du n*log(n).
      
      Bon, considérons les listes des entiers de 1 à n.
      Il y en a n! (n places possibles pour "n" puis (n-1) pour "n-1" car la place de
      "n" est prise etc.).
      
      On peut représenter un tri par comparaisons par un arbre de décision.
      
      Au début, je décide de comparer x et y
      Si x>y alors
      -- je compare z et t
      -- si z>t alors...
      -- si t<z alors...
      Si y<x alors
      -- je compare u et i
      -- si u>i alors...
      -- si u<i alors...
      
      Le feuilles de l'arbre correspondent au moment où le tri s'arrête. « J'ai fini.
      Ouai! »
      
      Si on se donne une liste particulière, le fonctionnement de l'algorithme
      correspond à un chemin particulier dans cet arbre et deux listes différentes
      vont correspondre à deux chemins distincts.
      
      Il faut donc n! feuilles dans notre arbre de décision. Intuitivement, si on veut
      que le plus long des chemins soit le plus cours possible, il faut que l'arbre
      soit équilibré, voir même que ce soit un arbre binaire complet. Or, le nombre de
      feuilles d'un arbre binaire complet de hauteur h est 2^h.
      
      La hauteur de l'arbre de décision doit donc vérifier 2^h>n! et donc h>log(n!).
      
      Or la formule de stirling donne n!~\sqrt{2\pi}(n/e)^n donc log(n!)~n*log(n) et
      donc, la profondeur de notre arbre de décision est donc au minimum
      O(n*log(n)).
      
      Fini.

  • [^]Re: Hum

    Posté par harbort1 () le 24/06/2005 à 17:44. (lien). Évalué à 1.

    Alors, sans hypothèse supplémentaire en effet c'est du O(n*log(n)) la complexité, mais avec des hypothèses supplémentaires ça peut tomber à O(n). Alors comme dit plus haut, s'il y a une analyse du type de fichier ...

    • [^]Re: Hum

      Posté par briaeros007 () le 25/06/2005 à 09:52. (lien). Évalué à 2.

      si je me rapelle mes cours d'algo ce sont les algos de tri par comparaison qui sont en minimum ( n ln (n) )
      Les algos de tri lineaires ne sont donc pas a comparaison :)

      --
      Subete ga wakatta toki…watashi ga anta wo korosu.

Pour sort, ca depend des options

• [^]Re: Pour sort, ca depend des options

  Posté par Matthieu C () le 24/06/2005 à 11:22. (lien). Évalué à 6.

  tu peux aussi jouer avec -S pour augmenter la taille du buffer...

• [^]Re: Pour sort, ca depend des options

  Posté par Ozz () le 24/06/2005 à 11:56. (lien). Évalué à 4.

  Fichtre, l'option -s n'est pas documenté dans le man de sort en français.
  
  Je préférerais qu'il m'affiche le man en anglais plutot qu'une version obsolète...

  • [^]Re: Pour sort, ca depend des options

    Posté par Fnor () le 24/06/2005 à 14:39. (lien). Évalué à 2.

    Fichtre, l'option -s n'est pas documenté dans le man de sort en français.

    
    
    Dans le man de sort de la Debian Sarge j'ai:
    
    

    Finalement, si toutes les clés sont égales, en dernier ressort sort compare les lignes octet par octet suivant l'ordre défini sur la machine. Cette dernière comparaison accepte l'option globale -r. L'option -s (stable) inhibe cette comparaison en dernier recours afin que les lignes considérées comme égales restent à leurs positions relatives. Si aucun champ clé, et aucune option ne sont fournis, -s est sans effet.

    
    
    Ce qui explique bien pourquoi c'est plus rapide et ça ne devrait pas poser de problème dans la plupart des cas. Je suis étonné que ce ne soit pas la valeur par défaut.

    • [^]Re: Pour sort, ca depend des options

      Posté par Obsidian () le 24/06/2005 à 15:25. (lien). Évalué à 2.

      Ben c'est écrit. Si ni champ clé ni option ne sont précisés, "s" est sans effet. Cela veut juste dire que si tu utilises un champ pour faire un tri, et que deux entrées ont la même valeur, il va comparer les deux lignes litéralement pour les classer (en fonction de leur contenu, leur longueur, etc.). Ce qui te garantit que ton fichier sera toujours trié en fonction d'au moins un critère, et que les lignes ne seront pas redéposées dans l'ordre où il apparaissent.
      
      Il est normal que ce soit le comportement par défaut.

• [^]Re: Pour sort, ca depend des options

  Posté par Bapt (page perso, ) le 24/06/2005 à 12:49. (lien). Évalué à 2.

  l'option -s c'est bien, mais c'est pas très portable (en même temps je ne suis pas sûr que synsort soit très portable non plus :)), A mon travail : mais ici :
  Solaris 8 => pas d'option -s
  Solaris 9 => pas d'option -s
  AIX 4.3 => pas d'option -s
  AIX 5.3 => pas d'option -s
  RHEL 3 => ouais, une option -s :)
  
  En revanche, si ton parc n'est composé que de machine équipée de GNU sort, c'est intéressant, sinon le problème reste le même.
  
  C'est souvent ce qui m'énerve dans ces utilitaires très pratiques, c'est les variantes suivant les version, genre :
  GNU ls/BSD ls/ autres ls
  GNU awk/awk/nawk/...
  grep/egrep/...
  
  C'est bien souvent dépendant des OS le mieux c'est awk/nawk sur Solaris. Pour faire des scripts portable c'est la croix et la banière, doù l'intérêt d'éviter de les utiliser au maximum dans ces script au profit des fonctions build-in de ton shell genre ksh... Mais là je suis H.S.

  • [^]Re: Pour sort, ca depend des options

    Posté par gc (page perso, ) le 24/06/2005 à 14:28. (lien). Évalué à 3.

    portable ? sort utilisé sous Linux est l'implémentation GNU d'un outil classique Unix, ce n'est pas un problème de portabilité, sort n'est pas standardisé.
    
    en plus, ça m'étonnerait que les coreutils GNU d'où provient sort ne soient pas portables sur tes vieux Unix propriétaires.

    • [^]Re: Pour sort, ca depend des options

      Posté par LeMagicien Garcimore () le 25/06/2005 à 04:52. (lien). Évalué à 3.

      ba et Posix c'est pas un standard peut-être ? Je viens de parcourir la spec posix et pas de -s à l'horizon.
      
      en plus, ça m'étonnerait que les coreutils GNU d'où provient sort ne soient pas portables sur tes vieux Unix propriétaires.
      
      Si tu dois te taper la compile des corutils pour faire tourner un pauvre script...
      Posix a justement été fait (cette partie là de posix en tout cas) pour permettre ce genre de compatibilité. Vouloir la conserver en evitant d'utiliser les options GNU, c'est pas un mal à mon avis. Bien sur dans certaine situation c'est pas très grave, mais bon autant faire les choses proprement.

      • [^]Re: Pour sort, ca depend des options

        Posté par gc (page perso, ) le 26/06/2005 à 20:15. (lien). Évalué à 2.

        je ne vois pas trace de la mention de posixité dans le man de sort, et vu que les specs posix ne semblent pas disponibles gratuitement.. tu as un pointeur ?

        • [^]Re: Pour sort, ca depend des options

          Posté par LeMagicien Garcimore () le 27/06/2005 à 15:40. (lien). Évalué à 2.

          elle sont dispo ici : http://www.opengroup.org/bookstore/catalog/elec_free.htm(...)
          
          il faut juste t'enregistrer (nom et email, même pas de confirmation).
          
          ensuite le lien direct :
          http://www.opengroup.org/onlinepubs/009695399/utilities/sort.html(...)
          
          je ne vois pas trace de la mention de posixité dans le man de sort
          
          dans info sort, par contre, il est indiqué :
          
          GNU sort follows the POSIX behavior, [...]

• [^]Re: Pour sort, ca depend des options

  Posté par gc (page perso, ) le 24/06/2005 à 15:04. (lien). Évalué à 6.

  Normalement la stabilité de l'algorithme ne devrait pas influer sur sa performance. Un algorithme de tri stable semble être (d'après perldoc -f sort) la caractéristique de garder l'ordre initial d'éléments qui comparent comme étant égaux. Vu le reste de la doc perl et des chiffres ci-dessous, je dirais que la demande d'un algo stable fait passer de l'utilisation de quicksort à mergesort, qui est plus efficace dans ce cas particulier.
  
  
  [gc@meuh /tmp] head meuh
  39541
  21152
  70685
  8033
  13506
  82620
  34950
  34526
  99135
  29911
  
  
  [gc@meuh /tmp] /usr/bin/time sort -n meuh > n
  0:29.01elapsed
  
  [gc@meuh /tmp] /usr/bin/time sort -ns meuh > ns
  0:21.11elapsed
  
  [gc@meuh /tmp] cat meuh | time perl -e 'print sort {$a <=> $b} ' > perldef
  0:12.18elapsed
  
  [gc@meuh /tmp] cat meuh | time perl -e 'use sort _quicksort; print sort {$a <=> $b} ' > perlqui
  0:18.85elapsed
  
  [gc@meuh /tmp] cat meuh | time perl -e 'use sort _mergesort; print sort {$a <=> $b} ' > perlme
  0:12.17elapsed

super logiciel

• [^]Re: super logiciel

  Posté par Hardy Damien (page perso, ) le 24/06/2005 à 12:23. (lien). Évalué à 2.

  Ben pareil, nous on s'en sert pour des traitements sur des releves de prix magasins. C'est plus rapide qu'une requete SQL ...
  Mais je n'avais jamais fait tourner l'appli moi même mais comme je vais m'interresser à cette partie de notre archi prochainement je regarde :)
  
  Dam

glou

• [^][HS] En parlant de quicksort...

  Posté par MeJohn () le 24/06/2005 à 14:38. (lien). Évalué à 2.

  Et dire que son inventeur, le grand Tony Hoare, bosse chez M$ Research maintenant...Si si...
  
  Allez, pour vous consoler, il se fait apparemment pas mal chambrer aux confs d'informatique ;-)

• [^]Re: glou

  Posté par gc (page perso, ) le 24/06/2005 à 14:50. (lien). Évalué à 3.

  Personne n'utilise merge sort
  
  perldoc -f sort :
  
  Perl 5.6 and earlier used a quicksort algorithm to implement sort. That algorithm was not stable, and could go quadratic. (A stable sort preserves the input order of elements that compare equal. Although quicksort’s run time is O(NlogN) when averaged over all arrays of length N, the time can be O(N**2), quadratic behavior, for some inputs.)
  
  In 5.7, the quicksort implementation was replaced with a stable mergesort algorithm whose worst case behavior is O(NlogN). But benchmarks indicated that for some inputs, on some platforms, the original quicksort was faster. 5.8 has a sort pragma for limited control of the sort. Its rather blunt control of the underlying algorithm may not persist into future perls, but the ability to characterize the input or output in implementation independent ways quite probably will.