Discussion :

[lkryss]

bonjour.
j'ai une liste composé d'elements ayant tous la forme suivante : YYY/XX
avec YYY un nombre compris entre 000 et 999
et XX represente les 2 derniers chiffres d'une année.

je recupere donc une liste venant d'une base de données, mais elle arrive brute et non rangée. Ayant besoin de l'afficher j'ai donc fait un algo recursif de tri qui doit dabord trier en fonction de XX puis en fonction de YYY.
je sais que mon algo marche mais sur des petites listes, en effet quand je prend plus d'une centaine de ces elements j'ai un probleme d'overflow. Ne sachant pas d'ou il provient je prefere etre sur que mon algo est correct.

soit YYY/XX un element et YYY+/XX+ deux elements bruts de ma liste non triée.
je recupere dabord XX dans une variable, ainsi que YYY, YYY+ et XX+
1er test : je regarde si XX est plus grand que XX+ ET si YYY est plus grand que YYY+
si cest le cas je fais une inversion entre les deux, puis je relance le tri depuis le debut
2eme test : je regarde si XX plus grand que XX+ ET si YYY est plus petit que YYY+, si cest le cas j'inverse aussi, et je relance le tri du debut
3eme test : je regarde si XX est egale à XX+ ET si YYY est plus grand que YYY+, jinverse aussi si cest le cas et je relance le tri du debut.
Si le tri n'est psa relancé c'est donc qu'aucun test n'est lancé et qu'il n'y a donc pas besoin d'inversion entre les 2 elements, je relance donc le tri avec les 2 elements suivants (YYY+/XX+ et YYY++/XX++).
je le code en java, et j'ai donc un probleme d'overflow, pour diminuer le probleme, lors des 3 tests au lieu de repartir au debut je relance le tri avec l'element precedent a YYY/XX. ca s'ameliore un peu, mais j'ai toujours le probleme. est ce que cela vient de l'algo?

[millie]

Tu travailles en quel langage ?

Si le langage passe les arguments des fonctions sur une pile, vu que ton algo est récursif, il peut vite y avoir un dépassement de la capacité de la pile, donc plantage.

[edit] Je viens de voir que c'est en Java, je crois (je suis pas sûr) qu'il passe les arguments sur la pile comme en C, donc ce n'est pas conseillé de faire un algorithme récursif où le nombre d'appel sera très important.

[Nemerle]

soit YYY/XX un element et YYY+/XX+ deux elements bruts de ma liste non triée.
je recupere dabord XX dans une variable, ainsi que YYY, YYY+ et XX+
1er test : je regarde si XX est plus grand que XX+ ET si YYY est plus grand que YYY+
si cest le cas je fais une inversion entre les deux, puis je relance le tri depuis le debut
2eme test : je regarde si XX plus grand que XX+ ET si YYY est plus petit que YYY+, si cest le cas j'inverse aussi, et je relance le tri du debut
3eme test : je regarde si XX est egale à XX+ ET si YYY est plus grand que YYY+, jinverse aussi si cest le cas et je relance le tri du debut.
Si le tri n'est psa relancé c'est donc qu'aucun test n'est lancé et qu'il n'y a donc pas besoin d'inversion entre les 2 elements, je relance donc le tri avec les 2 elements suivants (YYY+/XX+ et YYY++/XX++).
?

Test 2 inutile test1&2 se résume à si XX > XX+

à mon avis, ne vient pas de l'algo, mais d'un problème du langage (pile?)

[lkryss]

daccord, merci pour vos reponses, parce que quand j'ai fait mon algo, il marchait bien, la seul difference qu'il ya eu cest le nombre de chaine à traiter.

et simplement comment je pourrais faire le meme tri sans passer par du recursif?

[j.p.mignot]

Il y a eu déjà pas mal de discussions sur les tris: voir par exemple
http://www.developpez.net/forums/sho...d.php?t=115057
Le problème est sûrement lié à la pile.
Ici, il pourrait être avantageux de faire un tri comme ceci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
for i:=0 to 99 do 
   begin
   make_sub_liste;  // extraction des éléments dont l'année est i, ils sont au nombre de n n = 0..999
   if ( n=1) -> ajouter l'élément à la liste triée
   else if n > 1 -> trier la sous-liste puis ajouter les n éléments à la lite triée
   end;

ainsi la routine de tri travaillera sur des groupes de données plus petits donc sera moins sujette à des problèmes de pile.
Toutefois dans le lien proposé, on trouve bien des méthodes de tris non récursives.

[Sivrît]

Si ce n'est pas un exercice et que le but est le résultat, pourquoi ne pas définir un Comparator et utiliser la méthode sort de Collection, puisque c'est du Java ? C'est efficace et fiable (mais moins drole !)

Certains langages (Caml par exemple) sont capables d'éviter ce genre de problème si on prend soin de recourrir à une récurrence terminale. Quelqu'un sait si c'est le cas de Java ?
Edit : testé et manifestement non. Ma JVM me fait une StackOverflowError entre 12000 et 13000 appels récursifs avec "int fonction(int)" et vers 17000 avec "void fonction()". Donc java c'est bof pour le récursif à grande échelle

Enfin, avec un algo en "et je relance le tri du debut", ça devrait pouvoir facilement se faire avec un "while" ou un "for".

[lkryss]

ok je prend note, pas de recursif en java avec beaucoup de données

je vais regarder la classe comparator et également en decomposant ma liste en plusieurs morceaux (c'est en théorie la derniere chose qu'il me reste a faire pour mon stage, ce n'est pas bien important et j'ai du temps)

merci a vous !