Le quicksort non-recursif et l'impact de l'insertionsort sur ses performances
Description
Je depose cette source en rapport avec une discussion sur les performances du tri rapide (quicksort) qui pourraient etre ameliorees en visant une implementation non-recursive. Je me suis penche sur l'apport cote performance d'une autre methode de tri elle aussi tres rapide, sur des morceaux du tableau a trier de taille moindre lors du processus.
J'ai pour cela , par recurrence, demontrer que la taille maximale de la pile a allouer pour sauvegarder les index de tableau de taille N est le nombre binaire le plus proche >= N note N2.Par exemple si votre tableau est de 1000 items, la pile ne depassera pas les 1024 items (512 index de debut et 512 index de fin).
Ici vous pouvez modifier le code a votre guise. J'ai utiliser un tableau d'entiers. Les variables pour tester les performances et l'impact sont INSERTION_SORT_LIMIT(taille limite du tableau en dessous de laquelle on realise un insertionSort au lieu d'un quicksort) et ARRAY_SIZE pour la taille du tableau.
J'espere que vous serez nombreux a realiser des tests et a les rapporter pour comparer, ou corriger et/ou ameliorer la source. Pour ma part voici le resultat pour un exemple-test de configuration:
Hardware: Hewlett-Packard m8307c
Intel Core2 Quad CPU Q6600 @ 2.40Ghz 2.40Ghz
RAM = 3Gb
Vista 32bits
INSERTION_SORT_LIMIT = 500
ARRAY_SIZE = 10000000;//10 millions
temps d'execution moyen : 818 ms (millisecondes).
J'ai pour cela , par recurrence, demontrer que la taille maximale de la pile a allouer pour sauvegarder les index de tableau de taille N est le nombre binaire le plus proche >= N note N2.Par exemple si votre tableau est de 1000 items, la pile ne depassera pas les 1024 items (512 index de debut et 512 index de fin).
Ici vous pouvez modifier le code a votre guise. J'ai utiliser un tableau d'entiers. Les variables pour tester les performances et l'impact sont INSERTION_SORT_LIMIT(taille limite du tableau en dessous de laquelle on realise un insertionSort au lieu d'un quicksort) et ARRAY_SIZE pour la taille du tableau.
Source / Exemple :
// voir le Zip - source main.cpp windows Visual c++ 2005 professionnel
Conclusion :
J'espere que vous serez nombreux a realiser des tests et a les rapporter pour comparer, ou corriger et/ou ameliorer la source. Pour ma part voici le resultat pour un exemple-test de configuration:
Hardware: Hewlett-Packard m8307c
Intel Core2 Quad CPU Q6600 @ 2.40Ghz 2.40Ghz
RAM = 3Gb
Vista 32bits
INSERTION_SORT_LIMIT = 500
ARRAY_SIZE = 10000000;//10 millions
temps d'execution moyen : 818 ms (millisecondes).
Codes Sources
A voir également
- Le quicksort non-recursif et l'impact de l'insertionsort sur ses performances
- Quicksort c - Forum C / C++ / C++.NET
- Chmod recursif - Forum PHP
- Quicksort c# ✓ - Forum C# / .NET
- Le chmod 777 , c'est quoi? - Conseils pratiques -PHP
- Quicksort pascal - Forum Delphi / Pascal
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.