Discussion :

[camboui]

Voici une ébauche de code qui trie un vector, puis un autre vector sur des références des éléments du premier.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct IdStr
{
	unsigned id;
	std::string str;
	friend bool operator<(IdStr const & l, IdStr const & r) noexcept
	{
		int cmp = (l.id - r.id);
		return ((cmp == 0) ? (l.str < r.str) : (cmp < 0));
	}
};
void main()
{
	std::vector<IdStr> is;
	// remplir le vector is ...
 
	std::sort(is.begin(), is.end());
 
 
	std::vector<std::reference_wrapper<IdStr>> ris;
 
	// re-remplir le vector is ...
	ris.assign(is.begin(), is.end());
 
	std::sort(ris.begin(), ris.end());
}

Assez curieusement le tri des références est plus lent de l'ordre d'un bon 15%. J'aurais cru qu'il fasse au moins aussi bien puisque lors du tri les éléments déplacés ne sont jamais que des pointeurs et non pas des instances de structure (qui contient quand même un std::string dans mon exemple).
En bref, le coût CPU supplémentaire se trouve dans l'appel à la fonction de comparaison (rigoureusement la même dans les deux tris) qui pourtant ne fait qu'une indirection via le pointeur encapsulé dans la référence. Et je suis surpris que la différence soit aussi marquée.
Merci pour vos remarques.

[Bousk]

Hello,

cela ne me surprend pas, le reference_wrapper est un pointeur camouflé, donc l'indirection risque aussi de dire remise en cache. Concrètement tu perds probablement une bonne partie de l'intérêt du vector et sa contiguïté des données.

[koala01]

Salut,

De plus, il faut savoir que le simple fait de vouloir trier un ensemble qui est déjà trié (ou presque) te place "forcément" dans le pire des cas possible.

Quelle que soit la complexité de ton algorithme de tri, cela se passera comme lors du remplicage d'un arbre binaire: si les données sont fournies dans un ordre déjà trié, tu observera beaucoup plus de rotations dans tous les sens que si tu décidait de fournir les mêmes données dans un ordre dans lequel aucune rotation ne devait se produire (par exemple, dans l'ordre 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13,15)

Si is est déjà trié lorsque tu essayes de trier ris, tu ne dois pas t'étonner si ton algorithme de tri "travaille" plus longtemps pour trier ris, car tu sera forcément dans "le pire des cas" possible pour ton algorithme.

Peut-être t'y es tu pris autrement pour évaluer les performances, mais, si tu l'as fait avec le code que tu présentes ici, le résultat n'a pas grand chose d'étonnant à cause de ce "pire des cas"

[camboui]

Euh, non koala. J'ai bien sûr testé avec une disposition quelconque des éléments à chaque fois, voir mon commentaire "re-remplir le vector is" dans le pseudo-code fourni juste avant de travaller avec ris.
J'ai aussi testé avec un autre algorithme inspiré des "tris à clé " (un mix de "count sort" et "MSD radix sort") pour lequel il n'y a pas en théorie de "pire des cas" comme tu le dis
On est en complexité constante O(d(k+n)) (d et k étant des constantes indépendantes de n, avec d << k << n).

Bousk, je me suis souvent demandé comment programmer en tenant compte des optimizations possibles des processeurs quand on manipule des millions de données... Dans mes essais, peu importe le nombre de données, le constat est le même.

Merci

[dalfab]

La mémoire cache joue toujours un rôle, je pressens que les 15% seraient dus à des fautes de page. Et dans ce cas l'écart devrait diminuer pour de petits tableaux de l'ordre de centaines d'éléments.
Le mécanisme de cache gère bien des données lues successivement dans une zone contiguë. Les accès aléatoires sont par contre une plaie.
cas I. On a un vecteur de données relativement petites (cache favorisé si moins d'une ligne de cache par donnée soit 64 octets) qui pointent sur des chaînes dynamiques (cache perturbé).
cas II. On a un vecteur de pointeurs (cache favorisé) qui pointent sur des données (cache perturbé) qui pointent sur des chaînes dynamiques (cache perturbé).