Ce topic est là pour faire découvrir à ceux qui ne connaissent pas un algorithme de tri peu connu, récent (2002), très efficace en pratique et basé sur les comparaisons. Je parle du Timsort (lien en anglais, je n'ai pas trouvé d'article équivalent en français). Il est surtout connu des Pythoneux puisqu'il s'agit du tri standard de ce langage (qu'on me corrige si je me trompe, je ne m'y connais absolument pas en Python). Je propose plus bas des bench comparant mon implémentation de Timsort (en C++) à std::sort.
std::sort est un peu le maître du tri en C++, c'est une fonction standard que vous pouvez retrouver dans l'entête <algorithm>. Dès qu'il est question de trier des objets par comparaison, on la recommande immédiatement. Quand on trie des entiers, on nous conseille Bucketsort, qui a l'avantage d'être linéaire quand les entiers sont plus ou moins uniformément répartis. Quand les données sont presque triées, on recommande un Smoothsort ou éventuellement un tri par insertion. Eh bien Timsort, sachez-le, est une excellente alternative dans le cas "général".
Complexité
std::sort est généralement implémentée par un Introsort . L'avantage, c'est que cette fonction présente toujours une complexité en <math>\(O(n\log{n})\)</math>, quelque soit le niveau de désordre de l'entrée.
Timsort est beaucoup plus intéressant, puisque en moyenne, il est tout aussi efficace que std::sort, et dans le cas d'une entrée presque déjà triée, il est linéaire !
Timsort
Introsort
Tri rapide
Tri par insertion
Au meilleur des cas
<math>\(O(n)\)</math>
<math>\(O(n\log{n})\)</math>
<math>\(O(n\log{n})\)</math>
<math>\(O(n)\)</math>
En moyenne
<math>\(O(n\log{n})\)</math>
<math>\(O(n\log{n})\)</math>
<math>\(O(n\log{n})\)</math>
<math>\(O(n^2)\)</math>
Au pire des cas
<math>\(O(n\log{n})\)</math>
<math>\(O(n\log{n})\)</math>
<math>\(O(n^2)\)</math>
<math>\(O(n^2)\)</math>
Principe
Timsort reprend en réalité le nom de son inventeur, Tim Peters. C'est un algorithme qui combine intelligemment les avantages du tri par insertion et du tri fusion. Voici les étapes qu'effectue l'algorithme pour trier ses données :
En parcourant l'entrée, on détermine les sous-ensembles déjà triés ou triés en sens inverse. On les appelle "runs". Quand un run inversement trié est trouvé, on l'inverse (c'est linéaire) ;
Si un run est trop petit, on y insère des éléments à l'instar du tri par insertion, pour augmenter sa taille jusqu'à une certaine limite acceptable ;
Quand tous les runs ont une taille correcte (ie. pas trop petite), on les fusionne deux à deux à la manière d'un tri fusion. On fusionne jusqu'à aboutir à l'ensemble final trié.
C'est en quelque sorte un tri fusion qui part des runs et non plus d'une division naïve. Du coup, il devient clair que dans le cas d'une entrée presque déjà trié, le tri est linéaire : puisque beaucoup d'éléments sont déjà triés, on ne détermine que très peu de runs. Leur fusion se fait alors très rapidement.
Dans le cas d'une entrée déjà entièrement triée, la première étape de l'algorithme ne va déterminer qu'un seul run et... c'est fini. Si l'entrée est triée en sens inverse, Timsort va l'identifier comme un seul run et simplement l'inverser. C'est très efficace !
Déterminer efficacement les runs peut se faire en temps linéaire en se basant sur un tableau de pointeurs (qui pointent dans l'entrée sur le début de chaque run). Implémenter cet algorithme est d'ailleurs un excellent exercice pour se familiariser avec les automates à états.
Au pire des cas, le tri nécessitera un tableau de N/2 pointeurs où N est la taille de l'ensemble à trier. En effet, les plus petits runs qui puissent exister sont de taille 2 : deux éléments consécutifs sont forcément triés ou inversement triés. Mais autant dire que ce pire des cas en terme de complexité mémoire (et algorithmique !) ne doit pas apparaitre souvent...
Exemple
L'exemple concret qui suit ne travaille que sur une liste de petite taille, il n'est donc pas nécessaire, pour les explication, d'ajouter l'idée d'insertion pour augmenter la taille des runs trop petits.
Commentaire
Liste
On part d'une liste non-triée
7 5 3 8 1 2 4 6 9 0
Timsort va d'abord identifier les runs
(7 5 3) (8 1) (2 4 6 9) (0)
Avant d'inverser ceux qui sont triés dans le mauvais sens
(3 5 7) (1 8) (2 4 6 9) (0)
Ces runs sont ensuite fusionnés deux à deux à la manière d'un tri fusion
(1 3 5 7 8) (0 2 4 6 9)
Et vu qu'il reste au moins une paire de runs, on continue à fusionner deux à deux
(0 1 2 3 4 5 6 7 8 9)
Et c'est fini !
0 1 2 3 4 5 6 7 8 9
Benchs
Sur des entrées presque déjà triées, Timsort est beaucoup plus efficace que n'importe quel algorithme qui se veut optimal. Sauf peut-être Smoothsort, mais ce dernier est bien plus difficile à implémenter.
J'ai moi-même écrit une implémentation d'un Timsort simplifié : je ne vérifie pas la taille des runs en vue d'y insérer des éléments quand ils sont trop petits. On y gagne quand l'ensemble est presque trié, on y perd quand il y règne un désordre monstre. En attendant, c'est une implémentation qui respecte l'idée sous-jacente du Timsort qui consiste à profiter du caractère "presque trié" de certaines entrées, et en pratique cela arrive très souvent.
Vous retrouverez cette implémentation un peu plus bas. En attendant, je vous propose de comparer son efficacité à std::sort et au tri par tas (Heapsort) en comparant les temps d'exécution des trois algorithmes (en seconde) sur des entrées très variées. Pour chaque ligne, le temps le plus court est écrit en rouge. Il correspond donc à l'algorithme le plus rapide. Vous jugerez vous-même de ce qu'il en est :
Taille de l'entrée
Caractéristique
Timsort
std::sort
Heapsort
10K éléments
triés
0.000s
0.002s
0.012s
presque triés
0.001s
0.008s
0.013s
aléatoires
0.018s
0.006s
0.013s
100K éléments
triés
0.004s
0.026s
0.094s
presque triés
0.028s
0.051s
0.095s
aléatoires
0.120s
0.055s
0.101s
1 million d'éléments
triés
0.040s
0.188s
0.964s
presque triés
0.226s
0.663s
0.979s
aléatoires
1.150s
0.671s
1.030s
10 millions d'éléments
triés
0.239s
1.806s
11.043s
presque triés
1.734s
3.512s
11.098s
aléatoires
13.125s
13.324s
11.295s
Personnellement, ces performances m'ont séduit.
Implémentation
L'implémentation suivante se base sur deux random access iterator et, en interne, sur une std::list d'itérateurs qui marquent le début de chaque run. On remarque que dans les benchs, std::sort dépasse presque toujours Timsort dans le cas d'une entrée très désordonnée. On peut espérer mieux comme résultat, notamment en implémentant également l'insertion dans les petits runs.
template < typename RAIterator >
void timsort(RAIterator begin, RAIterator end)
{
if(begin == end || begin+1 == end)
return;
std::list < RAIterator > limits;
limits.push_back(begin);
int order = 2; // 1 : up | 0 : down | 2 : indeterminate
// find and order (if necessary) ordered subsets (runs) in [begin, end)
for(RAIterator forward = begin+1; forward != end; ++forward)
{
if(*(forward-1) < *forward)
{
if(order == 2)
order = 1;
else if(order == 0)
{
std::reverse(limits.back(), forward);
limits.push_back(forward);
order = 2;
}
}
else
{
if(order == 2)
order = 0;
else if(order == 1)
{
limits.push_back(forward);
order = 2;
}
}
}
if(order == 0)
std::reverse(limits.back(), end);
limits.push_back(end);
// merge sort starts with the determinated subsets (runs)
while(limits.size() != 2)
{
typedef typename std::list < RAIterator >::iterator iterator;
iterator a, b, c;
for(a = limits.begin();;)
{
b = a; std::advance(b, 1); // b = a+1
c = b; std::advance(c, 1); // c = a+2
if(b == limits.end() || c == limits.end())
break;
std::inplace_merge(*a, *b, *c);
a = limits.erase(b);
}
}
}
Liens
J'espère que ce petit topic vous aura intéressé et donné l'envie d'aller plus loin. Et justement, je vous propose pour conclure quelques liens sur Timsort très intéressants :
Ce topic est ouvert à tous. Si vous voulez poster pour donner votre avis sur cette méthode de tri, la comparer à d'autres (par exemple smoothsort), proposer d'autres implémentations (voire dans d'autres langages), d'autres bench, ou pour toute remarque, n'hésitez pas !
Intéressant comme technique. Tu ne mentionnes pas le O(n) spatial qui apparaît dans le pire cas et qui peut franchement être rédibitoire. Il serait intéressant de connaître le coût mémoire sur des cas réels.
Il me semble que ce O(n) en mémoire peut être transformé en ln(n). Au final, cela ne doit donc pas trop gêner si c'est le cas. Par contre, cela se fait avec de légéres contreparties en temps d’exécution.
Nanoc : Effectivement je ne parle pas de la complexité mémoire asymptotique, mais je précise quand même que :
"Au pire des cas, le tri nécessitera un tableau de N/2 pointeurs où N est la taille de l'ensemble à trier"
Oui ça peut être intéressant, je ferai surement quelques tests pour "voir" ce qui se passe au niveau de cette liste de pointeurs. Merci pour ce commentaire.
Edit : Mewtow : J'y ai pensé en écrivant le message. Peut-être en fusionnant directement ce qui peut être fusionné. Un peu comme une opération qu'on exécute dès que les opérandes sont prêts.
Il me semble que ce O(n) en mémoire peut être transformé en ln(n). Au final, cela ne doit donc pas trop gêner si c'est le cas. Par contre, cela se fait avec de légéres contreparties en temps d’exécution.
Oui. Il serait donc intéressant de voir ce que cela donne au niveau performance si l'on impose cette contrainte au niveau de la taille mémoire utilisée.
Algorithme fort intéressant !
Et c'est implanté dans python. Mais est ce qu'il est possible que ce soit le cas également dans qsort en C, les algos de tris STL ?
Tu ne pourrais pas avoir de meilleures perfs avec autre chose qu'une std::list qui va passer son temps dans son allocateur ?
J'avais essayé avec un système de file, puis de pile, puis les deux. Puis avec une deque. Y'a rien qui me permettait de faire aussi rapidement ce que je fais là avec une liste (ie. parcourir la liste d'itérateurs et en supprimer à chaque passage un sur deux). Peut-être une forward_list oui.
Citation : Fvirtman
Mais est ce qu'il est possible que ce soit le cas également dans qsort en C, les algos de tris STL ?
D'après Wikipédia, il serait utilisé dans Java SE 7 pour trier des tableaux et sur Android (source).
Nanoc : je vais voir si je peux implémenter ça facilement (si d'autres veulent essayer de leur côté, c'est tout à leur honneur).
Je pensais surtout à une liste mono-allocation -- avec une entrée : premier truc vide (qui linke vers le prochain), et une entrée premier truc plein (qui linke vers le prochain)
C'est le principe de fonctionnement des allocateurs (genre malloc): une seule très grosse alloc. Puis des chainons intrusifs: valeur + lien vers suivant. Et pour le parcours tu as deux chainons vraiment à part: celui des éléments, et celui des non-éléments.
Ce qui fait que la liste ne perd aucun cycle dans les allocations. Chose qui je soupçonne peut s'avérer très pénalisante dans un algo de tri -- c'est un peu la raison qui fait que les vecteurs sont généralement bien plus performants que les std::list en deçà de quelques milliers d'éléments, et qu'il s'agit du container recommandé par défaut en C++.
ton tableau est vachement bien, j'adore voir ce genre de stats.
Néanmoins, Je veux pas faire ma mauvaise langue, mais je ne trouves pas ces statistiques en faveur de Timsort. En effet, il semblerait que cet algo soit surtout efficace sur les trucs presque triés ou triés, et qu'à moins d'atteindre la dizaine de millions d'éléments, ses performance sont moindre comparées au qort, (en plus à 10M la différence n'est pas énorme). Et je rejoins d'une certaine manière Nanoc en disant que de manière générale, un algo qui améliore grandement la complexité en temps le fait forcément au détriment de la complexité mémoire. et le tri quantique en log(n) on en parle pas !?
Si on devait se passer d'un algorithme parce qu'on n'y gagne que quelques fractions de seconde, on irait pas loin. Le truc c'est que (il parait que) dans des cas concrets, les entrées sont souvent presque triées. Et c'est ça qui motive l'utilisation d'un tel algorithme.
En plus sur une entrée presque triée, Timsort présente une complexité algorithmique en O(n), et une complexité mémoire proche du constant (peu de runs -> peu de pointeurs à stocker). Si l'entrée est triée, l'algorithme est en O(n) et sa mémoire en O(1), alors que std::sort sera en O(n*log(n)) et sa mémoire de l'ordre de O(log n) (selon le pivot...)
Pour l'instant oui, dans le cas d'une entrée très désordonnée, std::sort reste la solution la plus rapide. Mais dans mon implémentation, je n'ai pas implémenté l'insertion pour "gonfler" les runs trop petits (et je pense que ça peut pas mal changer les perfs) et cf lmghs pour std::list. Je suis convaincu qu'on peut encore faire plus rapide.
Je ne connaissais pas ce tri là.
Cependant pour que ton benchmark soit complet, et que tes arguments aient plus de poids, il faudrait que tu définisses clairement la notion de "tableau presque trié". Parce que "presque" ne veut rien dire en science :).
Il me semble qu'il y a une définition connue, qui dépend d'un nombre N, qui ressemble à ça: un tableau v est N-trié si la position de chaque élément de v est à une distance <= N de sa position dans le tableau v trié.
Si tu utilises cette définition, il faudrait que "N" apparaissent dans le benchmark.
Sinon il y a un autre tri intéressant mais dont tout le monde semble ignorer l’existence : le radix sort. Un tri avec une complexité linéaire quelque soit le cas (trié, N-trié, aléatoire, etc...). En contrepartie, il ne trie que les nombres entiers (même si adaptable à d'autres structures, au coût d'une implémentation bien plus complexe^^)
Pourquoi tu cherches compliqué pour définir "presque trié" ? C'est surtout un concept intuitif : quand tu as sous les yeux une suite de nombres qui parait plus ou moins dans l'ordre à quelques erreurs près, tu peux dire qu'elle est presque triée, sans pour autant faire intervenir ta définition mathématiquement de "N-trié" (qui est typiquement le genre de formalisme dont je ne vois pas l'intérêt...)
Le radixsort est potentiellement moins rapide que timsort, et plus gourmand en mémoire. Quelques raisons de préférer timsort à radixsort :
- Timsort est au mieux en O(n), radixsort au mieux (et au pire) en O(k*n), où k représente le nombre maximal de chiffres que l'on peut trouver parmi les n éléments.
- Timsort a une complexité spatiale (si on l'optimise) au pire en O(log n) et au mieux en O(1), alors que radixsort a la même complexité spatiale qu'algorithmique, O(kn).
- Timsort étant basé sur les comparaisons, on peut le paramétrer pour qu'il tri dans un ordre plus "complexe" que l'ordre lexicographique. Ce n'est pas le cas du radixsort.
Et mine de rien, j'ai souvent entendu parler du radixsort, alors que Timsort...
Pourquoi tu cherches compliqué pour définir "presque trié" ? C'est surtout un concept intuitif : quand tu as sous les yeux une suite de nombres qui parait plus ou moins dans l'ordre à quelques erreurs près, tu peux dire qu'elle est presque triée, sans pour autant faire intervenir ta définition mathématiquement de "N-trié" (qui est typiquement le genre de formalisme dont je ne vois pas l'intérêt...)
Je comprends bien ce que tu veux dire par tableau presque trié^^. Mais à partir du moment où tu parles de complexité sur un tableau presque trié, il me semble nécessaire de définir clairement de quoi tu parles. Surtout qu'un de tes arguments en faveur du Timsort est qu'il est efficace sur ce type de tableau.
Je me mets à la place de quelqu'un intéressé par le Timsort car j'ai des tableaux presque triés à trier. Mais j'aimerais bien savoir à quel point l'algo sera efficace, et à quel point nos deux notions de tableaux presque triés correspondent.
D'où la nécessité de formaliser un peu le benchmark.
En ce qui concerne le radix sort :
- k est une constante "petite" qui va dépendre de l'implémentation du tri.
- La complexité spatiale n'est pas très importante par rapport à la complexité temporelle aujourd'hui, surtout sur un PC.
- Le point fort du radix sort est qu'il est stable : même complexité dans le meilleur et dans le pire des cas.
Sinon je pense que le timsort est plus efficace pour les tableaux presque triés. Chaque tri a un point fort^^.
A la rigueur, ce serait bien de savoir pour chaque taille de tableau, à partir de quelle quantité d’éléments pas à leur place (pas triés quoi...) le TimSort devient plus lent que le QuickSort. Ce serait un indicateur assez objectif, comparé à des indicateurs du style 20% trié, qui me sembleraient assez arbitraires.
Laugilus -> Il me semble que justement, le radix sort est plus lent que le quicksort dans la grosse majorité des cas. La raison serait une mauvaise interaction de cet algorithme avec la (ou les) mémoire cache du processeur et la mémoire virtuelle. C'est un peu le problème des algorithmes qui ont une mauvaise complexité spatiale, ou qui pré-calculent beaucoup : leur complexité en terme de cache miss est parfois mauvaise à cause de cela. Bien sur, cela dépend aussi de leur localité, mais il faut se méfier un peu des algorithmes prenant trop de mémoires.
Pour ce que dit lmghs, j'ai pas regardé en détail, mais ca doit se faire en prenant un des allocateurs de boost::pool comme allocateur de std::list.
Et si je comprends bien, l'interet de la liste se situe dans le passage des merges. A la place d'en supprimer un sur deux "physiquement" on pourrait le faire "virtuellement". Par exemple utiliser un std::vector et par dessus le concept de range (boost::range) avec un "strided adaptator" bien choisis à chaque tour.
@shareman: Comment tu as construit tes entrées "presque triées" ? Ca répondra directement à la question de Laugilus sans avoir besoin d'expliciter le formalisme d'une telle entrée.
A la rigueur, ce serait bien de savoir pour chaque taille de tableau, à partir de quelle quantité d’éléments pas à leur place (pas triés quoi...) le TimSort devient plus lent que le QuickSort. Ce serait un indicateur assez objectif, comparé à des indicateurs du style 20% trié, qui me sembleraient assez arbitraires.
Honnêtement je n'y crois pas trop. Les vitesses d'exécution dépendent trop de l'architecture sur laquelle on effectue le test, et puis il faudra vraiment voir ce qui se passe exactement au niveau des runs quand on change un élément de place, ça me parait bien bien compliqué et quand bien même on arriverait à quelque chose, ça ne serait pas significatif (amha). Mais je parle peut-être un peu vite.
De toute façon je vais déjà voir si j'obtiens de meilleurs résultats en implémentant l'insertion dans les miniruns. Au même titre qu'un bon sedgesort est plus rapide qu'un quicksort, ça doit pouvoir jouer sur les benchs.
Freedom : Effectivement, ça pourrait le faire. De toute façon, il faut tester (ce que je vais faire).
Pour la méthode de génération des entrées presque triées, j'avais testé deux méthodes :
- Shellsort partiel (allure générale triée)
- std::partial_sort (un peu plus particulier)
Les deux me donnaient à peu près les mêmes résultats vis à vis de Timsort.
Edit :
Citation : Laugilus
Le point fort du radix sort est qu'il est stable : même complexité dans le meilleur et dans le pire des cas.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html