Erreur de Segmentation dûe au trop grand nombre d'éléments

spykII · Le 23/04/2008, à 12:40

Bonjour à toutes et tous, je viens vers vous car j'ai un petit problème de compilation comme l'indique le titre.
Je vous présente la chose. A la fac nous avons un projet sur les algorithmes de tri à réaliser. Les principaux algo sont écrits, seulement notre tuteur souhaiterait que nous testions ces derniers sur un très grand nombres d'éléments, même si cela devait durer toute une nuit.
L'algorithme en question se nomme QuickSort ou encore algorithme de tri rapide. ( petite description et implémentation ici http://www.prog-info.org/cpp/trietreche … rapide.php).
Cet Algorithme fonctionne très bien, seulement pour un tri d'un tableau rempli d'éléments choisis aléatoirement, d'une taille de 10 000 000 ( je sais c'est beaucoup mais vu sa rapidité il faut bien ça ), une erreur de segmentation apparait.

J'en arrive donc au but de ce post : auriez-vous une méthode pour que le tri se poursuive même si cela doit prendre beaucoup de temps?

Je tourne sous Gutsy Gibbon 7.10 sur un ordinateur portable, mais s'il y a besoin d'une plus grande puissance de calcul pas de problème.

Voilà j'espère avoir été assez clair et n'avoir rien oublié, sauf si peut-être vous souhaitez voir l'algorithme, à ce moment là vous n'avez qu'à demander.

Merci par avance

++

obiwankennedy · Le 23/04/2008, à 12:48

en général, si le tri provoque une segmentation fault c'est que ton algo est mal écrit.
Donc tu peux peut etre voir à le débugger. après si c'est effectivement l'allocation des 10 000 000 éléments qui fait planté il suffit de vérifier tes données apres l'allocation mémoire.

Ultandir · Le 23/04/2008, à 12:54

Bonjour,

Peut tu mettre ton algorithme sur le forum, que l'on puisse l'analyser?

Le Farfadet Spatial · Le 23/04/2008, à 12:55

Salut à tous !

Normalement, avec le tri rapide, tu peux effectuer le tri en place, donc il n'y a pas de raison de provoquer une erreur de segmentation. Peux-tu donner ton code, pour voir où se situe le problème ?

À bientôt.

Le Farfadet Spatial

iuchiban · Le 23/04/2008, à 12:56

Ça doit être un indice déclaré en short int et qui gère pas la valeur 10 000 000,

Mais effectivement, avec le langage utilisé et le code qui va bien, on pourra mieux te renseigner.

spykII · Le 23/04/2008, à 12:58

Merci de répondre aussi vite d'abord
Pour la mauvaise écriture je n'espère pas car, c'est seulement pour ce nombre d'éléments. De 2 éléments à 2 000 000 il n'y aucun souci. A partir de 4 000 000 Erreur de segmentation (core dumped). S'il devait y avoir une mauvaise écriture cela se serait vu bien plus tôt non?
N'y a-t-il pas une sorte de sécurité visant à empêcher l'ordinateur de faire des calculs pendant trop longtemps dans le terminal?
En ce qui concerne votre allocation mémoire je n'ai pas trop compris.

Merci en tout cas

spykII · Le 23/04/2008, à 13:01

Oula désolé je post trop lentement j'avais pas vu toutes vos réponses
Voilà je vais vous mettre ça tout de suite.

#include <iostream>
#include <time.h>

using namespace std;


//Fonction executant les recherches, les déplacements et permettant le tri.

int place(int t[], int deb, int fin)
{
int pivot,vide,ancienne,aux;
pivot=t[deb];
vide=deb;ancienne=fin;

while(vide != ancienne)
	{ while ( t[ancienne] > pivot and ancienne != vide)
		{ ancienne = ancienne -1;
		}
	 if (ancienne != vide)
		{ t[vide] = t[ancienne];
		  aux=vide; vide=ancienne; ancienne= aux+1; 
		}
	while( t[ancienne]< pivot and ancienne != vide)
		{ancienne = ancienne++;
		}
	if(ancienne != vide)
		{ t[vide]=t[ancienne];
		  aux=vide; vide=ancienne; ancienne=aux -1;
		}
	}
t[vide]=pivot; 
return vide;
}


//Simple fonction d'échange de deux valeurs " a " et " b " d'un tableau " t[] ".

void ech(int a, int b,int t[])
{
int c;
c=t[a] ;
t[a]=t[b];
t[b]=c;
}


//Fonction de tri rapide récursive sur tous les éléments du tableau, faisant appel à la méthode place.

void trirapide(int t[], int deb, int fin)
{
int p;

if(deb<fin)
	{if( fin == deb + 1)
		{ if(t[fin]<t[deb])
	    {ech(deb,fin,t);
	    }
	}
      else 
	{ p=place(t,deb,fin);
	  trirapide(t,deb,p-1);
	  trirapide(t,p+1,fin);
	}
    }
}


//Fonction d'affichage du tableau passé en paramètre.

void affiche(int t[],int n)
{
for(int i=0;i<n;i++)
	{ cout<<t[i]<<" | ";
    	}
}


//Fonction de remplissage du tableau passé en paramètre, par des éléments aléatoires compris entre 2 et la taille du tableau.

void saisierand(int t[], int n)
{ srand( time( NULL ) );
     for(int i=0; i<n; i++)
	 { t[i] = 0 + int( double( rand() ) / ( double( RAND_MAX) + 1 ) * n ); }
}


//prend cputime en donn�e

void cputime_reset(clock_t time1) 
        {time1 = clock();}


//prend cputime en donn�e

double cputime_get(clock_t time2)
        { return (double)(clock()-time2)/(CLOCKS_PER_SEC);}


//Fonction main, faisant appel à toutes les méthodes précédement déclarées en executant le programme principal.

int main()
{ int n,deb,fin;


cout<<"donnez la taille de votre tableau"<<endl;
cin>>n;
int t[n];

cout<<endl;

//cout<<"Votre tableau va être remplie à l'aide de valeurs générées aléatoirement."<<endl;
saisierand(t,n);

deb=0;
fin=n;

cout<<endl;

cout<<"affichage de votre tableau : "<<endl;
 affiche(t,n);
 cout<<endl<<endl;

cout<<"tri de votre tableau... "<<endl<<endl;

static clock_t cputime;
cputime_reset(cputime);


trirapide(t,0,n);

cout<<cputime_get(cputime)<<endl<<endl;

//  cout<<"affichage de votre tableau trie : "<<endl;
//  affiche(t,n);
//  cout<<endl<<endl;
// cout<<cputime_get(cputime)<<endl<<endl;
}

spykII · Le 23/04/2008, à 13:04

Je ne sais pas si c'est le meilleur moyen pour vous montrer l'algo..Vous trouverez peut-être l'algo mal écrit, j'ai fait de mon mieux et je ne suis pas encore expert à la matière..

Merci en tout cas de votre rapidité ^^

spykII · Le 23/04/2008, à 13:05

Pardon c'est du C++ j'ai oublié de le signaler, même si vous avez du le constater en lisant le code..

iuchiban · Le 23/04/2008, à 13:08

Effectivement, vu que tu utilises du récursif (très puissant ), tu dépasses peut etre le nombre de threads possibles vu que ton algo consiste a couper en deux le tableau et a trier chaque partie.

Avec 2 éléments, il te faut 3 threads
avec 4 éléments -> 7
avec 8 -> 15
avec n éléments -> 2n-1
avec 10000000 -> 19999999 threads.

je sais pas si Ubuntu gère le ulimit (je pense que si) et c'est peut etre dee ce cote qu'il faut chercher.

Dernière modification par iuchiban (Le 23/04/2008, à 13:09)

spykII · Le 23/04/2008, à 13:10

Ouep merci de ta réponse, j'ai tenté sur google, et sur google/linux de trouver un moyen de laisser tourner, mais je vais creuser ton idée du "ulimit".

Merci bien

spykII · Le 23/04/2008, à 14:15

Bon après pas mal de temps passé sur google, je n'ai pas trouvé de solution pour utiliser la commande nice ou ulimit.. le nice sert à attribuer l'importance d'un processus et d'en modifier la valeur. Je n'ai pas trouver avec le man comment l'utiliser, et quant au ulimit c'est vague.

Auriez-vous des idées ?

Bonne aprem.

Le Farfadet Spatial · Le 23/04/2008, à 14:40

Salut à tous !

spykII, ton code est bien. Un habitué du C++ fera quelques changements, mais globalement c'est plutôt bien foutu. Simplement, je te conseille d'enlever tes conversions à la C et d'utiliser l'opérateur static_cast. Par exemple, pour convertir i en double et stocker le tout dans x :

x = static_cast<double>(i)

Cela dit, ton problème ne vient pas de là.

iuchiban a écrit :

vu que tu utilises du récursif (très puissant )

Que oui ! Il ne faut jamais négliger la récursivité.

iuchiban a écrit :

tu dépasses peut etre le nombre de threads

?
??
???

Depuis quand le C++ lance un nouveau thread par appel de fonction ? Je n'ai vu ça dans aucun des rapports techniques...

Non, simplement, à chaque appel de fonction, ses paramètres sont stockés dans la pile (empilés), qui est, pour simplifier, une page de mémoire un peu particulière reservée à ton programme. Pile qui, de toute façon, a une taille limitée --- un ordinateur est une machine finie. Donc, arrivé à un moment, la pile est pleine et ne peut plus rien contenir. Pour être plus précis, lorsque la pile est pleine et que l'on essaye d'empiler une nouvelle valeur, alors on cherche à la stocker dans une adresse à laquelle notre programme n'a pas accès (dans un segment de la mémoire qui ne nous est pas autorisé). Le système d'exploitation détecte ce manque totale de courtoisie et met immédiatement le fautif à l'amende en arrêtant le processus et en déclarant une erreur de segmentation.

Donc, ton problème, spykil, c'est que tu utilises un jeu de données trop grand pour ta pile (c'est ce qu'on appelle avoir les yeux plus gros que le ventre). Que peux-tu faire pour remédier à ce problème ?

Première solution : ne pas utiliser un jeu de données trop gros. 2 000 000, c'est déjà bien ! Pour faire du profilage de ton code, tu peux le lancer plusieurs fois de suite (disons 20 fois) et voir ce que cela donne.

Deuxième solution : dérécurser ton algorithme. À partir de là, tu pourras bricoler avec les pages de mémoires. Le problème, c'est que c'est un peu compliqué et c'est dommage de dérécurser un algorithme, je trouve (c'est mon côté esthète qui ressort).

Troisième solution : t'introduire de nuit dans le centre de calcul le plus proche de chez toi pour utiliser une machine de calcul qui propose une pile de dingue. Le Earth Simulator au CEA est plutôt pas mal ! Le problème, c'est que cette solution n'est pas très légale...

À bientôt.

Le Farfadet Spatial

iuchiban · Le 23/04/2008, à 15:26

Non, simplement, à chaque appel de fonction, ses paramètres sont stockés dans la pile (empilés)

Ca remonte a trop longtemps mes cours de C++

C'est vrai que c'est en JAVA que je faisais du multi threading

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 23/04/2008, à 12:40

Erreur de Segmentation dûe au trop grand nombre d'éléments

#2 Le 23/04/2008, à 12:48

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#3 Le 23/04/2008, à 12:54

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#4 Le 23/04/2008, à 12:55

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#5 Le 23/04/2008, à 12:56

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#6 Le 23/04/2008, à 12:58

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#7 Le 23/04/2008, à 13:01

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#8 Le 23/04/2008, à 13:04

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#9 Le 23/04/2008, à 13:05

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#10 Le 23/04/2008, à 13:08

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#11 Le 23/04/2008, à 13:10

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#12 Le 23/04/2008, à 14:15

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#13 Le 23/04/2008, à 14:40

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

#14 Le 23/04/2008, à 15:26

Re : Erreur de Segmentation dûe au trop grand nombre d'éléments

Pied de page des forums