Je viens quérir votre aide pour ce problème auquel je ne vois actuellement pas de solution. J'ai créé un petit algorithme qui passe en revue toutes les possibilités d'une chaîne de caractère en fonction d'un alphabet. Ce n'est pas très clair, ce le sera plus avec le programme. C'est un bon exercice d'appel de fonction récurrente mais j'ai un problème. Tant que l'on donne une longueur de chaîne <= 4 tout va bien mais dès que c'est >= 5, la programme plante avec le message :
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Abandon (core dumped)
Ce qui me laisse sceptique étant donné que je n'utilise aucune allocation dynamique dans ce programme. La seule chose que j'utilise sont des vector mais je ne vois pas comment je peux en arriver à faire planter le programme.
Voici le code source :
#include <iostream>
#include <vector>
#include <string>
#include <time.h>
using namespace std;
int Start(int n,vector<string> &listeChaines);
int RecFonc(int n,vector<string> &listeChaines,vector<char> &tabChaines,vector<char> &alphabet);
int main(int argc,char *argv[])
{
int n = 0;
cout << "Entrez le nombre de caractères :"<<endl;
cin >> n;
vector<string> listeChaines;
double elapsedTime = 0;
clock_t stopTime;
clock_t startTime = clock();
Start(n,listeChaines);
stopTime = clock();
elapsedTime = (stopTime-startTime)/(CLOCKS_PER_SEC/(double)1000.0);
elapsedTime /= 1000;
cout << elapsedTime<<endl;
/*
for(int i = 0; i < listeChaines.size();i++)
{
cout << listeChaines[i]<<endl;
}*/
}
int Start(int n,vector<string> &listeChaines)
{
n+=1;
vector<char> alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char> tabChaines(n-1,alphabet[0]);
RecFonc(n-2,listeChaines,tabChaines,alphabet);
}
int RecFonc(int n,vector<string> &listeChaines,vector<char> &tabChaines,vector<char> &alphabet)//fonction de récurrence pour trouver les chaines
{
int longAlpha = alphabet.size();
for(int i = 0; i < longAlpha;i++)
{
tabChaines[n] = alphabet[i];
if(n > 0)
{
RecFonc(n-1,listeChaines,tabChaines,alphabet);
}
else
{
string chaine = "";
for(int j = 0; j < tabChaines.size();j++)
{
chaine += tabChaines[j];
}
listeChaines.push_back(chaine);
}
}
return 0;
}
Merci d'avance pour votre aide, je ne comprends pas d'où peut venir le problème (mis à part des vector mais là, je ne sais que faire)
C'est une erreur au runtime, il n'y a pas forcement plus de messages. (Par contre, il y a un core dump, et bacelar dirait qu'il faut savoir utiliser les core dump).
string et vector sont des classes RAII qui font des allocations dynamiques. Le plus probable est que tu as une erreur dans ton algo, que tu alloues a l'infini des tableaux, jusqu'a ne plus avoir de memoire dispo et que ca plante.
Verifies ton algo. Utilises le mode debug en pas a pas.
Hors sujet : ca manque de const. Et evites les pré-declarations de variables. Et n'utilises jamais les headers en <xxx.h> mais ceux en <cxxx>. N'utilises pas "using namespace".
Pour info, les warnings de clang sur ton code :
main.cpp:23:56: warning: use of old-style cast [-Wold-style-cast]
elapsedTime = (stopTime-startTime)/(CLOCKS_PER_SEC/(double)1000.0);
^ ~~~~~~
main.cpp:11:14: warning: unused parameter 'argc' [-Wunused-parameter]
int main(int argc,char *argv[])
^
main.cpp:11:25: warning: unused parameter 'argv' [-Wunused-parameter]
int main(int argc,char *argv[])
^
main.cpp:37:30: warning: implicit conversion changes signedness: 'int' to 'std::vector::size_type' (aka 'unsigned long') [-Wsign-conversion]
vector<char> tabChaines(n-1,alphabet[0]);
~~~~~~~~~~ ~^~
main.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
main.cpp:46:20: warning: implicit conversion changes signedness: 'int' to 'std::vector::size_type' (aka 'unsigned long') [-Wsign-conversion]
tabChaines[n] = alphabet[i];
~~~~~~~~~~ ^
main.cpp:46:34: warning: implicit conversion changes signedness: 'int' to 'std::vector::size_type' (aka 'unsigned long') [-Wsign-conversion]
tabChaines[n] = alphabet[i];
~~~~~~~~ ^
main.cpp:56:38: warning: implicit conversion changes signedness: 'int' to 'std::vector::size_type' (aka 'unsigned long') [-Wsign-conversion]
chaine += tabChaines[j];
~~~~~~~~~~ ^
main.cpp:43:30: warning: implicit conversion loses integer precision: 'std::vector::size_type' (aka 'unsigned long') to 'int' [-Wshorten-64-to-32]
int longAlpha = alphabet.size();
~~~~~~~~~ ~~~~~~~~~^~~~~~
main.cpp:54:30: warning: comparison of integers of different signs: 'int' and 'std::vector::size_type' (aka 'unsigned long') [-Wsign-compare]
for(int j = 0; j < tabChaines.size();j++)
~ ^ ~~~~~~~~~~~~~~~~~
10 warnings generated.
EDIT : au fait, on n'a aucune idée de ce que fais ton algo et a quoi correspondent les variables. Ce problème vient du fait que tu n'as pas utilisé des noms de variables et fonctions pertinents.
Je n'ai pas testé le code, mais quand je vois la partie de code suivante :
int RecFonc(int n,vector<string> &listeChaines,vector<char> &tabChaines,vector<char> &alphabet)//fonction de récurrence pour trouver les chaines
{
int longAlpha = alphabet.size();
for(int i = 0; i < longAlpha;i++)
{
tabChaines[n] = alphabet[i];
if(n > 0)
je me demande si le fait que ton tableau dynamique tabChaines soit sans taille précise dans ls signature, est vraiment possible.
Où en savoir plus sur les core dump ? Je ne cherche qu'à apprendre
J'alloues en effet de nombreux tableaux mais je doute que ceux-ci soient suffisamment lourd au point de saturer 6 Go de mémoire vive libre ...
HS :
Pourquoi éviter les pré-déclarations de variables ?
J'avais raté l'existence d'un header c++ pour la lib time que je n'utilise absolument jamais.
Pour using namespace, je ne l'utilise pas en temps normal mais cet algorithme a été écrit sur VIM en quelques minutes donc cela simplifiait grandement l'écriture de cet algo qui ne représente en rien un bon programme.
Pour les messages d'erreurs ... Je penserais à exécuter g++ correctement la prochaine fois ... Merci
Les noms ici ne sont pas les plus adaptés et ont été modifié par rapport au programme original afin de ne pas prêter à confusion sur son utilisation qui a pour but simple de faire un exercice sympa.
Le principe d'un vector est d'être un tableau à dimension dynamiquement variable il me semble. Tu te demandes si j'ai des index qui sont "out of range", la réponse est non. En effet, n reste dans les bornes du tableau.
je me demande si le fait que ton tableau dynamique tabChaines soit sans taille précise dans ls signature, est vraiment possible.
Ok. Tu n'as toujours pas compris comment fonctionne std::vector...
Cypher__ a écrit:
Où en savoir plus sur les core dump ?
Un core dump, c'est un "enregistrement" de l'etat du systeme lors du plantage. Pleins d'informations. Trop parfois. Donc complexe a analyser. Ou pas, la call stack est souvent la premiere chose qu'on regarde.
J'alloues en effet de nombreux tableaux mais je doute que ceux-ci soient suffisamment lourd au point de saturer 6 Go de mémoire vive libre ...
Attention, 6 Go de RAM ne veut pas dire 6 Go dispo pour ton application. C'est plus complexe que ca.
Mais de toute façon, si c'est une erreur d'algo et que tu as une boucle infinie, ca finira forcement par planter a un moment donné, quelque soit la memoire que tu as.
Cypher__ a écrit:
Pourquoi éviter les pré-déclarations de variables ?
Pourquoi faire les pré-déclarations de variables ?
Cypher__ a écrit:
J'avais raté l'existence d'un header c++ pour la lib time que je n'utilise absolument jamais.
Pourquoi éviter les pré-déclarations de variables ?
Pour limiter la portée et la visibilité de la variable, et pour rendre le code lisible EDIT : Et également pour pouvoir lui fournir une initialisation qui a du sens (c'est pas toujours le cas en pré-déclaration)
Cypher__ a écrit:
J'avais raté l'existence d'un header c++ pour la lib time que je n'utilise absolument jamais.
Ou sinon pour manipuler le temps en C++ il y a le header <chrono>
- Edité par romantik 24 octobre 2018 à 15:56:16
Dream on, Dream on, Dream until your dream comes true
-Core Dump : Je prendrais le temps de lire tout ça à tête reposée, ça promet d'être intéressant.
- RAM : je me doutais un peu (beaucoup) de cette réponse... J'ai malheureusement encore une mauvaise connaissance du système, je ne désespère pas d'apprendre un jour. Le problème, c'est que c'est tellement vaste que l'on ne sait pas trop par où commencer pour cerner le fonctionnement d'un système.
-Pré-déclarations : certainement une mauvais habitude ... La personne qui m'a fait faire mes premières lignes était un programmeur Pascal ... Je pense que ça vient de là, j'ai pris l'habitude d'en faire, je trouve ça plus clair, on déclare et ensuite on affecte. Ca me fait bizarre de faire les deux en même temps.
-Headers : Merci du lien, je savais que la plupart étaient dépréciés, je ne savais pas que tous l'étaient
-Je n'utilise pas (encore) clang, je suis actuellement avec g++, il faudrait que je me renseigne pour voir si clang serait vraiment profitable pour moi.
@YES, man
Non. C'est un appel de fonction récurrent, un fonctionnement normal.
- RAM : je me doutais un peu (beaucoup) de cette réponse... J'ai malheureusement encore une mauvaise connaissance du système, je ne désespère pas d'apprendre un jour. Le problème, c'est que c'est tellement vaste que l'on ne sait pas trop par où commencer pour cerner le fonctionnement d'un système.
Quand tu auras fini d'apprendre les bases (en gros, le livre C++ Primer), je te conseille de lire "Professional C++".
Cypher__ a écrit:
-Pré-déclarations : certainement une mauvais habitude ... La personne qui m'a fait faire mes premières lignes était un programmeur Pascal ... Je pense que ça vient de là, j'ai pris l'habitude d'en faire, je trouve ça plus clair, on déclare et ensuite on affecte. Ca me fait bizarre de faire les deux en même temps.
Il y a plusieurs arguments en faveur de ne pas pré-déclarer, dont la qualité du code (const, verification a la construction, etc). Mais aussi des arguments sur la lisibilité du code, issus des recherches cognitives (oh yeah ! On a du level en informatique !). A lire : https://zestedesavoir.com/articles/4/lisibilite-dun-code-source/
Globalement, le point important avec la programmation "old school" : les programmes ne ressemblent plus a aux programmes d'il y a 20 ans. Beaucoup plus gros, plus complexe, plus de libs, plus d'architecture, plus de materiel differents, equipes plus grosses, etc. Les methodes de développement se sont adaptés et se sont enrichis de nombreux autres domaines (cognition, design d'interface, etc).
On ne fait plus les choses comme il y a 20 ans parce que les choses ont changées.
Cypher__ a écrit:
-Je n'utilise pas (encore) clang, je suis actuellement avec g++, il faudrait que je me renseigne pour voir si clang serait vraiment profitable pour moi
Les compilateurs ne donnent pas tous les memes informations, ne detectent pas les memes erreurs. On conseille souvent de compiler le code sur plusieurs compilateurs. (Cf travisCI par exemple ou outils équivalents. Ca permet de compiler automatiquement sur plusieurs plateformes, mais aussi faire tourner des tests, faire du packaging, etc. Pleins de choses qu'il faut savoir faire pour créer un programme "moderne". En plus generalement, regardes "continous integration")
Pour using namespace, je ne l'utilise pas en temps normal mais cet algorithme a été écrit sur VIM en quelques minutes donc cela simplifiait grandement l'écriture de cet algo qui ne représente en rien un bon programme.
Ce n'est pas une excuse.
inoremap <m-s> std::
(Bon, les meta-mappings, avec vim dans le terminal c'est une cata, mais avec gvim, c'est très bien)
gbdivers a écrit:
Cypher__ a écrit:
-Pré-déclarations : certainement une mauvais habitude ... La personne qui m'a fait faire mes premières lignes était un programmeur Pascal ... Je pense que ça vient de là, j'ai pris l'habitude d'en faire, je trouve ça plus clair, on déclare et ensuite on affecte. Ca me fait bizarre de faire les deux en même temps.
Il y a plusieurs arguments en faveur de ne pas pré-déclarer, dont la qualité du code (const, verification a la construction, etc). Mais aussi des arguments sur la lisibilité du code, issus des recherches cognitives (oh yeah ! On a du level en informatique !). A lire : https://zestedesavoir.com/articles/4/lisibilite-dun-code-source/
Il faut que je décortique l'article, mais je n'y vois pas vraiment d'argument en faveur de l'abandon de la pré-déclaration. C'est limite le contraire.
Il faut que je décortique l'article, mais je n'y vois pas vraiment d'argument en faveur de l'abandon de la pré-déclaration. C'est limite le contraire.
J'ai cité l'article de mémoire, mais je crois que c'est bien celui laà que j'avais en tête. L'argument est sur la localité des informations : il est plus facile de comprendre le code quand les informations sont regroupées (ici la création de la variable et l'initialisation) sur une seule ligne plutôt que de les séparer.
C'est pas l'argument le plus fort contre les pré-déclaration, mais je l'aime bien, parce que cela montre que des choses comme la lisibilité du code (et beaucoup d'autres choses en programmation "moderne") peuvent être étudiées par une approche objective scientifique.
Le mieux étant de prendre les *debug_full_broken_abi qui ne fonctionneront pas très bien si on utilise des bibliothèques qui exposent des objets de la stl mais compilés avec des options différentes. Pour des programmes de test il n'y a pas de problème, sinon il faut utiliser les *debug_full.
Concernant ton algo, il y a un problème de complexité qui est de O(26^n)^ pour puissance. Avec n=3, il y a 17'576 éléments dans le vector. Avec n=5, il y en a 11'881'376. À vrai dire, je ne comprends pas à quoi correspond n et ce que tu entends par toutes les possibilités ? Uniquement les permutations ? Peut-on avoir des lettres en double ? Un résultat entre 0 et 26 caractères ou toujours 26 ?
Il galère pour faire 5 boucles imbriqués mais le besoin final est le même.
Et la solution qu'on lui propose est de ne pas utiliser la récursivité, mais de faire une simple conversion int=>représentation d'un int dans un alphabet de 36 chiffres.
Et coté complexité, comme l'indique @jo_link_noir, nous, avec cet algo (non récursif), on est assez détendu sur le bidule. Niveau mémoire, on doit être à O(1) à la louche (la console, c'est pas chez moi).
Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
Avant toute chose, merci à tous pour vos réponses.
@gbdivers merci pour les livres, je regarderais ça quand j'aurais un peu plus de temps ...
Et merci aussi pour l'article qui fut fort intéressant même si il n'y a pas vraiment d'arguments en défaveur de la pré-déclaration des variables. Ils notent en effet que la centralisation des données est plus efficace mais seulement dans une certaine limite. Il vaudrait donc mieux parfois déclarer avant leur utilisation (le plus tard possible, d'accord) les variables.
Et j'ai en effet plutôt appris "old school" ce qui ne semble pas être forcément une bonne chose, mais j'ai encore le temps pour changer. Le tout c'est de savoir qu'il y a un problème.
@lmghs je considère ça comme une excuse vu que j'étais en effet uniquement avec vim dans la console ... Ce qui m'intéressait, c'était plus le principe plutôt que le programme.
Merci pour le lien, je prends note pour les déclarations de variables ...
@jo_link_noir Merci pour le dépôt, je regarderais ça.
En fait il y a un peu plus que ça ... Il y a plutôt 52^n possibilité avec l'alphabet fournit.
Imaginons que nous avons un alphabet de trois lettre {a,b,c} pour une chaîne de 3 caractères, il y a 3^3 possibilités soit 27 qui sont :
aaa
baa
caa
aba
bba
cba
aca
bca
cca
aab
bab
cab
abb
bbb
cbb
acb
bcb
ccb
aac
bac
cac
abc
bbc
cbc
acc
bcc
ccc
Peut-être que ce sera un peu plus clair
@bacelar je ne vois pas en quoi le fait de changer le tableau de caractère en une suite de nombres changerait la complexité de l'algorithme. Peut-être pourriez vous définir ce que vous appelez la complexité d'un algorithme ?
En fait, si tu respectes SRP (Single Responsability Principle) la question de déclarer au plus près ses variables de leur utilisation ne se pose quasiment plus. En effet, ta fonction va être tellement courte, que tu auras au maximum deux ou trois variables locales qui se battent en duel pour un corps de fonction qui ne dépassera pas les 10 lignes. Dans ces conditions, peu probable qu'un problème puisse passer à travers ta sagacité où les tests que tu auras mis en place.
Pour ce qui concerne l'approche récursive en général (pas forcément dans ton cas), elle présente un premier problème qui est d'être bien au point sur la condition d'arrêt, si tu te rates, c'est le débordement de pile avec plantage assuré à la clé. Le soucis, c'est que sera grandement dépendant des données de départ, donc il sera difficile de tester une approche récursive de manière à avoir une couverture de l'espace des possibilités convenable. Le second, c'est qu'elle peut s'avérer assez gourmande en mémoire parce que tu vas potentiellement devoir garder de multiples états en mémoire, et que si tu en as trop, çà risque de péter sur une copie. Une approche itérative lorsqu'elle est pertinente, permet de souvent mieux borner le contexte, et donc d'avoir une couverture par les tests correcte "plus facile" à établir. C'est à dire que je vais pouvoir plus facilement imaginer un jeu de tests, qui me donnera un haut degré de fiabilité, qu'avec une approche récursive. C'est essentiellement dû au bornage strict des approches itératives. Après transformer un algorithme récursif en son pendant itératif(ou l'inverse, c'est plus rare, mais parfois...), c'est pas forcément simple, l'algorithme récursif peut être beaucoup plus lisible et compréhensible que l'itératif et ça joue aussi, car on relit plus souvent son code qu'on ne l'écrit...
Et globalement, merci à tous, ce sujet s'est avéré profitable.
Je vais le passer en résolu, ça ne sert à rien de s'attarder dessus, encore une fois merci à tous
std::bad_alloc Abandon : core dumped
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Discord NaN. Mon site.
Discord NaN. Mon site.
Discord NaN. Mon site.
Discord NaN. Mon site.