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

[xtrm0]

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 July 28, 2012 at 03:18 PM by xtrm0

[pmg]

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.

[xtrm0]

Há enganei-me a copiar. Era suposto estar o i no local do x XD. Já troquei. lol. Mas pkk está lento? Só está a fazero sort de 5000 vetores com um valor cada.

[HappyHippyHippo]

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

[KTachyon]

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

Edited July 27, 2012 at 11:09 PM by KTachyon

[pikax]

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 July 27, 2012 at 11:37 PM by pikax

[xtrm0]

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 July 28, 2012 at 03:17 PM by xtrm0

[pikax]

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

[mogers]

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 July 28, 2012 at 07:35 PM by mogers

[pikax]

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 July 28, 2012 at 08:51 PM by pikax

[KTachyon]

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.

[pikax]

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.

[KTachyon]

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.

[pikax]

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 July 28, 2012 at 11:50 PM by pikax

[pikax]

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 😄

[mogers]

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;
}