Jump to content

Porque é que este pedaço de código é tão lento?


xtrm0
 Share

Recommended Posts

Boas, estava a treinar para o CIIC, quando ao fazer a seguinte função, reparei que ela demorava quase 4 segundos a correr havendo apenas 9 valores no total dentro de todos os vetores

vector <vector<pair<int,int> > > mapa (5001, vector<pair<int,int> >());

/*...*/
/*mete la os valores*/
/*...*/

for (int x=0; x<5001; x++) {
if (!mapa[x].empty())
	sort(mapa[x].begin(), mapa[x].end());
mapa[x].push_back(pair<int,int>(-1,0));
}

Porque é que é tão lento?

Edited by xtrm0

<Signature goes here>

Link to comment
Share on other sites

Eu não sei C++.

Qual é a relação entre i (a variável de controle do ciclo) e x (a variavel que indexa o mapa).

Aparentemente estás a fazer a mesma coisa 5000 vezes.

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

o que vejo no código é que estás a efetuar sobre um vector inicial com 9 valores

- num ciclo de 1 a 5000

- ordenar o vector

- adicionar um novo elemento

isto resulta em :

- ordernar 9 valores

- adicinar um valor

- ordernar 10 valores

- adicinar um valor

- ordernar 11 valores

...

- adicinar um valor

- ordernar 5009 valores

e normal demorar um bocado devido a tantas chamadas a ordenações

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

De facto, tendo em conta que estás a usar um vector, faz mais sentido inserires na posição ordenadamente.

Edited by KTachyon

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Link to comment
Share on other sites

um multi-map nao seria mais pratico e rapido?

EDIT: Sei que a pesquisa por valores nao e' tao rapida como o vector, mas simplifica mais a forma como pensas no problema.

Edited by pikax

Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Link to comment
Share on other sites

Não é isso que eu estou a fazer.

Eu tenho um vetor bidimensional de 5000 por k(que pode ir ate 5000)

Na parte onde estão os commentos, eu leio o input do problema e insiro-o dentro dos vetores.

Depois ordeno cada um dos 5000 vetores e adiciono um par de inteiros (-1,0), que serve para saber onde é o fim de cada um dos vetores de tamanho variavel, sem ter de estar a por ifs.

Nos 5000 vetores que eu tenho ha apenas no total 9 pares, mais os 5000 (-1,0). No entanto esta parte do codigo demora 4 segundos a correr. Porquê?

Edited by xtrm0

<Signature goes here>

Link to comment
Share on other sites

Acho que um multimap faz isso tudo sozinho, porque a "ordenacao" e' feita na hora em que o valor e' inserido.

Nos 5000 vetores que eu tenho ha apenas no total 9 pares, mais os 5000 (-1,0). No entanto esta parte do codigo demora 4 segundos a correr. Porquê?

o que vejo no código é que estás a efetuar sobre um vector inicial com 9 valores

- num ciclo de 1 a 5000

- ordenar o vector

- adicionar um novo elemento

isto resulta em :

- ordernar 9 valores

- adicinar um valor

- ordernar 10 valores

- adicinar um valor

- ordernar 11 valores

...

- adicinar um valor

- ordernar 5009 valores

e normal demorar um bocado devido a tantas chamadas a ordenações

Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Link to comment
Share on other sites

Sugiro que sejas mais explicito e mostres o programa todo em que fizeste esse teste (e com que input) em que demorava 4 segundos.


#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int i , x;
vector <vector<pair<int,int> > > mapa (5001, vector<pair<int,int> >());

for (i = 0 ; i < 9 ; i++) { // teste
	mapa[i].push_back(make_pair(i,i));	
}

for (x=0; x<5001; x++) {
	if (!mapa[x].empty())
		sort(mapa[x].begin(), mapa[x].end());
	mapa[x].push_back(pair<int,int>(-1,0));
}
return 0;
}

time ./a

real 0m0.009s

user 0m0.004s

sys 0m0.003s

edit: pikax, se o objectivo é simplesmente ordenar os valores, um sort é muito melhor do que usar uma árvore (multimap). Para além disso, o acesso ao multimap é feito em O(log N) enquanto que o acesso a um elemento no vector depois da ordenação é O(1) (constante).

Edited by mogers

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

edit: pikax, se o objectivo é simplesmente ordenar os valores, um sort é muito melhor do que usar uma árvore (multimap). Para além disso, o acesso ao multimap é feito em O(log N) enquanto que o acesso a um elemento no vector depois da ordenação é O(1) (constante).

EDIT: Sei que a pesquisa por valores nao e' tao rapida como o vector, mas simplifica mais a forma como pensas no problema.

Em termos de acesso e' muito melhor o vector, no multi map ao inserir ja' faz a ordenacao,

Sugiro que sejas mais explicito e mostres o programa todo em que fizeste esse teste (e com que input) em que demorava 4 segundos.


#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int i , x;
vector <vector<pair<int,int> > > mapa (5001, vector<pair<int,int> >());

for (i = 0 ; i < 9 ; i++) { // teste
	mapa[i].push_back(make_pair(i,i));	
}

for (x=0; x<5001; x++) {
	if (!mapa[x].empty())
		sort(mapa[x].begin(), mapa[x].end());
	mapa[x].push_back(pair<int,int>(-1,0));
}
return 0;
}

Tas errado a preencher os valores, so' estas a inserir nove elementos no vector e nao 5001, a mim os testes dao cerca de 4+ segundos.

etenho aqui o teste, esta' a estourar a segunda passagem, tou com um bocado de pressa, por isso deixo aqui, e' so' para windows, como o windows nao tem a funcao time(acho eu), usei o performancecounter para calcular o tempo.

#include <vector>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <windows.h>
#include <iostream>

using namespace std;

//timer vars
double PCFreq = 0.0;
__int64 CounterStart = 0;

//timer functions
void StartCounter()
{
LARGE_INTEGER li;
if(!QueryPerformanceFrequency(&li))
cout << "QueryPerformanceFrequency failed!\n";

PCFreq = double(li.QuadPart)/1000.0;

QueryPerformanceCounter(&li);
CounterStart = li.QuadPart;
}
double GetCounter()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
return double(li.QuadPart-CounterStart)/PCFreq;
}


void insertmap(multimap<int,int> *map)
{
int i , x,b;
//vector <vector<pair<int,int> > > mapa (5001, vector<pair<int,int> >());

for (i = 0,b = 0 ; i < 9 ; i++,b++) { // teste
		//mapa[i].push_back(make_pair(i,i));
		map->insert(pair<int,int>(i,b));

}

}


void insertMatrixPair(vector <vector<pair<int,int> > > &mapa)
{
int i , x,b;

for (x=0; x<5001; x++) {
		if (!mapa[x].empty())
				sort(mapa.at(x).begin(), mapa.at(x).end());
	mapa[x].push_back(pair<int,int>(-1,0));
}
}

//void compare()

int main()
{

	multimap<int,int> *map;
	vector <vector<pair<int,int> > > mapa(5002, vector<pair<int,int> >());
	int x;

	for (x = 0 ; x < 5001 ; x++) { // teste
			mapa[x].push_back(make_pair(x,x));
	}

	for(int i=0;i<15;i++)
	{
		map = new multimap<int,int>();
		StartCounter();
		insertmap(map);
		cout<<"MAP - "<<GetCounter()<<"ms"<<endl;

		StartCounter();
		insertMatrixPair(mapa);
		cout<<"MatrixPair - "<<GetCounter()<<"ms"<<endl;

		for(int a= 0;a<5001;a++)
		{
			mapa[a].clear();
			mapa[x].push_back(make_pair(x,x));
			//mapa[a].erase(mapa[a].begin(),mapa[a].end());
		}

		mapa.clear();
		map->clear();

		delete map;
	}



	return 0;
}

EDIT: Nao corrigi o "estouranco" porque como disse anteriormente, um multi-map e' mais pratico, quando se comeca a usar matriz de pares, troquei-me todo no construtor com o operador new, por isso nem tentei mais.

Edited by pikax

Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Link to comment
Share on other sites

Tas errado a preencher os valores, so' estas a inserir nove elementos no vector e nao 5001, a mim os testes dao cerca de 4+ segundos.

O xtrm0 disse que cada vector tem apenas 9 elementos.

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Link to comment
Share on other sites

O xtrm0 disse que cada vector tem apenas 9 elementos.

por isso mesmo, a insercao so esta a preencher nove vetores de pares, em vez de preencher 5001 vectores de array com 9 pares cada, que significa que aumentara' mais uns milisegundos.

Entao o teste de insercao seria assim:

for(int i=0;i<5001;i++)
 for(int a=0;a<9;a++)
   mapa[i].push_back(make_pair(i,a));

Nao sei se o multi-map podera' ser utilizado, porque ele esta a usar uma matriz de pares, e um multimap e' um vector de pares. Entao penso que um Vector de set de pares seria melhor, ja' que nao e' necessaria a ordenacao.

Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Link to comment
Share on other sites

por isso mesmo, a insercao so esta a preencher nove vetores de pares, em vez de preencher 5001 vectores de array com 9 pares cada, que significa que aumentara' mais uns milisegundos.

Ah, sim, tens razão. Mas não deverá ser isso que está a fazer o algoritmo demorar os 4 segundos.

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Link to comment
Share on other sites

Ah, sim, tens razão. Mas não deverá ser isso que está a fazer o algoritmo demorar os 4 segundos.

a mim a insercao de todos os valores demora entre 1.5~2.0 segundos.

esta aqui o codigo que estou a usar:

#include <vector>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <windows.h>
#include <iostream>

using namespace std;

//timer vars
double PCFreq = 0.0;
__int64 CounterStart = 0;

//timer functions
void StartCounter()
{
LARGE_INTEGER li;
if(!QueryPerformanceFrequency(&li))
cout << "QueryPerformanceFrequency failed!\n";

PCFreq = double(li.QuadPart)/1000.0;

QueryPerformanceCounter(&li);
CounterStart = li.QuadPart;
}
double GetCounter()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
return double(li.QuadPart-CounterStart)/PCFreq;
}


void insertMatrixPair(vector <vector<pair<int,int> > > &mapa)
{
int i , x,b;

for (x=0; x<5001; x++) {
		if (!mapa[x].empty())
				sort(mapa.at(x).begin(), mapa.at(x).end());
	mapa[x].push_back(pair<int,int>(-1,0));
}
}


int main()
{

	multimap<int,int> *map;
	vector <vector<pair<int,int> > > mapa(5002, vector<pair<int,int> >());
	int x;


	StartCounter();
	for (x = 0 ; x < 5001 ; x++) { // teste
			mapa[x].push_back(make_pair(x,x));
	}
	cout<<"Fill vector - "<<GetCounter()<<"s"<<endl; //cerca de 1.5~2.0segundos
	StartCounter();
	insertMatrixPair(mapa);
	cout<<"Call insertMatrixPair - "<<GetCounter()<<"s"<<endl; //cerca de 2.0s
}

EDIT: Acho que descobri o problema(acho eu), e' o uso do vector, como ao se criar o vector sem reservar memoria, parece que as chamadas de alocacao de memoria(ao crescer o vector) estao a comer muito tempo(pelo o menos no meu windows).

consegui reduzir a insercao de valores no array de ~2s para ~0.5s, usando uma estrutura de nove pares.


struct vecpair
{
   pair<int,int> _pair[9];
};

//....

vecpair arr[5001];

for(int i=0;i<5001;i++)
 for(int a=0;a<9;a++)
   arr[i]._pair[a] = pair<int,int>(i,a);//make_pair(i,a);
Edited by pikax

Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Link to comment
Share on other sites

a mim a insercao de todos os valores demora entre 1.5~2.0 segundos.

esta aqui o codigo que estou a usar:

#include <vector>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <windows.h>
#include <iostream>

using namespace std;

//timer vars
double PCFreq = 0.0;
__int64 CounterStart = 0;

//timer functions
void StartCounter()
{
LARGE_INTEGER li;
if(!QueryPerformanceFrequency(&li))
cout << "QueryPerformanceFrequency failed!\n";

PCFreq = double(li.QuadPart)/1000.0;

QueryPerformanceCounter(&li);
CounterStart = li.QuadPart;
}
double GetCounter()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
return double(li.QuadPart-CounterStart)/PCFreq;
}


void insertMatrixPair(vector <vector<pair<int,int> > > &mapa)
{
int i , x,b;

for (x=0; x<5001; x++) {
		if (!mapa[x].empty())
				sort(mapa.at(x).begin(), mapa.at(x).end());
	mapa[x].push_back(pair<int,int>(-1,0));
}
}


int main()
{

	multimap<int,int> *map;
	vector <vector<pair<int,int> > > mapa(5002, vector<pair<int,int> >());
	int x;


	StartCounter();
	for (x = 0 ; x < 5001 ; x++) { // teste
			mapa[x].push_back(make_pair(x,x));
	}
	cout<<"Fill vector - "<<GetCounter()<<"s"<<endl; //cerca de 1.5~2.0segundos
	StartCounter();
	insertMatrixPair(mapa);
	cout<<"Call insertMatrixPair - "<<GetCounter()<<"s"<<endl; //cerca de 2.0s
}

EDIT: Acho que descobri o problema(acho eu), e' o uso do vector, como ao se criar o vector sem reservar memoria, parece que as chamadas de alocacao de memoria(ao crescer o vector) estao a comer muito tempo(pelo o menos no meu windows).

consegui reduzir a insercao de valores no array de ~2s para ~0.5s, usando uma estrutura de nove pares.


struct vecpair
{
pair<int,int> _pair[9];
};

//....

vecpair arr[5001];

for(int i=0;i<5001;i++)
 for(int a=0;a<9;a++)
arr[i]._pair[a] = pair<int,int>(i,a);//make_pair(i,a);

EDIT2: Os tempos estao errados, porcaria do windows 😄

Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Link to comment
Share on other sites

Nos 5000 vetores que eu tenho ha apenas no total 9 pares, mais os 5000 (-1,0). No entanto esta parte do codigo demora 4 segundos a correr. Porquê?

Por esta frase, eu percebi que só existem 9 no total e não em cada um dos vectors.

Sobre o multimap, sim faz a ordenação mas as árvores têm muito overhead em relação ao uso do sort.

Para ver o tempo de execução em windows, costumo fazer assim:

#include <time.h>

int main() {
   clock_t start = clock();

   // codigo

   // final
   clock_t ends = clock();
   printf("Tempo de execucao: %.5f seg\n\n",(double) (ends - start) / CLOCKS_PER_SEC);
   return 0;
}

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.