Voila dans ma boite je me vois imposé un logiciel de traitement de liste pour les tri / filtre / merge / paste etc etc ... le logiciel c'est synsort.
Je me disais bouarf pourquoi payer si cher un truc pour faire de la bete commande shell. Mes collegues goguenards me soutiennent que ce truc est une tuerie d'efficacité ...
Mouarf j'y crois pas. un bete sort ca doit quand meme etre le top du top maintenant depuis le temps ...
Et ben que dalle
j'ai créé un fichier de 115 Mo a coup de "echo $RANDOM >> fichier"
sur un trie par valeur numérique le synsort me trie le fichier presque 3 fois plus vite que le sort du shell ...
Sur le cul !!!
d'autant que la machin est multi plateforme Windows / Unix / Linux ... (mais je n'ai que la version Windows)
Comment depuis le temps que les algos de tris sont connus peut t'on se faire laminer ainsi dans le libre ? je pige pas ...
les tests :
(le script généré par syncsort)
$ time cscript ss.wsf
real 1m20.137s
user 0m0.015s
sys 0m0.031s
la commande shell
$ time sort -n test.lst > sort.out
real 2m49.231s
user 1m56.515s
sys 0m3.327s
pour ce qui objecteront que c'est sous cygwin, j'ai aussi testé sous un bon vieux linux sur une machine comparable en reiferfs et le résultat du sort est du meme ordre ...
Je vois une tres grosse difference en userspace, pourquoi ?
Il m'est possible de faire d'autres tests avec time si cela vous interesse
Dam
la tronche du fichier :
$ head test.lst
23710
30538
18351
5643
560
15546
9945
20787
20266
25161
... (comme ca sur 115 Mo)
Journal M'enfin ?? ...
24
juin
2005
# Question concernant la mesure
Posté par Sylvain Briole (site web personnel) . Évalué à 10.
# Plusieurs raisons possibles.
Posté par Obsidian . Évalué à 8.
Il se peut très bien que GNU sort ait été écrit simplement pour faire ce qu'il a besoin de faire et que personne n'ait jamais eu le besoin de mettre la pression aux développeurs pour en faire une voiture de course. Cela ne me dérange pas plus que cela ...
Mais surtout, synsort c'est un logiciel propriétaire ? Code source fermé, etc ? Si c'est le cas, il y a eu une équipe de développement spécialement affectée à ce projet en particulier, ce qui favorise les efforts d'optimisation. Le logiciel a été conçu pour çà. Ensuite, si ton logiciel est livré déjà compilé, sans les sources, etc. et n'est pas spécialement un projet GNU, ou de philosophie Unix, il y a fort à parier qu'ils fassent un usage poussé de fonctions assembleur propre à la machine sur laquelle tu tournes (99% du temps un PC, même si Windows ou Linux) et tirent avantage des jeux d'instructions étendu style MMX etc. Et en ce sens, ils ont parfaitement raison. Une opération de tri est pratiquement un cas d'école dans ce domaine.
A cela, on peut ajouter la façon dont les différents outils acquièrent leurs données, et gèrent les fichiers. Je suppose que sort est capable d'utiliser mmap depuis longtemps, mais il doit rester un programme tout-terrain, gérant les ressources avec des appels les plus conventionnels possibles.
Avec tout cela, j'ai presque envie de dire que 3x la vitesse de sort, c'est honorable mais sans plus. Je suis persuadé qu'un algo de tueur optimisé par un démomaker (ou pire, un programmeur de 8 bits :-) devrait pouvoir monter jusqu'à 10 fois la vitesse de base (à vue de nez bien sûr).
[^] # Re: Plusieurs raisons possibles.
Posté par Obsidian . Évalué à 4.
[^] # Re: Plusieurs raisons possibles.
Posté par Lana . Évalué à 6.
[^] # Re: Plusieurs raisons possibles.
Posté par kd . Évalué à 2.
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 . Évalué à 2.
# Hum
Posté par Gregplus . Évalué à 3.
- algo complètement différents (par exemple au niveau de l'utilisation de la mémoire)
- peut-être que le compilo utilisé optimise très bien le type d'opération effectuées
Il n'est pas toujours pertinent de comparer des outils qui font la même chose car leurs spécifications de départ peuvent être différentes.
Ton test est à revoir aussi sans doute, il faudrait essayer avec des fichiers triés, presque triés ou pas triés du tout, avec des tailles de fichiers variées (petit, tout petit, gros, très gros ...) et différents types de données.
[^] # Re: Hum
Posté par qstone . Évalué à 3.
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 . Évalué à 2.
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 . Évalué à 1.
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 . Évalué à 3.
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 . Évalué à 1.
[^] # Re: Hum
Posté par briaeros007 . Évalué à 2.
Les algos de tri lineaires ne sont donc pas a comparaison :)
# Pour sort, ca depend des options
Posté par pi6Lohe . Évalué à 10.
$ time sort -n /tmp/test > /tmp/test.0
real 2m10.619s
user 2m5.835s
sys 0m0.813s
$ time sort -ns /tmp/test > /tmp/test.1
real 0m48.893s
user 0m46.934s
sys 0m0.626s
$ md5sum /tmp/test.*
5a04eeff80719ae6a73e6966c2e5d13a /tmp/test.0
5a04eeff80719ae6a73e6966c2e5d13a /tmp/test.1
$
En inversant l'ordre des tris ca ne change pas.
[^] # Re: Pour sort, ca depend des options
Posté par M . Évalué à 6.
[^] # Re: Pour sort, ca depend des options
Posté par Ozz . Évalué à 4.
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 . Évalué à 2.
Dans le man de sort de la Debian Sarge j'ai:
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 . Évalué à 2.
Il est normal que ce soit le comportement par défaut.
[^] # Re: Pour sort, ca depend des options
Posté par Bapt (site web personnel) . Évalué à 2.
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 (site web personnel) . Évalué à 3.
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 . Évalué à 3.
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 (site web personnel) . Évalué à 2.
[^] # Re: Pour sort, ca depend des options
Posté par LeMagicien Garcimore . Évalué à 2.
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 (site web personnel) . Évalué à 6.
[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
Posté par webseb . Évalué à 5.
Je crois que tu essayes de comparer des logiciels qui n'ont pas les mêmes finalités. Synsort a dés algos de traitement super optimiser et permet bien plus de chose que le "sort" d'unix.
Il parait évident que pour quelqu'un qui n'utilise qu’occasionnellement le trie, synsort va être bien trop lourd. Mais quand on a besoin de trier/rechercher/fusionner/développer ..., synsort est vraiment royale.
Et puis soyons chauvin, synsort est français :)
[^] # Re: super logiciel
Posté par Hardy Damien . Évalué à 2.
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
Posté par fmaz fmaz . Évalué à 10.
Je ne vais pas le redémontrer mais.
La complexité (en nombre de comparaisons) dans le pire des cas d'un
algorithme de tri est n.log(n). On connait beaucoup d'algorithmes qui
ont cette complexité dans le pire des cas (entre autre merge-sort et heap-sort)
et un certain nombre qui l'on en moyenne (quick-sort).
Personne n'utilise merge sort car ce n'est pas un algorithme en place (on
recopie les infos et on a besoin de deux fois plus de mémoire).
Tout le monde utilise quick-sort car il fonctionne en placeet a une très faible
constante cachée (mieux vaut du 2n.log(n) en pratique mais pas tout le temps
que du 100000n.log(n) toujours).
Ceci dit, il existe effectivement des algorithmes très efficace dans des cas
particuliers. Bucket sort en fait partie. Si tu sais que tu dois trier une liste
contenant tous les entiers de 1 à n, ben tu lis les entiers et tu les mets
directement dans la bonne case.
Pour information, le sort d'unix est un quick-sort. Or, quick-sort compare les
premiers éléments de la liste et les derniers elements de la liste à un "pivot".
C'est très mauvais dans pas mal de cas. Pour s'en rendre compte, imaginez
ce qui se passe si on doit trier les éléments d'une bande magnétique?
Paf, je vais chercher le premier élément, paf je vais chercher le dernier,
paf, je vais chercher le second élément... Bref, vous avez l'idée.
De nos jours, il y a une telle différence entre l'accès mémoire et le
fonctionnement du processeur qu'il est beaucoup plus rentable d'optimiser
les accès mémoire que le temps de calcul. Le sort d'unix ne le fait pas. Il
est donc normal qu'il se fasse enfoncer.
Frédéric
[^] # [HS] En parlant de quicksort...
Posté par MeJohn . Évalué à 2.
Allez, pour vous consoler, il se fait apparemment pas mal chambrer aux confs d'informatique ;-)
[^] # Re: glou
Posté par gc (site web personnel) . Évalué à 3.
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.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.