## 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>

##### 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!

##### Share on other sites

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.

<Signature goes here>

##### 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

isto resulta em :

- ordernar 9 valores

- ordernar 10 valores

- ordernar 11 valores

...

- ordernar 5009 valores

 IRC : sim, é algo que ainda existe >> #p@p
##### 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

##### 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."

##### 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>

##### 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

isto resulta em :

- ordernar 9 valores

- ordernar 10 valores

- ordernar 11 valores

...

- ordernar 5009 valores

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."

##### 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.

##### 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";

QueryPerformanceCounter(&li);
}
double GetCounter()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
}

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."

##### 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

##### 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."

##### 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

##### 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";

QueryPerformanceCounter(&li);
}
double GetCounter()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
}

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

//....

vecpair arr;

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."

##### 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";

QueryPerformanceCounter(&li);
}
double GetCounter()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
}

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

//....

vecpair arr;

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."

##### 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.

## Create an account

Register a new account

×

• #### Revista PROGRAMAR

• Wiki
• IRC
×
• Create New...