Ir para o conteúdo
fransma64

Memória

Mensagens Recomendadas

fransma64    0
fransma64

Olá pessoal. Sou um iniciante na programação em c++ e tenho andado a resolver problemas das oni. No entanto ainda não consegui perceber como a memória funciona e ainda não consegui ter nenhuma submissão aceite no servidor mooshak por causa disso.

Os limites para os problemas das oni são:

  • Limite de memória global: 256MB
  • Limite de memória de stack: 256MB
  • Limite de tamanho de código fonte: 32KB

Como é que eu posso saber se o meu programa cumpre cada um destes parâmetros? Existe alguma forma de determinar a memória usada de forma exata ou pelo menos fazer uma estimativa?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

A sugestão do HHH é a melhor, especialmente se o teu programa for relativamente simples (por exemplo, várias chamadas recursivas podem estourar a stack).

Se precisares de ajuda indica qual o problema e coloca o código.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
fransma64    0
fransma64

claro ... conta os bytes reservados pelas tuas variáveis e/ou alocações de memória

A sugestão do HHH é a melhor, especialmente se o teu programa for relativamente simples (por exemplo, várias chamadas recursivas podem estourar a stack).

Se precisares de ajuda indica qual o problema e coloca o código.

No problema 2 da fase de qualificação das oni 2014-desenhando quadrados, por exemplo, excedi o limite de memória. O meu código é o seguinte:

#include <iostream>

using namespace std;
struct point{
double x;
double y;};
int main()
{
bool** coord=new bool*[20001];
for(int i=0;i<=20000;i++){
   coord[i]=new bool[20001];
}
for(int i=0;i<=20000;i++){
   for(int j=0;j<=20000;j++){
    coord[i][j]=false;}
   }
int N,xx,yy;
cin>>N;
point *p=new point[N];
for(int i=0;i<=N-1;i++){
  cin>>xx>>yy;
   p[i].x=xx;
   p[i].y=yy;
   coord[xx][yy]=true;
}
point medio;
int numq=0;
int amax=0;
int xx1,xx2,yy1,yy2;
int mx,my;
for(int i=0;i<=N-2;i++){
   for(int j=i+1;j<=N-1;j++){
	    mx=(p[i].x+p[j].x);
	    my=(p[i].y+p[j].y);
    if( (((mx)%2==0) and ((my)%2==0))or (((mx)%2==1) and ((my)%2==1)) ){
	    medio.x=(p[i].x+p[j].x)/2;
	    medio.y=(p[i].y+p[j].y)/2;
	    if((medio.x+(p[i].y-p[j].y)/2>0) and (medio.x+(p[j].y-p[i].y)/2>0) and (medio.y+(p[i].x-p[j].x)/2>0) and (medio.y+(p[j].x-p[i].x)/2>0)){
		    xx1=medio.x+(p[i].y-p[j].y)/2;
		    xx2=medio.x+(p[j].y-p[i].y)/2;
		    yy1=medio.y+(p[i].x-p[j].x)/2;
		    yy2=medio.y+(p[j].x-p[i].x)/2;
		    if((coord[xx1][yy2]==true) and (coord[xx2][yy1]==true)){
			   numq=numq+1;
			   if((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)>amax){
			    amax=(p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y);
			   }
		    }
	    }
    }
   }
}
delete []p;
for(int i=0;i<=20000;i++){
   delete []coord[i];
}
delete []coord;
cout<<"\n"<<numq/2<<"\n";
if(amax>0){
cout<<amax/2;}

}

Como posso calcular a memória global e a memória de stack usada utilizando a sugestão do HHH?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1132
HappyHippyHippo

bem ... parece que tens uma matrix de 20001 por 20001 booleanos.

se cada booleano ocupar 1 byte, então só ai tens 20001 * 20001 = 400040001 bytes

400040001 Bytes / 1024 ~= 390664 KB ~= 381 MB > 256MB limite

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
fransma64    0
fransma64

bem ... parece que tens uma matrix de 20001 por 20001 booleanos.

se cada booleano ocupar 1 byte, então só ai tens 20001 * 20001 = 400040001 bytes

400040001 Bytes / 1024 ~= 390664 KB ~= 381 MB > 256MB limite

Muito obrigado pela ajuda. Outra questão, qual é a diferença entre a memória global e a memória de stack. E a memória heap, que foi onde eu aloquei a minha matriz. É contabilizada como memória global ou memória de stack?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

Estes conceitos aplicam-se a C/C++, outras linguagens gerem a memória de forma diferente (e.g. Java tem Garbage Colector e isso tem um impacto gigante nesta discussão):

A stack é a área onde são colocadas as variáveis locais (e.g. o teu apontador "coord", as variáveis N, xx e yy, etc.). Também são colocados na stack os argumentos de funções, dado que são variáveis locais. Estas variáveis são "apagadas" assim que a função retorne e o espaço de memória pode ser reutilizado; é por este motivo que se declarares uma variável dentro de uma função e guardares o seu apontador, depois da função retornar esse espaço de memória pode ter sido reescrito.

Para a heap vão as variáveis globais e tudo o que é declarado dinamicamente (e.g. a tua matriz coord).

Acho que já percebeste que não podes declarar a variável coord porque excede os 256MB, mas em situações como a tua é preferível declarar a variável coord como global (simplesmente "bool coord[20001][20001]") do que como está actualmente.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade