Au passage, puisqu'on parle de tri, je me demandais quel était le meilleur compromis temps/mémoire sur un grand nombre de données, pour des systèmes embarqués par exemple ?
Au passage, puisqu'on parle de tri, je me demandais quel était le meilleur compromis temps/mémoire sur un grand nombre de données, pour des systèmes embarqués par exemple ?
Les systèmes embarqués, ca recouvre beaucoup de choses et beaucoup de contraintes. Et par un "grand nombre de données" je vais supposer que tu veux dire "comportement quadratique inacceptable".Envoyé par progman
Un quicksort peut être bon mais a deux risques: si normalement il faut de la mémoire en log(N) en plus des données pour obtenir un temps en N log N avec une des meilleures constantes qui existe le comportement peut dégénéré et devenir linéaire en mémoire et quadratique en temps ce qui peut être un risque inacceptable.
Un heapsort a des avantages: en place avec une occupation constante en plus et un comportment N log N garanti même si la constante est moins bonne que le quick sort.
Puis il y a les algorithmes adaptatifs qui commencent comme un quicksort mais se terminent en heapsort s'ils détectent des données qui font dégénérer le quicksort. Mais l'implémentation est plus complexe.
Naturellement, si les données sont dans une liste chainée, un merge sort est quasiment imbattable: en place, comportement N log N en temps avec une constante faible qui peut dégénérer en comportement linéaire sur des données presque triées (ce que le heapsort ne fait pas mais le quicksort bien).
Je vois 2 problèmes de plus au quicksort
1- La récurrence ne permet pas de prévoir la quantité de stack qui va être nécessaire. Hors un problème à ce niveau induit inéluctablement une nécessité de reset voir reboot avec perte des données en cours. Le nombre de réentrances est entre autre fonction du choix du pivot ce qui est de loin pas facile à optimiser.
2- il n'est pas stable ( => si des éléments sont identiques au regard du test de comparaison ils peuvent tout de même être échangés ce qui peut poser dans certains cas des problèmes)
Il est tout de même en général plus rapide que tri par tas (heapsort) et je l’utilise de façon standard sur PC où la pile n’est pas réellement un problème ( pour mes applications ) mais l’évite sur les systèmes embarqués ( raison 1 ).
C'est ce à quoi je faisais allusion en parlant de quantité de mémoire nécessaire pouvant être linéaire. Mais en fait il y a une astuce permettant d'y échapper.Envoyé par j.p.mignot
Si on teste la taille des partitions, on peut faire d'abord la partition la plus petite et ensuite la partition la plus grande. Comme le tri de la partition la plus grande est un appel terminal (tail call), il peut être remplacé par une itération (soit par le compilateur, soit manuellement) et donc on n'a pas besoin de plus de O(log N) appels récursifs consommant de la pile. C'est toujours plus que pour le heapsort mais au moins on a une borne beaucoup plus raisonnable que le comportement linéaire.
Si c'est un problème, heapsort n'est pas plus adapté. Si les données sont au départ dans un tableau, je ne vois pas d'algorithme en place avec un comportement N log N ou bien est-ce que je suis distrait?2- il n'est pas stable ( => si des éléments sont identiques au regard du test de comparaison ils peuvent tout de même être échangés ce qui peut poser dans certains cas des problèmes)
Non le tri pas tas n'est pas stable non plu de ce point de vue. Par contre le 1er algorithme très simpliste que j'avais donné au début de cette discussion en réponse "méthode à une boucle" peu l'être si on trie avec "strictement inférieur" ou "strictement supérieur".
J’ai trouvé que le site
http://fr.wikipedia.org/wiki/Tri
avait pas mal d’informations
Je crois que ce tri s'appelle le "pigeon-hole sort". Ca n'est applicable que sur les domaines finis, et avec peu de valeurs possibles.Envoyé par ToTo13
***
Une fois, j'avais le problème suivant (c'était lors de mon stage de licence):
- on devait trier les informations contenues dans plusieurs gros fichiers
- en mémoire, on avait des objets qui indiquaient la position des données dans le fichier
- quand on avait besoin d'accéder aux données, on les rechargeait à partir du fichier
Donc quand on accédait aux données, ça mettait du temps vu qu'il fallait chercher l'info dans le fichier. En tant que stagiaire, je devais améliorer les performances de ce programme. Voilà ce que j'ai fait:
- je me suis fait un "cache" pour ne pas recharger systématiquement les données à partir du fichier
Par conséquent, si on accède plusieurs fois de suite aux mêmes données, on économise les temps de chargement et donc ça va plus vite. Il vaut mieux dans ce cas que l'algo effectue sur des données consécutives (éviter les aller-retour dans le fichier).
Voilà ce que ça donnait avec différents algos:
- tri par insertion (la méthode utilisée par l'ancien programme): performances misérables
- quick sort: bonne performances, mais pas si rapide que ça
- heap sort: très mauvaises performances (beaucoup trop d'aller-retour!)
- merge sort: les meilleures perfs. En plus, le tri est stable.
Si j'avais pu, j'aurais complètement repensé l'application en utilisant des flux pour le traitement plutôt que de mettre les données en mémoire pour les traiter après (parce que c'est franchement débile comme manière de faire...). Idem pour les tris: j'aurais fait un merge sort utilisant des fichiers temporaires. J'était même étonné qu'ils n'aient pas pensé à utiliser un SGBD pour faire ce genre de manip' (après tout, ils sont faits pour ça: traiter une grande quantié de données, et ils le font de manière optimale). Enfin bref, l'appli était mal pensée à la base mais j'ai dû faire avec. De toute façon, c'était une boite de m**** aussi...
Néanmoins, ce que je retire de cette "expérience", c'est que le "merge sort" a d'excellentes propriétés (bonne perfs, stable...) et qu'il permet une utilisation optimale du "cache" (utile quand les données ne sont pas toujours physiquement en mémoire mais qu'on doit les rechercher ailleurs: dans un fichier par exemple).
"On en a vu poser les armes avant de se tirer une balle dans le pied..."
-- pydévelop
Derniers articles:
(SQL Server) Introduction à la gestion des droits
(UML) Souplesse et modularité grâce aux Design Patterns
(UML) Le Pattern Etat
Autres articles...
Partager