[std::sort & std::vector] Quelle est la manière la plus rapide pour effectuer un tri ?

Bonsoir à tous ! :-]

Dans le projet que je confectionne actuellement avec la SFML, j'ai constaté une chute significative de FPS au fur & à mesure que j'affiche des sprites, au début je me suis dit " ben m**rde alors, ça bouffe tant de CPU que ça les sprites ? ", mais Que Nenni ! Je me suis finalement rendu compte que ce qui ralentissait mon programme au fur & à mesure que le nombre de sprite augmentait.. c'était ma fonction de tri !

J'ai conçu cette mini-fonction toute simple en utilisant une fonction lambda :

Code:

---

1 2 3 4 5 6

void Camera::sortFunction() { ///ON TRI LES SPRITES LES PLUS LOINS AUX PLUS PROCHES/// std::sort(m_vecSprites.begin(), m_vecSprites.end(), [](Sprite& s1, Sprite& s2) -> bool { return s1.getDistance() > s2.getDistance(); }); }

---

Le but étant de trier les sprites les plus loin jusqu'aux plus près de la caméra, je suis obligé de procéder à un tri dans mon cas de figure, mais quand je passe à 6,7 / 10,11 voir 15 sprites, mon programme rame énormément, comme si j'avais un vieux pentium 133mHz :mouarf:

Lorsque je retire cette fonction, mon programme redevient parfaitement fluide, j'ai mes 60 FPS, mais évidemment, mes sprites n'apparaissent pas le bon ordre car non triés...

Donc selon vous, comment pourrais-je essayer de procéder afin de pouvoir gérer un tri de manière rapide & optimisée ?
J'ai essayé d'appeler ma fonction dans un thread séparé, ça n'a rien changé au problème, hélas :-/

Merci à vous ! :mrgreen:

Le coût du tri est lié à la quantité de données à déplacer, si l'opération de swap entre 2 objets de la liste est lourde cela ralenti car on il doit se faire plus de cent fois.
Ce qui coûte aussi est l'appel de la fonction getDistance() qui sera elle encore plus appelée alors qu'il suffirait d'une fois par sprite.
Si le tri ne sert qu'à l'ordre d'affichage, on peut passer par une table d'index qui sera triée

Code:

---

1 2 3 4 5 6

std::vector<std::pair<double,std::size_t>> sprSorted(m_vecSprites.size()); for ( std::size_t i = 0 ; i < m_vectSprites.size() ; ++i ) sprSorted[i] = std::make_pair( m_vecSprites[i].getDistance() , i ); std::sort( sprSorted.rbegin() , sprSorted.rend() ); // tri du plus éloigné au plus proche for ( auto const& x : sprSorted ) m_vecSprites[x.second].display();

---

Salut à toi Dalfab, merci beaucoup de m'avoir répondu aussi rapidement, ce forum est super dynamique, c'est top !

J'irais tester ça dés que je serais rentré chez moi, merci encore & encore :-)

Donc, j'ai testé ta solution mais j'ai trouvé un équivalent beaucoup plus rapide que ma précédente fonction et surtout bien plus simple ! :-)

J'ai utilisé std::swap de la manière suivante :

Code:

---

1 2 3 4 5 6 7 8

void Camera::sortFunction() { for (short int i = 1 ; i < m_vecSprites.size() ; i++) { if (m_vecSprites[i].getDistance() > m_vecSprites[i-1].getDistance()) std::swap(m_vecSprites[i], m_vecSprites[i-1]); } }

---

Encore merci en tout cas ;)

Ce que tu fais là n'est pas un tri... Après ça, tes données seront un peu plus triées, mais pas totalement. Et pour qu'elles le soient totalement, il faudrait imbriquer 2 boucles de ce genre, et là tu aura un algorithme équivalent à std::sort, mais beaucoup moins performant.

Mais de toute façon, il n'y a aucune raison qu'un tri d’une quinzaine d'éléments ralentisse de manière mesurable ton rendu...

Quand tu parles de sprite, tu parles de sf::sprite, ou d’une classe à toi ? Si c'est une classe à toi, j'aimerais la voir. Sinon, un sf::sprite n'est pas quelque-chose d'ultra léger à copier (j'ai jeté un œil, et il y a grosso modo une centaine d'octets à copier), mais ce n'est pas non plus la mort (il n'y a pas d’allocation mémoire à faire, par exemple) et de toute manière, les std::swap doivent aussi faire les mêmes copies...

Dit autrement, je pense que ton problème n'est pas actuellement résolu, juste camouflé, et qu'il reviendra te poignarder dans le dos au moment le moins opportun...

Salut,

il n'y a rien à faire, quelque soit la méthode de tri envisagée, si tu t'amuse à trier tous les éléments d'une collection (quelle qu'elle soit : il s'agit d'un [c]std::vector[c] dans ton cas) tu dois t'attendre à ce que chaque élément de ta collection soit comparé avec tous les autres, ce qui fait un nombre de comparaison évoluant plus ou moins à la manière d'une factorielle.

Les choses sont encore pires lorsque tu dois trier des éléments lourds / dont la copie prend du temps, car, en plus de toutes les comparaisons, tu te tapes à chaque fois au moins trois copie par déplacement.

La première chose à faire est donc peut-être de faire en sorte de ne pas devoir faire autant de parcours de ta collection. Or, dans le cas que tu explique, il est tout à fait possible de le faire. Je m'explique:

Tu veux trier tes sprites par rapport à la distance qui les sépare de la caméra (sur l'axe des Z). Mais chaque éléments n'a que trois choix possible:

1. soit il s'approche de la caméra et "dépasse" donc éventuellement les éléments qui sont "devant lui", mais ceux qui sont "derrière lui" n'ont aucun intérêt
2. soit il s'éloigne de la caméra se fait fait donc éventuellement "dépasser" par les élément qui sont "derrière lui", mais ceux qui sont "devant lui" n'ont aucun intérêt
3. soit il reste "à la même distance" de la caméra, et il n'y a donc rien à faire

Cela signifie que l'on peut donc déjà très fortement limiter le nombre de comparaisons et de déplacements en évitant d'aller comparer notre élément courant à ceux qui "n'ont aucun intérêt", sous une forme qui serait proche de

Code:

---

1 2 3 4 5 6 7 8 9

Si 'élément courant avance Tant qu'il y a un élément précédant et que élément précédant a été dépassé intervertir élément courant et élément précédant Fin Tant Sinon Si élément courant recule Tant qu'il y a un élément suivant et que élément courant a été dépassé par l'élément suivant intervertir élément courant et élément suivant Fin Tant Fin Si

---

(je te laisse traduire cela en C++ ;) )
Cela signifie que, dans le pire des cas,

1. si l'élément avance, il ne sera comparé qu'une seule fois à tous les éléments qui le précèdent
2. si l'élément recule, il ne sera comparé qu'une seule fois à tous les élément qui le suivent

Tu me diras que cela revient finalement grosso modo au même qu'avec n'importe quelle fonction de tri (vu que ce sera quand même effectué pour chaque élément qui se déplace). Mais il y a quand même de grosses différences parce que:

1. il y a "toute une partie" des éléments qui seront ignorés, selon le sens du mouvement (voire tous, si l'élément ne se déplace pas sur l'axe des Z)
2. Soit il n'y a plus d'élément devant / derrière l'élément (selon le sens du déplacement) courant, et on a fini, soit l'élément qui se trouve devant / derrière (selon le sens du déplacement) n'a pas été dépassé par l'élément courant (respectivement n'a pas dépassé l'élément courant), et cela ne sert donc à rien de vérifier les autres.

La deuxième chose à faire, ce sera d'éviter les copies inutiles d'éléments (de sf::Sprite dans ton cas):Il faut savoir en effet que le processus de copie d'un élément prend du temps et tu as trois copies qui sont effectuées lors de l'inversion de deux éléments (nommons les A et B), car la logique est proche de

Code:

---

1 2 3 4 5

soit Temp est un élément du type adéquat: Temp = A (première copie) A = B (deuxième copie) B = Temp (troisième copie)

---

Avant l'arrivée de C++11, on aurait sans doute travaillé avec des pointeurs, car un pointeur n'est jamais qu'une valeur numérique entière (généralement non signée) représentant l'adresse mémoire à laquelle on devrait trouver un élément du type qui nous intéresse.

On ne pouvait pas utiliser les références à l'époque parce que les règles sur les références font qu'on ne peut pas faire en sorte qu'une référence fasse référence à un autre élément que celui qui lui a été assigné au moment de sa définition en cours d'utilisation et parce que l'on ne peut pas créer une collection de références.

Autrement, une référence n'est jamais qu'un pointeur bien déguisé, et elle sera représentée dans le code binaire final utilisable par le processeur sous la forme d'un pointeur ;)

Mais C++11 est arrivé avec une classe géniale qui lève ces restriction en nous permettant la création d'un objet contenant une référence. Objet qu'il est possible de placer dans une collection et que l'on peut "réassigner" afin de changer l'élément référencé. Je veux bien sur parler de la classe std::reference_wrapper.

Tu peux donc utiliser un std::vector<std::reference_wrapper<sf::Sprite>> et le manipuler (à peu de chose près: il faut utiliser tab[i].get()./* la fonction qui t'intéresse*/) exactement comme si tu manipulait ton tableau de sf::Sprite, les copie inutiles en moins ;)

Citation:

---

Envoyé par koala01

Tu veux trier tes sprites par rapport à la distance qui les sépare de la caméra (sur l'axe des Z). Mais chaque éléments n'a que trois choix possible:

1. soit il s'approche de la caméra et "dépasse" donc éventuellement les éléments qui sont "devant lui", mais ceux qui sont "derrière lui" n'ont aucun intérêt
2. soit il s'éloigne de la caméra se fait fait donc éventuellement "dépasser" par les élément qui sont "derrière lui", mais ceux qui sont "devant lui" n'ont aucun intérêt
3. soit il reste "à la même distance" de la caméra, et il n'y a donc rien à faire

---

En résumé :mrgreen: partition binaire de l'espace (<- lien wiki)

Citation:

---

Envoyé par koala01

il n'y a rien à faire, quelque soit la méthode de tri envisagée, si tu t'amuse à trier tous les éléments d'une collection (quelle qu'elle soit : il s'agit d'un [c]std::vector[c] dans ton cas) tu dois t'attendre à ce que chaque élément de ta collection soit comparé avec tous les autres, ce qui fait un nombre de comparaison évoluant plus ou moins à la manière d'une factorielle.

---

Aucun algorithme de tri couramment utilisé n'a un nombre de comparaisons qui "[évolue] plus ou moins à la manière d'une factorielle". Il existe bien un algorithme de tri qui a cette propriété et qui s'appelle le tri stupide (bogosort), mais c'est seulement une farce.

Les algorithmes de tri simples mais généralement peu performants, comme le tri à bulle, le tri par sélection et le tri par insertion, ont un nombre de comparaisons moyen en O(n²). Le nombre moyen de swaps est aussi un O(n²), sauf dans le cas du tri par sélection où il ne dépasse pas n - 1.

Les algorithmes de tri performants, comme le tri fusion, le tri par tas et introsort, ont un nombre de comparaisons en O(n log n). Idem pour le nombre de swaps.
Le tri rapide a aussi un nombre de comparaisons moyen en O(n log n), mais peu s'élever à O(n²) si les éléments sont, au départ, triés dans l'ordre inverse. Idem pour le nombre de swaps.

Citation:

---

Envoyé par Pyramidev

Le tri rapide a aussi un nombre de comparaisons moyen en O(n log n), mais peu s'élever à O(n²) si les éléments sont, au départ, triés dans l'ordre inverse. Idem pour le nombre de swaps.

---

Sauf si on prend le pivot au hasard, ce que font toutes les implémentations un peu sérieuses.

Citation:

---

Envoyé par Pyramidev

Le tri rapide a aussi un nombre de comparaisons moyen en O(n log n), mais peu s'élever à O(n²) si les éléments sont, au départ, triés dans l'ordre inverse. Idem pour le nombre de swaps.

---

Citation:

---

Envoyé par JolyLoic

Sauf si on prend le pivot au hasard, ce que font toutes les implémentations un peu sérieuses.

---

Je croyais que le pivot était, en pratique, le premier élément ou le dernier du sous-tableau.
Je viens de regarder l'implémentation de std::sort dans GCC 7.1.0, qui utilise introsort, donc qui commence par un tri rapide et qui continue par un tri par tas si le compteur de récursion dépasse une certaine constante fois log n.
Le choix du pivot n'est pas aléatoire, mais est assez astucieux : Dans le sous-tableau, l'implémentation compare le deuxième élément, celui du milieu et le dernier. Parmi ces trois, elle choisit comme pivot celui qui n'est ni le plus petit, ni le plus grand.
Du coup, en effet, le cas où le nombre de comparaisons est un O(n²) n'est pas celui où les éléments sont, au départ, triés dans l'ordre inverse.

Citation:

---

Envoyé par Pyramidev

Le choix du pivot n'est pas aléatoire, mais est assez astucieux : Dans le sous-tableau, l'implémentation compare le deuxième élément, celui du milieu et le dernier. Parmi ces trois, elle choisit comme pivot celui qui n'est ni le plus petit, ni le plus grand.

---

Cette méthode s'appelle le median of three

Citation:

---

The median of three has you look at the first, middle and last elements of the array, and choose the median of those three elements as the pivot.

To get the "full effect" of the median of three, it's also important to sort those three items, not just use the median as the pivot -- this doesn't affect what's chosen as the pivot in the current iteration, but can/will affect what's used as the pivot in the next recursive call, which helps to limit the bad behavior for a few initial orderings (one that turns out to be particularly bad in many cases is an array that's sorted, except for having the smallest element at the high end of the array (or largest element at the low end). For example:

Compared to picking the pivot randomly:

*) It ensures that one common case (fully sorted data) remains optimal.
*) It's more difficult to manipulate into giving the worst case.
*) A PRNG is often relatively slow.

---

Trouvé sur stackoverflow, désolé pour l'anglais :oops: