Tri stable rapide pour les petits tableaux (sous 32 ou 64 éléments)

Question

La sagesse commune indique que pour les tableaux suffisamment petits, le tri par insertion est le meilleur. Par exemple, Timsort utilise le tri d'insertion (binaire) pour les tableaux jusqu'à 64 éléments; de Wikipedia:

Certains algorithmes diviser pour régner tels que le tri rapide et tri mergesort en divisant la liste récursive en sous-listes plus petites qui sont ensuite triés. Une optimisation utile en pratique pour ces algorithmes est d'utiliser le tri d'insertion pour trier de petites sous-listes, car le tri d'insertion surpasse ces algorithmes plus complexes. La taille de la liste pour laquelle le tri par insertion a l'avantage varie selon l'environnement et la mise en œuvre, mais se situe généralement entre huit et vingt éléments.

Est-ce réellement correct? Y a-t-il de meilleures alternatives?

Dans le cas où cela dépend beaucoup de la plate-forme, je suis très intéressé par .NET.

Answer 1

Oui, c'est ce que j'ai appris dans mes classes d'algorithmes. C++ STL. Un article de Wikipédia:

Le Juin 2000 SGI C++ Standard Library Modèle stl_algo.h mise en œuvre de type instable utilise la Musser introsort approche avec la profondeur de récursivité pour passer à HeapSort passé en paramètre, médian de -3 sélection du pivot et la passe de tri d'insertion finale Sedgewick . L'élément seuil de passage au simple tri par insertion était 16.

J'ai fait quelques tests de performance informelle l'an dernier et STL std :: de tri de C était environ deux fois plus vite que dans Array.Sort .NET. Je ne sais pas comment .NET Array.Sort est implémenté, mais dans .NET, un accès dans un tableau nécessite une vérification des limites, contrairement à C++, ce qui pourrait largement expliquer la différence de performance.

Answer 2

Depuis .NET est un langage qui ne compile pas en raw machinecode. Je dirais que l'appel d'une fonction API (qui utilise du code natif) est probablement le moyen le plus rapide.

Answer 3

J'ai trouvé que cela dépend vraiment du travail que la fonction de comparaison doit faire. Comme si je triais indirectement des lignes d'une feuille de calcul, et que chaque comparaison impliquait l'extraction d'une ligne et la comparaison éventuelle de plusieurs colonnes, en mélangeant éventuellement des valeurs numériques et des chaînes, elle pouvait être lente. D'autre part, si la longueur du tableau est courte, cela dépend du nombre de fois que vous avez besoin de le trier, car même s'il est relativement lent comparé à ce qu'il pourrait être, vous ne remarquerez peut-être jamais la différence.

Si j'ai le moindre doute, je viens de coder un tri de fusion et aller avec ça. J'ai eu une mauvaise expérience avec qsort n'étant pas stable et prenant parfois beaucoup de temps. Le tri par fusion codé à la main est simple, fiable et assez rapide.

Answer 4

Il n'existe pas d'algorithme O (n log n) plus rapide que le tri par insertion pour les petites listes. Cependant, il existe certains algorithmes O (n^2) qui sont en concurrence. Notamment, le tri sélectif n'en fait pas partie, bien qu'il soit bon dans la rare situation où les swaps et les moves sont chers. Le tri des bulles et les variantes sont également tout simplement mauvais.

Tri du réseau: Algorithme de tri, toujours stable, sans branches.Il a des caractéristiques terribles dans l'ensemble, mais aucune branche signifie une performance stellaire sur la plus petite des listes. Le cas de base est le suivant: if(a<b) swap(a,b);

Tri par insertion avec lots: Sur chaque boucle, trier 2 à 4 éléments, puis les insérer ensemble. Cela réduit le nombre de mouvements et les compare de 25 à 37% pour les listes plus longues. L'effet global est l'optimisation pour les listes dans la plage de taille 16 à 64.