[C++] Pourquoi ça sature la pile?

Pourquoi ça sature la pile? [C++] - C++ - Programmation

Marsh Posté le 27-03-2003 à 22:47:30    

Alors voilà, j'ai une pointeur pointant sur une liste de unsigned int, j'utilise ce pointeur dans une fonction qui fait un QuickSort sur la liste asignée au pointeur.
 
Bon, je lance la fonction tout ce passe bien, tout est trié. Je relance la fonction et là il y a une surchage de la pile!
 
Pourtant, si avant de lancer la fonction de trie je détruis la liste associée au pointeur et en réassigne une nouvelle je peux lancer la fonction un nombre de fois illimité. Bien sûr ça marche mais je ne trouve pas ça élégant...
 
Je ne comprend pas pourquoi il y a une saturation si je ne détruis pas à chaque fois ma liste sachant que je fais seulement quelques swaps (enfin un QuickSOrt quoi :D) qui ne surchage pas la pile lors d'une première itération, alors pourquoi lors d'un second passage il y a une surchage?
 
Pouvez-vous m'aider à comprendre? Merci.

Reply

Marsh Posté le 27-03-2003 à 22:47:30   

Reply

Marsh Posté le 27-03-2003 à 22:52:06    

Ca depend de comment tu as codé ton QuickSort. Il est très facile de tomber sur la version dans lequel le pire des cas correspond à une liste déjà triée. Autrement dis, quand tu tries 2 fois d'affilé, la deuxième fois ton QuickSort se tape une complexité de O(n²) avec plus d'it"ration et donc plus d'appel récursifs successifs.

Reply

Marsh Posté le 27-03-2003 à 22:54:58    

Ah ça doit être ça sachant que quand je détruis pas ma liste, je ne la modifie pas donc elle est déjà triée.
 
PS: je me dite pas que c'est con de trier une liste qu'on sait triée, c'est seulement des tests pour le moment :D

Reply

Marsh Posté le 27-03-2003 à 23:04:27    

la question c'est pourquoi TON implementation de quicksort
sature la pile sur une liste deja triee..
 
Et franchement on ne peut pas vraiment repondre sans voir ton implementation..
 
LeGreg


---------------
voxel terrain render engine | animation mentor
Reply

Marsh Posté le 28-03-2003 à 16:35:25    

Alors voilà ma fonction qui fait le QuickSort, c'est pas moi qui l'ai écris, je l'ai pompé sur le net et je l'ai modifié pour qu'elle puisse trier la hauteur de plusieurs colonnes que j'utilise dans mon programme. Le but est de mettre dans la liste pColumnsOrder l'ordre des colonnes de la plus petite à la plus grande:
 

Code :
  1. void QuickSort(unsigned int left, unsigned int right)
  2. {
  3. float pivot = pColumns[pColumnsOrder[left]].fHeight;
  4. unsigned int indexpivotdata = pColumnsOrder[left];
  5. unsigned int indexpivot = left;
  6. unsigned int l_hold = left;
  7. unsigned int r_hold = right;
  8. while (left < right)
  9. {
  10.  while ((pColumns[pColumnsOrder[right]].fHeight >= pivot) && (left < right))
  11.   right--;
  12.  if (left != right)
  13.  {
  14.   pColumnsOrder[left] = pColumnsOrder[right];
  15.   left++;
  16.  }
  17.  while ((pColumns[pColumnsOrder[left]].fHeight <= pivot) && (left < right))
  18.   left++;
  19.  if (left != right)
  20.  {
  21.   pColumnsOrder[right] = pColumnsOrder[left];
  22.   right--;
  23.  }
  24. }
  25. pColumnsOrder[left] = indexpivotdata;
  26. indexpivot = left;
  27. if (l_hold < indexpivot)
  28.  QuickSort(l_hold, indexpivot - 1);
  29. if (r_hold > indexpivot)
  30.  QuickSort(indexpivot + 1, r_hold);
  31. }

Reply

Marsh Posté le 28-03-2003 à 17:41:47    

tu pourrais preciser tes types de données, on sait jamais, juste comme ça
 
le mieux: tu mais des cout partout ou tu prends ton debuggeur et tu vas voire que ta recursion est infinie ou alors trop grande pour ton systeme (limitation de la  taille de la pile)

Reply

Marsh Posté le 28-03-2003 à 18:23:13    

Taz> Remplace "mais" par "mets", parce que là, le plafond a failli être repeint de mon sang tellement j'ai bondi... :sarcastic:
 
edit> Et vire ce 'e' à 'voire' que je ne saurais voir !


Message édité par BifaceMcLeOD le 28-03-2003 à 18:23:48
Reply

Marsh Posté le 28-03-2003 à 18:42:05    

Comme tu choisis pour pivot le premier element de la liste, c'est justement que le pire des cas pour le QuickSort avec une liste triee.
 
Pour information, dans cette situation tu vas probablement faire dans les n(n-1)/2 appels recursifs. Pas ettonant que ca finisse par peter

Reply

Marsh Posté le 28-03-2003 à 18:42:18    

pColumns[i].fHeight sont des floats.
pColumnsOrder[i] sont des unsigned int.

Reply

Marsh Posté le 29-03-2003 à 10:34:01    

Alload a écrit :

(enfin un QuickSOrt quoi :D)


Moi je parie que tu es étudiant, car sinon tu utiliserais "std::sort" :-)

Reply

Marsh Posté le 29-03-2003 à 10:34:01   

Reply

Marsh Posté le 29-03-2003 à 10:42:18    

kenshiro182 a écrit :


Moi je parie que tu es étudiant, car sinon tu utiliserais "std::sort" :-)

Oui et non :D Suis pas en filière info, en fait j'utilise ce tri dans un programme fait pour un TIPE (exposé) et j'avais besoin d'un tri très rapide. J'ai pensé au std::sort, mais première je ne sais pas si il est plus rapide que QuickSort et deuxièmement il faut que tri des structures alors je ne savais pas comment utiliser la fonction.

Reply

Marsh Posté le 29-03-2003 à 10:51:25    

c'est bien ce qu'on pensait. utilise le std::sort, il est plus rapide, fonctionnel et adaptable

Reply

Marsh Posté le 29-03-2003 à 12:15:58    

Alload a écrit :

Oui et non :D Suis pas en filière info, en fait j'utilise ce tri dans un programme fait pour un TIPE (exposé) et j'avais besoin d'un tri très rapide. J'ai pensé au std::sort, mais première je ne sais pas si il est plus rapide que QuickSort et deuxièmement il faut que tri des structures alors je ne savais pas comment utiliser la fonction.


"std::sort" a une complexité en n*log(n) (c'est à dire que le nombre d'opérations nécessaires pour n élément est de l'ordre de n*log(n), sauf cas rares). std::sort peut être implémenté par un algo "quick sort".
"std::sort" est plus rapide car contrairement à "quicksort", la fonction de comparaison peut etre "inlinée".

Reply

Marsh Posté le 29-03-2003 à 13:13:28    

Alload a écrit :

c'est pas moi qui l'ai écris

si ce n'est pas pour un tp, utilise qsort. http://msdn.microsoft.com/library/ [...] _qsort.asp

Reply

Marsh Posté le 29-03-2003 à 13:14:50    

Alload a écrit :

j'avais besoin d'un tri très rapide.

le plus rapide (en n) est le bytesort, aussi appellé radix. fais une recherche, ça a déjà été abordé plusieurs fois ici.

Reply

Marsh Posté le 29-03-2003 à 13:45:04    

youdontcare a écrit :

le plus rapide (en n) est le bytesort, aussi appellé radix. fais une recherche, ça a déjà été abordé plusieurs fois ici.

hey, on parle de tri généralisé ici, obéissant à un critère de haut niveau tel que less, tu peux essayer ton bytesort autant de fois que tu veux, tu n'arriveras jamais à rien. => std::sort

Reply

Marsh Posté le 30-03-2003 à 00:23:07    

++Taz a écrit :

hey, on parle de tri généralisé ici, obéissant à un critère de haut niveau tel que less, tu peux essayer ton bytesort autant de fois que tu veux, tu n'arriveras jamais à rien. => std::sort


 
je ne vois pas en quoi il est de plus haut niveau
ce n'est jamais qu'une comparaison de flottants..
 
Certes en utilisant, le std::sort tu as un algo générique
que tu peux réutiliser librement.. C'est d'ailleurs l'objectif de la STL, pas forcément compatible avec la meilleure performance dans le cas général.
 
LeGreg


---------------
voxel terrain render engine | animation mentor
Reply

Marsh Posté le 30-03-2003 à 00:32:52    

fo pas pousser non plus

Reply

Marsh Posté le 30-03-2003 à 01:25:31    

std::sort std::sort  ...
 
ok std::jsuisdehors
 
 
 
 
 
 
 
 
...  
[:dehors2]


---------------
last.fm
Reply

Marsh Posté le 30-03-2003 à 01:50:46    

Au fait ... J'vois pas vraiment comment on peut faire un byte sort sur des flottants ... (si je ne me trompe pas, même en les comparant méchamment bit à bit, ca colle pas car l'exposant dans les nombres floattants est sur les bits de poids le plus faible)
 
Edit : une faute d'orthographe ... :D


Message édité par theshockwave le 30-03-2003 à 01:51:31

---------------
last.fm
Reply

Marsh Posté le 30-03-2003 à 01:57:04    

theShOcKwAvE a écrit :

Au fait ... J'vois pas vraiment comment on peut faire un byte sort sur des flottants ... (si je ne me trompe pas, même en les comparant méchamment bit à bit, ca colle pas car l'exposant dans les nombres floattants est sur les bits de poids le plus faible)


 
http://www.stereopsis.com/radix.html
 
LeGreg


---------------
voxel terrain render engine | animation mentor
Reply

Marsh Posté le 30-03-2003 à 03:17:50    


 
 
merci ! :jap:


---------------
last.fm
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed