Tri optimal ?

Bonjour,

Dans un projet sur lequel je bosse en ce moment, je dois implémenter un tri.

Jusque là, rien de très complexe...

Mais voila, quel algo choisir ?

Voici les détails :

Je doit trier un "buffer" de structures, qui ressemble à ça :

Code:

---

1 2 3 4 5 6 7 8

struct sEvenement { int m_position; char m_data01; char m_data02; char m_data03; char m_data04; };

---

Le buffer est déclaré comme ça :
(attention, le tableau evenements est bien un tableau de pointeurs vers des evenements alloués en mémoire)

Code:

---

1 2 3 4 5

struct sEvenementsBuffer { int numEvenements; sEvenement* evenements[MAX_EVEMENTS]; };

---

Bon, j'ai pas choisi le format de mes données, c'était là avant moi...

Je dois ecrire une fonction qui prend une structure sEvenementsBuffer en entrée et tri son tableau d'evenements par m_position croissante.

Il suffit donc de trier les pointeurs dans le tableau en fonction de :
evenements[i]->m_position

Voila les contraintes :

- 1024 éléments au maximum
- entre 50 et 100 éléments quand le système est "en charge"
- entre 0 et 20 éléments quand le système est "pépére"
- à priori, les données n'ont aucune raison d'être "presque triées" à l'avance
- ça doit aller très très vite

D'après ce que j'ai trouvé ici :
http://fr.wikipedia.org/wiki/Algorithme_de_tri

- le tri par insertion est le plus rapide pour de petites listes
- le "quicksort" est le plus rapide pour de plus grandes listes

Pour l'instant, je suis parti sur l'idée d'implémenter plusieurs algo en fonction du nombre d'éléments à trier.

Auriez-vous une super idée pour avoir un truc réélement efficace ?

Le quick sort est déjà incorporé à la bibliothèque standard via la fonction qsort(). Tout ce que tu as à faire, c'est écrire une fonction de comparaison pour tes structures, dont tu passeras l'adresse à qsort.

Le insertion sort, est en effet plus rapide pour les tableaux de moins de 15 éléments, mais franchement, je comprends pas pourquoi optimiser quand y en a pas besoin. Sans parler du risque d'introduire des bugs supplémentaires.

À moins que ça soit à but didactique, alors là, ok...

Edit : Oups, je croyais à la lecture de ta question que le sujet était en C, pas en C++, utilise plutôt std::sort() alors...

Merci de la réponse !

Citation:

---

mais franchement, je comprends pas pourquoi optimiser quand y en a pas besoin

---

Ben justement, ici il y a besoin !

Coder un algo de tri, c'est quand même pas bien compliqué, alors on peut très bien le faire à la main pour tenir compte des spécificités du problème et pas faire appel à une bibliothèque standard qui a une solution standard : toujours stable, mais pas forcement la plus performante.

Si ça peut te rassurer, il ya des parties de mon code qui ne sont pas du tout optimisées, mais elles tournent rarement.

Le tri de ces données fait partie d'un traitement dans un thread qui tourne en boucle, synchronisé sur du matos externe, avec une boucle toutes les 4-5 ms.

Donc si je peux gagner en efficacité sur ce tri, c'est pas negligeable.

Un truc comme

Code:

---

1 2 3

std::sort(evenements, evenements+MAX_EVEMENTS, &condition)

---

http://r0d.developpez.com/articles/algos-stl/#LII-E
Avec des vector se serait mieux peut être.
Ou peut être un set ou multi_set? (déja trié)




ou d'utiliser les
make_heap()
push_heap()
pop_heap()
sort_heap()
qui sera peut être plus rapide. J'ai tout compris de sont fonctionnement.
En gros si tes donné sont en forme heap (utiliser make_heap() pour convertir)
tu ajoute les éléments par un push_heap() et tu enlève les élément par un pop_heap().
Pour les trier un suffit d'utiliser sort_heap()

Au temps pour moi, il me semblait que si tu pouvais attendre d'avoir trié 1024 éléments, tu pouvais te permettre de perdre un peu de temps pour trier 15 éléments.

Disons que s'il est courant de dire qu'une optimisation prématurée est dangereuse, c'est qu'il y a une raison...

Citation:

---

il me semblait que si tu pouvais attendre d'avoir trié 1024 éléments, tu pouvais te permettre de perdre un peu de temps pour trier 15 éléments

---

Pas faux du tout... j'avais pas vu les choses comme ça.

En fait, il y a d'autres threads qui tournent pendant ce temps aussi, donc si je peux gagner du temps ici, ça en fait plus pour les autres...

Et 1024 éléments, c'est le cas le plus "critique" (qui ne devrait jamais arriver) en général, on est plutôt entre 50 et 100.

J'ai déjà une solution qui tourne et qui marche bien (avec un quicksort) disons que j'aimerais bien optimiser cette partie là du code pour libérer un peu de ressources.

J'ai essayé avec différentes variantes du quicksort, mais si l'algo devient trop complexe, je perds en performance (du genre quicksort puis tri par insertion en dessous de 16 éléments) ce que je ne m'explique pas vraiment.

Pour info, ça va plus vite que la STL, surement parceque la STL fait appel à "&condition" qui est un pointeur, donc à chaque fois qu'il evalue la condition, il doit déréférencer le pointeur, donc recharger un bout de mémoire en cache, etc...
(enfin, un truc de ce genre)

Citation:

---

Envoyé par buzzkaido

Pour info, ça va plus vite que la STL, surement parceque la STL fait appel à "&condition" qui est un pointeur, donc à chaque fois qu'il evalue la condition, il doit déréférencer le pointeur, donc recharger un bout de mémoire en cache, etc...
(enfin, un truc de ce genre)

---

si c'est optimisé, le code de condition est inline (en principe)

Ah ! C'est peut-etre parceque je suis en debug, alors ?

En debug le code est pas du tout optimisé (je dirai même franchement ralenti) ;)

Citation:

---

Envoyé par buzzkaido

Pour info, ça va plus vite que la STL, surement parceque la STL fait appel à "&condition" qui est un pointeur

---

Je serais curieux de voir comment tu as défini condition. Si c'est un pointeur sur fonction, c'est a priori sous optimal, et le remplacer par un foncteur devrait justement permettre l'inlining. C'est ce qui fait que std::sort est en général bien plus rapide que qsort.

Ensuite, faire des tests de perfs en debug n'a aucun sens. Selon les codes, un ralentissement (variable, bien évidemment) d'un facteur 1 à 10 est tout à fait classique.

Autrement, si tu as un faible nombre de positions, toutes différentes, et que la valeur de position est faible, effectivement un tri par insertion est probablement le plus rapide, puisqu'en O(n) et simple à mettre en oeuvre.