[C++] [résolu] Besoin d'un coup de main pour déboguer mon algo de tri

Besoin d'un coup de main pour déboguer mon algo de tri [C++] [résolu] - C++ - Programmation

Marsh Posté le 15-12-2007 à 16:52:53    

Hello !
 
Je test des algo de tris pour calculer le temps d'execution selon le nombre de données.
 
A partir de 130 000 éléments dans mon tableau ça plante, (je vais de 10 000 en 10 000, ça plante donc entre 120 000 et 130 000).
 
Je sais très peut utiliser gdb mais en mettant un break point, j'obtiens ça à l'execution :
 

Code :
  1. Program received signal SIGSEGV, Segmentation fault.
  2. 0x0000000000400fb0 in echanger (t=Cannot access memory at address 0x7fffcde9efe8
  3. ) at projet.cc:232
  4. 232     void echanger (int t[], int i, int j)


Sachant que la fonction échanger est :
 

Code :
  1. void echanger (int t[], int i, int j)
  2. {
  3. int temp = t[i];
  4. t[i] = t[j];
  5. t[j] = temp;
  6. nbAffectations = nbAffectations + 3;
  7. }


Voilà, je n'ai absolument aucune idée de ce que je peux faire d'autre, je ne balance pas tout le code, il y a plus de 400 lignes, si vous pouvez m'orienter ou m'aider, c'est avec grand plaisir !!!


Message édité par Fused le 16-12-2007 à 16:50:44
Reply

Marsh Posté le 15-12-2007 à 16:52:53   

Reply

Marsh Posté le 15-12-2007 à 19:29:21    

Mouais, de toute évidence ta fonction "echanger" n'est que la partie visible de l'iceberg et ce qui a provoqué l'erreur se situe bien en-dessous de ta pile d'appel des fonctions.
 
Poste plus de code.

Reply

Marsh Posté le 15-12-2007 à 21:14:41    

Ta fonction echanger semble correcte.
 

0x0000000000400fb0 in echanger (t=Cannot access memory at address 0x7fffcde9efe8
) at projet.cc:232


=> Apparemment, tu demandes un accès hors des limites de ton tableau t.
Donc :  
 
- vérifie la mémoire que tu alloues (N) pour ce tableau;
- vérifie que tes index i et j ne dépassent l'indice N-1 du dernier élément du tableau.
 
N'hésite pas à envoyer d'autres bouts de code si nécessaire.


Message édité par Hangleton le 15-12-2007 à 21:18:07
Reply

Marsh Posté le 16-12-2007 à 01:01:13    

Merci de vos messages, j'ai réussi à trouver ou celà bloque, en fait je test plusieurs tri différents, cela bloque sur le tri rapide quand je lui balance un tableau déjà trié, le temps est de l'ordre de 60 secondes pour 100 000 éléments, contre environ 0.6 secondes pour le même tableau non trié !
 
Je dois avoir une erreur forcément ! mais je ne trouve pas du tout !
 
Je vous donne un extrait du code, ce qui sert là ou ça plante :

Code :
  1. int main (int argc, char** argv)
  2. {
  3. int n = 100000;   // Nombre d'éléments à trier au départ
  5.  int t_rapide[n];  // Tableau pour le tri rapide
  6.  int t_tas[n+1];   // Tableau pour le tri par tas
  7.  int t_trie[n];   // Tableau trié du sauvegarde
  9.   for (int z=1; z<=4; z++)
  10.   // Cette boucle permet de varier les 4 types de tableau d'entrée
  11.   // 1. Tableau aléatoire
  12.   // 2. Tableau trié
  13.   // 3. Tableau partiellement trié
  14.   // 4. Tableau quasiment trié
  15.   {
  16.    switch (z)
  17.    {
  18.     case 1 :
  19.      // Tableaux aléatoires
  20.      ...
  21.     case 2 :
  22.      // Tableaux triés
  23.      copie_tableau(t_rapide, t_tas, 1, n+1);
  24.             // je copie le tableau en double exemplaire pour le trier en tri rapide puis en tri par tas
  25.      break;
  26.     case 3 :
  27.      // Tableaux partiellement triés
  28.             ...
  29.     case 4 :
  30.      // Tableaux quasiment triés
  31.             ...
  32.     default :
  33.      break;
  34.    }
  36.    for (int t=0; t<2; t++)
  37.    {
  38.     temps_initial = clock ();
  39.     if (t==0) tri_rapide(t_rapide,0,n-1);             // ici cela met 58 secondes à n=100 000 et z = 2
  40.     else tri_tas(t_tas,1,n);
  41.     temps_final = clock ();
  42.     temps_cpu = (temps_final - temps_initial) * 1e-6;
  43.    }
  44. }
  45. }


Voilà, en k = 2, j'ai déjà le tableau t_rapide déjà trié du coup d'avant, je le retrie et cela est très long, même tandis que tous les autres tris fonctionnent rapidement.
 
edit : je rajoute l'algo de tri rapide :

Code :
  1. int partition(int T[],int p,int s)
  2. {
  3. int x = T[s];
  4. int i = p-1;
  5. for(int j = p ; j < s; j++)
  6. {
  7.  if(T[j]<= x)
  8.  {
  9.   i++;
  10.   int temp = T[i];
  11.   T[i] = T[j];
  12.   T[j] = temp;
  13.  }
  14. }
  15. int temp = T[i+1] ;
  16. T[i+1] = T[s] ;
  17. T[s] = temp;
  18. return i+1;
  19. }
  21. void tri_rapide(int tab[],int p,int n)
  22. {
  23. if(p < n)
  24. {
  25.  int q = partition(tab,p,n);
  26.  tri_rapide(tab,p,q-1);
  27.  tri_rapide(tab,q+1,n);
  28. }
  29. }


Quand j'interompt l'execution avec gdb lorsque qu'il bloque, je suis dans la boucle for entre les lignes 5 à 14 ici.
 
 
Je reste sur mon PC tant que j'ai pas trouvé, faut que je lance l'algo cette nuit pour faire des tests en boucle pour un rendu lundi, si vous avez la bonté de m'aider, c'est avec très grand plaisir !
 
Je peux donner plus de code si il faut, voir tout le source si besoin est.
 
Merci beaucoup d'avance !


Message édité par Fused le 16-12-2007 à 01:16:31
Reply

Marsh Posté le 16-12-2007 à 02:24:18    

En ignorant le tri rapide pour un tableau déjà trié, j'ai segmentation fault à partir de 700 000 éléments dans mon tableau...
 
Je comprends vraiment pas d'ou ça vient !
 
Si vous pouvez tester le programme sur votre machine et voir si ça fait pareil.
http://unlimitedriders.free.fr/test/projet2.cc
 
Supprimez la condition ligne 133 et 137 pour ne plus qu'avoir :
 
  if (t==0) tri_rapide(t_rapide,0,n-1);
  else tri_tas(t_tas,1,n);
 
Et essayez en mettant n = 10 000 comme premiere valeur.
 
J'en demande beaucoup et même trop je sais, mais si quelqu'un peut m'aider il me sauverai la vie (ou presque !!!).

Reply

Marsh Posté le 16-12-2007 à 12:09:12    

Je m'en suis toujours pas sorti !
 
En écrivant ce seulement ça, que je me sers dans mon programme pour générer des tableaux aléatoires :
 

Code :
  1. void tab_aleatoire(int t[], int n)
  2. {
  3. srand(time(NULL));
  4. for (int j=0; j<n; j++)
  5. {
  6.  t[j]=rand()%n;
  7. }
  8. }
  10. int main (int argc, char** argv)
  11. {
  12. int n = 1500000;
  14. while (n<10000000)
  15. {
  16.  int t[n];
  17.  tab_aleatoire(t,n);
  18.  n = n + 100000;
  19.  cout << n << endl;
  20. }
  21. }


Code :
  1. 1500000
  2. 1600000
  3. 1700000
  4. 1800000
  5. 1900000
  6. 2000000
  7. 2100000
  9. Program received signal SIGSEGV, Segmentation fault.
  10. 0x0000000000400ae0 in main ()


 
Ca plante comme dans mon programme, j'ai l'impressession.
 
Dans mon programme ça plante avant, mais c'est peut être parce que j'ai plusieurs tableaux, un exces de mémoire ou autre ?


Message édité par Fused le 16-12-2007 à 12:27:12
Reply

Marsh Posté le 16-12-2007 à 13:36:24    

deja si tu faisais des new et des delete au lieu de tes moche et pas standard int t[n], ca irait un peu mieux. 10$ que tu petes la pile d'appel avec tes 15000000 int dans un tableau statique.


Message édité par Joel F le 16-12-2007 à 13:37:06
Reply

Marsh Posté le 16-12-2007 à 16:20:17    

J'avais pas pensé à ça !
 
En gros je remplace tout les int [] par :
 int *t2;
 t2 = new int [n];
?

Reply

Marsh Posté le 16-12-2007 à 16:49:53    

Bon tu avais raison !
 
J'ai passé mon week end à chercher pour une connerie comme ça !

Reply

Sujets relatifs:

Leave a Replay

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