limite memoire - Page 1

Bonjour

J'utilise TIGCC 0.96 et je programme en c (ti89 titanium).

Je crée crée un jeu avec lequel on peut jouer contre un adversaire géré par le programme
l'algorithme qui fait jouer l'adversaire utilise une fonction recursive qui teste touts les coups possibles et garde celui qui aboutit à la mailleure configuration
En pratique cela fonctionne pas mal et tres rapidement, mais lorsque la fonction doit s'apeller recursivement plus de 4 fois la calculatrice plante (invalid instruction - barre noire).
La fonction s'appelle avec en parametre un tableau tridimensonnel de 512 type short.

Est-ce qu'il y a une limite de memoire ? Si oui peut-on la repousser ?

c'est peut-être effectivement un problème de mémoire si ton tableau est alloué sur la pile. Je sais plus de combien est la taille de la pile, mais si à chaque appel tu bouffe 1ko, s'est sur que ca fait beaucoup.
Alloue ton tableau avec malloc et free plutot que de la prendre sur la pile.

oui mais peut-on implémenter malloc et free en recursif ?
la calculatrice dispose de 192 ko de memoire vive. le compilateur limite-t-il la memoire allouée au programme ?
puisque si je reprends to raisonnement avec 4 appels 4*1ko on est loin du 192.
enfin qu'est ce que la pile ?

merci hibou

la pile c'est une petite partie de la ram qui sert a faire des appels de fonctions et stocker les variables locales :

void f() {
  //sur la pile
  int x;
  int tab[256];
  int tab2[];

  //dans la RAM
  tab2 = malloc(200*sizeof(int));
  //la y'a 400 o. de moins de libre dans la ram
  free(tab2);
  //la il sont de nouveau libres
}

avec malloc, tu peux en faire autant que tu veux dans les 192ko
la pile, y'en a 16ko je crois.
Le pb avec la pile, c'est que tu sais pas quand elle est pleine. Avec malloc, s'il te renvoie NULL, c'est qu'il n'y a plus de place libre.

le probleme c'est alors d'implanter la gestion de memoire malloc / free dans ma recursivité.
la fonction s'appelle avec une structure de données regroupant chaque cas.
comment gérer alors l'allocation dynamique dans ce cas ?

merci hibou pour ces précisions

La, je sais pas trop de quoi tu causes, donc je peux pas trop t'aider. Il faudrait que tu me détailles un peu plus ton algo, que tu mettes meme le code (cf le lien "sources" à droite quand tu veux poster un message)

oui j'ai galéré pas mal avec ces balises. j'ai pas l'habitude. merci

donc voila ma structure "node" passee en argument :

// structure de liens entre les points
typedef short tab[9][7][9];

// node
typedef struct
{
	tab link;
	short x;
	short y;
	short path[20];
	short pathindex;
} node;

et voici ma fonction recursive :

void m68kpath(node prevnode)
{
	short i, tmpx, tmpy;
	for(i=1;i<=8;i++)
	{
		if(prevnode.link[prevnode.x][prevnode.y][i]!=1) continue;			
		n++;
		node tmpnode=prevnode;
		tmpnode.link[prevnode.x][prevnode.y][i]=2;
		tmpnode.link[prevnode.x][prevnode.y][0]=1;
		tmpx=prevnode.x+dir[i][0];
		tmpy=prevnode.y+dir[i][1];
		tmpnode.x=tmpx;
		tmpnode.y=tmpy;			
		tmpnode.link[tmpx][tmpy][0]=1;
		tmpnode.link[tmpx][tmpy][ind[prevnode.x-tmpx+1][prevnode.y-tmpy+1]]=2;
		tmpnode.path[prevnode.pathindex]=i;
		if(prevnode.link[tmpx][tmpy][0]==0)
		{
			if((tmpx*tmpx+(tmpy-3)*(tmpy-3))<(bestx*bestx+(besty-3)*(besty-3)))
			{
				bestx=tmpx;
				besty=tmpy;
				pathnode=tmpnode;
			}
		}		
		else
		{
			tmpnode.pathindex++;
			m68kpath(tmpnode);
		}
	}		
}

édite ton post et mets des balises "pre" autour (comme pour mon post ./4)
c'est illisible la.

tu as du mal avec les balises je vois ^^.

indice : clique sur "citer" de mon post ./4 pour voir le "source" de mon post. sinon tu as les liens à droite quand tu tapes ton post.

Tu peux virer "SAVE_SCREEN" -> ça bouffe 3840 octets sur la pile
2 solutions:
-tu force le refresh (il y a un topic qui en parle actuellement sur yN)
-tu copie manuellement la zone écran dans une zone allouée.

xantares>je vois pas de problèmes particuliers : au lieu de travailler avec des structure, tu vas travailler avec des pointeurs sur ces structures.

void m68kpath(node prevnode) 
    ...
    node tmpnode=prevnode
    ...
    if... { 
      if... {
        pathnode=tmpnode; 
       ...
      }
    }
  }
}

se change en

void m68kpath(node * prevnode) {
...
    node * tmpnode=malloc(sizeof(node));
    memcpy(tmpnode,prevnode,sizeof(node));
    tmpnode->link[prevnode.x][prevnode.y][i]=2; 
    ....
    if... { 
      if... {
        memcpy(pathnode,tmpnode,sizeof(node));
        ....
      }
    }
  }
  free(tmpnode);
}

y'a juste pathnode, je sais pas ou il est créé, mais lui aussi faudra qu'il soit un pointeur, faut lui faire aussi un malloc et un free.

jfg>c'est qu'un début de solution vu ce qui est consommé dans cet algo.

oui, mais c'est ce qui ya de + facile à changer

voila g posté mon code plus hat (foutues balises........)
en fait basiquement c ca

void fonction(node)
{
nodesuivante node;
for( i=1 jusqu'a 8)
{
modifications sur nodesuivante
fonction(nodesuivante)
{
}

avec la strucure node qui contient un tableau tridimentionnel de environ 500 entiers short

jfg :
-tu force le refresh (il y a un topic qui en parle actuellement sur yN)

heu, ou ca ?

topics/63197-viewer-de-matrixlist/3
à partir du post ./72

pathnode est declarée dans une fonction englobant la fonction recursive.
pourquoi faut-il que ce soit des pointeurs ?
je vois pas ce que ca change en terme d'utilisation de la memoire.
d'accord la fonction s'executera plus vite mais les variables sur lesquelles pointent les pointeurs devront toujours etre crees.
je ne comprends pas l'utilité de memcpy

merci pour vos messages

petite précision/erreur : le malloc, le faire en dehors de la boucle for

void m68kpath(node * prevnode) {
...
  node * tmpnode=malloc(sizeof(node));
  for (.....) {
    memcpy(tmpnode,prevnode,sizeof(node));
    tmpnode->link[prevnode.x][prevnode.y][i]=2; 
    ....
    if... { 
      if... {
        memcpy(pathnode,tmpnode,sizeof(node));
        ....
      }
    }
  }
  free(tmpnode);
}

./16 > Oui, mais les variables seront allouées sur le tas et pas sur la pile. Revois tes cours de programmation !

Sasume :
./16 > Oui, mais les variables seront allouées sur le tas et pas sur la pile. Revois tes cours de programmation !

a quoi fais-tu reference ? a l'utilisation des pointeurs ?

xantares :
pathnode est declarée dans une fonction englobant la fonction recursive. pourquoi faut-il que ce soit des pointeurs ?

parce que malloc te renvoie un pointeur sur l'espace mémoire alloué

je vois pas ce que ca change en terme d'utilisation de la memoire.

le malloc va chercher la mémoire dans toute la RAM disponible. Les variables locales sont mises dans la pile, qui est une petite partie de la RAM (16ko sur les 192 ko)

d'accord la fonction s'executera plus vite mais les variables sur lesquelles pointent les pointeurs devront toujours etre crees.

je pense pas que ca aille plus vite, mais tu as accès a bien plus de mémoire

je ne comprends pas l'utilité de memcpy

quand tu fais
node tmpnode=prevnode tu crées une variable sur la pile, et tu recopie tout ce qu'il y a dans prevnode dans tmpnode
avec le malloc, on a un espace mémoire, puis il faut recopier le contenu de tmpnode dans prevnode

T'es patient hibou

ah ouaaaaaaaaaais !

merci beaucoup hibou

d'accord ca y est g compris.
mais quelqu'un peut m'en dire un peu plus sur les commandes malloc/free/memcpy ?

Sasume>je dois faire du ocaml au boulot, donc je suis assez content de pouvoir faire un peu de C

xantares>un peu vague ta question... assez vague pour que tu trouves facilement la réponse dans la littérature, notemment dans la doc de tigcc

hibou>c vrai là j'abuse de votre gentillesse

ben j'vais me debrouiller avec tout ca alors

merci beaucoup les gens hibou, sasume, jfg

En plus comme tu passes tes valeurs par copie, tu copie 2x tes arguments sur la pile. Pas etonnnant que ca plante si vite.
(En plus d'etre hyper lent).

PpHd :
En plus comme tu passes tes valeurs par copie, tu copie 2x tes arguments sur la pile. Pas etonnnant que ca plante si vite.
(En plus d'etre hyper lent).

le programme reagit à peu près au dixieme de seconde dans le cas de deux ou trois appels recursifs
d'accord c pas encore optimisé mais le compilateur fait bien son boulot et ca reste fluide en regard de l'algorithme

cela dit il me reste un dernier probleme :
la variable transmise étant une structure (node) lorsque j'utilise un pointeur vers celle-ci dans ma fonction, je n'arrive pas à accéder
aux elements de ma structure

// node 
typedef struct 
{ 
	tab link; 
	short x; 
	short y; 
	short path[20]; 
	short pathindex; 
} node; 

*tmpnode renvoie bien node mais le compilateur retourne une erreur quand j'utilise *tmpnode.x par exemple

(*tmpnode).x ?
Sinon : tmpnode->x.

tmpnode->x our (*tmpnode).x

Quand tu as un pointeur vers une structure, tu dois utiliser la flèche -> au lieu du point.
Si tu fais *tmpnode.x, tu prends tmpnode.x pour un pointeur et tu veux y accéder, mais x n'est pas un pointeur, d'où le problème. Cela dit, peut-être que (*tmpnode).x fonctionne, je ne me rappelle plus, mais la solution correcte est tmpnode->x.
[Edit] Oups j'étais pas logué, et je n'ai pas vu les deux derniers messages Désolé...