Discussion :

[piedintelligent]

Bonjour,
Je viens de faire un test comparatif des temps d'exécution de std::sort sur différents types de base. Le résultat est déroutant : trier des short int est presque 3 fois plus long que de trier des int !

Est-ce qqn a l'explication ????

Voici les conditions :
- tableaux (C) de 10^8 valeurs à trier.
- les tableaux sont initialisés dans les désordre
- résultats obtenus avec du code compilé sous visual 2010
- même résultats sous windows 2008 server 64 bits
windows 7 64bits et 32bits.

(code source du main.cpp en fichier attaché)

résultats console :
2715 ms pour trier 10^8 uchar
4462 ms pour trier 10^8 ushort
1840 ms pour trier 10^8 uint
3339 ms pour trier 10^8 float

[Flob90]

C'est pas nécessairement incohérant, le type int est normalement le plus adapté à l'architecture de ta machine. Les autres types peuvent être moins adapté et donc pas nécessairement plus rapide même si plus petit.

Je ne connais pas assez les détails techniques pour approfondir plus

[JolyLoic]

Tes tableaux ne sont pas initialisés dans le désordre, mais dans un ordre bien précis. Qui plus est, avec les int, on n'a pas de doublons dans le tableau.

Je serais curieux de voir ce que ça donne :
- Avec un random shuffle avant le tri
- Idem, mais en s'assurant au début que tous les tableaux contiennent les mêmes valeurs uniquement (entre 0 et 255 donc).

[Arzar]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
   tic();
   std::sort(ustable, ustable + NBIG);
   toc();
   printf(" pour trier 10^8 ushort\n");
 
   tic();
   std::sort(ustable, ustable + NBIG);
   toc();
   printf(" pour trier 10^8 uint\n");

Ce code fait deux fois la même chose. Les printf mentent.

Edit : + 1 avec loic, ce n'est pas une très bonne idée de comparer des ensembles de donnée différents. Et surtout le tableau d'uint est déjà trié de 65535 à 0 en ordre décroissant ce qui est clairement un cas particulier qui fausse la mesure du sort.

Chez moi (vs2010), si tous les tableaux contiennent des valeurs aléatoires comprises entre zéro et 255 alors le timing de chaque sort deviennent quasi similaire.

[piedintelligent]

J'avais pas vu la coquille ! merci Arzar. C'est encore pire que ça la mesure la plus rapide était en fait un tri du tableau déjà trié

J'ai tenu compte de vos remarques : maintenant les tableaux sont initialisés par la fonction rand, qui sort un entier pseudo aléatoire entre 0 et RAND_MAX = 32767. tous les tableaux ont les mêmes valeurs après init (j'oublie les uchar), effectivement le tri de short et de int est presque aussi rapide, ce qui semble plus naturel

@JolyLoic : voici les résultats avec des nombre aléatoires entre 0 et 255
(sortie de rand casté en uchar). Les mêmes valeurs sont données aux 4 tableaux à l'init.

résultats console :
4649 ms pour trier 10^8 uchar
4852 ms pour trier 10^8 ushort
4742 ms pour trier 10^8 uint
6521 ms pour trier 10^8 float

il n'y a que pour les float que c'est plus long sinon les différences ne sont pas significatives.

Pour les types entiers, effectivement la durée d'exécution du tri de valeurs aléatoires dépend de la dynamique.

merci à tous

[Invité]

Une petite remarque, qui n'invalide pas les résultats du test.

std::sort, généralement fondé sur l'implémentation usuelle de quicksort, n'est pas très efficace en présence de clefs dupliquées (parce qu'il s'acharne à "trier" les valeurs égales). Sur des tableaux de 100 millions d'entrées remplis au hasard, on pourra, en modifiant l'algorithme (je crois qu'on peut le faire sans sortir de la stl, en jouant astucieusement sur "partition") accélérer nettement les tris sur des tableaux fortement dupliqués (ici les char).

Egalement, sur des tableaux ayant un tout petit nombre de valeurs (256 ici), un comptage suffirait (donc une mémoire additionnelle de 256 double mots, et deux passes sur le tableau de départ, N lectures, N écritures, N incrémentations d'un entier, aucune comparaison, par rapport à un quicksort, et sur 100 millions de données on doit gagner pas mal).

Du coup, ce test de vitesse de sort() ne correspond pas vraiment à des conditions normales d'utilisation.

Francois