C++

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

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [C++] [résolu] Besoin d'un coup de main pour déboguer mon algo de tri

Fused

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 :

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

Sachant que la fonction échanger est :

Code :

void echanger (int t[], int i, int j)
{
int temp = t[i];
t[i] = t[j];
t[j] = temp;
nbAffectations = nbAffectations + 3;
}

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

Publicité

tpierron

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.

Hangleton

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

Fused

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 :

int main (int argc, char** argv)
{
int n = 100000; // Nombre d'éléments à trier au départ
int t_rapide[n]; // Tableau pour le tri rapide
int t_tas[n+1]; // Tableau pour le tri par tas
int t_trie[n]; // Tableau trié du sauvegarde
for (int z=1; z<=4; z++)
// Cette boucle permet de varier les 4 types de tableau d'entrée
// 1. Tableau aléatoire
// 2. Tableau trié
// 3. Tableau partiellement trié
// 4. Tableau quasiment trié
{
switch (z)
{
case 1 :
// Tableaux aléatoires
...
case 2 :
// Tableaux triés
copie_tableau(t_rapide, t_tas, 1, n+1);
// je copie le tableau en double exemplaire pour le trier en tri rapide puis en tri par tas
break;
case 3 :
// Tableaux partiellement triés
...
case 4 :
// Tableaux quasiment triés
...
default :
break;
}
for (int t=0; t<2; t++)
{
temps_initial = clock ();
if (t==0) tri_rapide(t_rapide,0,n-1); // ici cela met 58 secondes à n=100 000 et z = 2
else tri_tas(t_tas,1,n);
temps_final = clock ();
temps_cpu = (temps_final - temps_initial) * 1e-6;
}
}
}

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 :

int partition(int T[],int p,int s)
{
int x = T[s];
int i = p-1;
for(int j = p ; j < s; j++)
{
if(T[j]<= x)
{
i++;
int temp = T[i];
T[i] = T[j];
T[j] = temp;
}
}
int temp = T[i+1] ;
T[i+1] = T[s] ;
T[s] = temp;
return i+1;
}
void tri_rapide(int tab[],int p,int n)
{
if(p < n)
{
int q = partition(tab,p,n);
tri_rapide(tab,p,q-1);
tri_rapide(tab,q+1,n);
}
}

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

Fused

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 !!!).

Fused

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 :

void tab_aleatoire(int t[], int n)
{
srand(time(NULL));
for (int j=0; j<n; j++)
{
t[j]=rand()%n;
}
}
int main (int argc, char** argv)
{
int n = 1500000;
while (n<10000000)
{
int t[n];
tab_aleatoire(t,n);
n = n + 100000;
cout << n << endl;
}
}

Code :

1500000
1600000
1700000
1800000
1900000
2000000
2100000
Program received signal SIGSEGV, Segmentation fault.
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

Joel F

Real men use unique_ptr

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

Fused

J'avais pas pensé à ça !

En gros je remplace tout les int [] par :
int *t2;
t2 = new int [n];
?

Fused

Bon tu avais raison !

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

FORUM HardWare.fr

Programmation

C++

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

Sujets relatifs
Planning assisté excel; besoin de formules VB pour deux problématiques	[Résolu] Site internet en japonais
[resolu]Boucles sur des requetes MySQL	[résolu] Automatiser une fonction excel sur vba
[PHP](AJAX) - Pb Caractères spéciaux (apostrophe) ..euh RESOLU en fait	[C++] [resolu] Problème de templates
Petit problème avec mon algo de tri !	besoin d'un gérant de forum de team Python
Exécution commande, pas de retour [Résolu]	Résolu [Excel] colori selon critère
Plus de sujets relatifs à : [C++] [résolu] Besoin d'un coup de main pour déboguer mon algo de tri

Page générée en 0.089 secondes