# Array of Vectors amd other STL questions

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 04-10-2007
kolistivra
Array of Vectors amd other STL questions
Hi,

I'm experimenting to code dijkstra with STL. The STL version of the algorithm runs slower than the hand-written heap, expectedly.

Even though STL one probably will never work as fast as the C version with heap, I'm looking for some tips to speed up this code.

here is the code:

Code:

```#include <iostream> #include <cstdio> #include <set> #include <cstdlib> #include <ctime> #include <fstream> #include <vector> #include <algorithm> #include <utility> //#define ii pair<int,int> #define MAXV 8002 #define UNDIRECTED 1 #define MAX 0x7fffffff int startv = 1, finalv = 0, nvertex, nedge; using namespace std; FILE *in,*out; //ifstream in("girdi.in"); void dijkstra(); void read_file(); struct ii {     int first;     int second;     ii(int a,int b) { first = a,second = b; } }; bool operator<(const ii &a, const ii &b) { return a.first < b.first || (a.first == b.first && a.second < b.second); } vector<ii > m[MAXV]; int main() {     clock_t start = clock(), end;     read_file();     dijkstra();             end = clock();         printf("sure : %f\n",(float)(end-start)/CLOCKS_PER_SEC);         } void read_file() {     in = fopen("girdi.in","r");     fscanf(in,"%d%d",&nvertex,&nedge);     finalv = nvertex;     for (int i=0; i<nedge; ++i) {         int v1,v2,w;         fscanf(in,"%d%d%d",&v1,&v2,&w);         m[v1].push_back(ii(v2,w));         if (UNDIRECTED) m[v2].push_back(ii(v1,w));     } } void dijkstra() {     set<ii > Q;set<ii >::iterator var;     int d[MAXV]; for (int i=0; i<MAXV; i++) d[i] = MAX;     d[startv] = 0;     Q.insert(ii(startv,d[startv]));     while (!Q.empty()) {         ii cur = *Q.begin();         Q.erase(Q.begin());         int v = cur.first;         for (vector<ii >::iterator it = m[v].begin(); it !=  m[v].end(); it++) {             int v2 = it->first, cost = it->second;             if (d[v2] > d[v] + cost) {                 if (d[v2] != MAX) {                     var = Q.find(ii(v2,d[v2]));                     if (var != Q.end()) Q.erase(var);                 }                 d[v2] = d[v] + cost;                 Q.insert(ii(v2,d[v2]));             }         }     }     printf("%d\n",d[finalv]); }```
As far as i know, vector allocates some space and if more elements are being added, it doubles its capacity and copies its element into this doubled vector. If I can specify its capacity beforehand(thus decreasing this slow copying process's effect), the code would run faster, I guess. How can I do this?

Besides of this, what else can you suggest to improve the performance of above code?

• 04-10-2007
ZuK
Quote:

Originally Posted by kolistivra
If I can specify its capacity beforehand(thus decreasing this slow copying process's effect), the code would run faster, I guess. How can I do this?

You can. Use vector::reserve( size_t );
Kurt
• 04-10-2007
laserlight
Quote:

If I can specify its capacity beforehand(thus decreasing this slow copying process's effect), the code would run faster, I guess. How can I do this?
Use the member function reserve() to provide a minimum capacity, or create it with a given size by passing an argument when constructing the vector.
• 04-10-2007
kolistivra
Well, it did indeed increase the performance by about ~%7-8. thanks. do you have any other suggestions?
• 04-10-2007
Daved
Use more descriptive variable names? It is difficult to read the code with all the one and two letter variables.
• 04-10-2007
twomers
>> Well, it did indeed increase the performance [...]

Out of curiosity, how did the performance compare to the C implementation and how does it compare now?
• 04-11-2007
kolistivra
Well, my new tests showed me an unbeliveable difference. in this test, i didn't count the IO(reading vertex and edge information from ~3mb file)

in the best performances:

STL Set version: 0.687 seconds
C hand-coded heap version: 0.031 seconds

the test input consists of 8000 vertices and 200000 edges...

The C version is written by someone else, and I wrote STL. The huge difference may be because I'm not using STL as efficent as I can..
• 04-11-2007
Daved
When I looked earlier it looked like you had an array of vectors and the vectors each had two elements. Was that correct? If you are allowed to post the C version it might be easier to show places to improve, although I admit I still haven't had a chance to spend time wading through the code above.
• 04-11-2007
anon
Could you may-be post the input file? ... Mm, that would be enormous... May-be code that generates the input file?
• 04-11-2007
kolistivra
Well, here we go:

the input generator:

Code:

```#include <cstdio> #include <cstdlib> #include <ctime> using namespace std; const int NVERTEX = 8000; const int NEDGE = 200000; const int MAXWEIGHT = 1000; const bool ISDIRECTED = false; #define FILENAME "girdi.in" bool isused[NVERTEX][NVERTEX]; int main() {     FILE *out = fopen(FILENAME,"w");     srand(time(NULL));     fprintf(out,"%d %d\n",NVERTEX,NEDGE);     for (int i=0; i<NEDGE; ) {         int v1,v2;         v1 = rand() % NVERTEX + 1;         v2 = rand() % NVERTEX + 1;         if (v1 != v2 && !isused[v1][v2]) {             isused[v1][v2] = true;             if (!ISDIRECTED) isused[v2][v1] = true;             int w = rand() % MAXWEIGHT + 1;             fprintf(out,"%d %d %d\n",v1,v2,w);             i++;         }     }     return 0; }```
the STL version:

Code:

```#include <iostream> #include <cstdio> #include <set> #include <cstdlib> #include <ctime> #include <fstream> #include <vector> #include <algorithm> #include <utility> //#define ii pair<int,int> #define MAXV 8002 #define UNDIRECTED 1 #define MAX 0x7fffffff int startv = 1, finalv = 0, nvertex, nedge; using namespace std; FILE *in,*out; //ifstream in("girdi.in"); void dijkstra(); void read_file(); struct ii {     int first;     int second;     ii(int a,int b) { first = a,second = b; } }; bool operator<(const ii &a, const ii &b) { return a.first < b.first || (a.first == b.first && a.second < b.second); } vector<ii > m[MAXV]; int main() {     read_file();     clock_t start = clock(), end;     dijkstra();         end = clock();         printf("sure : %f\n",(float)(end-start)/CLOCKS_PER_SEC); } void read_file() {     in = fopen("girdi.in","r");     fscanf(in,"%d%d",&nvertex,&nedge);     finalv = nvertex;     for (int i=0; i<MAXV; i++) m[i].reserve(100);     for (int i=0; i<nedge; ++i) {         int v1,v2,w;         fscanf(in,"%d%d%d",&v1,&v2,&w);         m[v1].push_back(ii(v2,w));         if (UNDIRECTED) m[v2].push_back(ii(v1,w));     } } void dijkstra() {     set<ii > Q;set<ii >::iterator var;     int d[MAXV]; for (int i=0; i<MAXV; i++) d[i] = MAX;     d[startv] = 0;     Q.insert(ii(startv,d[startv]));     while (!Q.empty()) {         ii cur = *Q.begin();         Q.erase(Q.begin());         int v = cur.first;         for (vector<ii >::iterator it = m[v].begin(); it !=  m[v].end(); it++) {             int v2 = it->first, cost = it->second;             if (d[v2] > d[v] + cost) {                 if (d[v2] != MAX) {                     var = Q.find(ii(v2,d[v2]));                     if (var != Q.end()) Q.erase(var);                 }                 d[v2] = d[v] + cost;                 Q.insert(ii(v2,d[v2]));             }         }     }     printf("%d\n",d[finalv]); }```
and the heap version(this code does not belong to me. http://www.shygypsy.com/tools/ that's where i got it):

Code:

```#include <string.h> #define NN 8005 int graph[NN][NN], adj[NN][NN], deg[NN]; int d[NN], q[NN], inq[NN], prev[NN], qs; #define CLR( x, v ) memset( x, v, sizeof( x ) ) #define BUBL { \     t = q[i]; q[i] = q[j]; q[j] = t; \     t = inq[q[i]]; inq[q[i]] = inq[q[j]]; inq[q[j]] = t; } int dijkstra( int n, int s, int t ) {     CLR( d, 9 ); CLR( inq, -1 ); CLR( prev, -1 );     d[s] = qs = 0;     inq[q[qs++] = s] = 0;     prev[s] = -2;     while( qs )     {         // get the minimum from the q         int u = q[0]; inq[u] = -1;         // bubble down         q[0] = q[--qs];         if( qs ) inq[q[0]] = 0;         for( int i = 0, j = 2*i + 1, t; j < qs; i = j, j = 2*i + 1 )         {             if( j + 1 < qs && d[q[j + 1]] < d[q[j]] ) j++;             if( d[q[j]] >= d[q[i]] ) break;             BUBL;         }         // relax neighbours         for( int k = 0, v = adj[u][k]; k < deg[u]; v = adj[u][++k] )         {             int newd = d[u] + graph[u][v];             if( newd < d[v] )             {                 d[v] = newd;                 prev[v] = u;                 if( inq[v] < 0 ) { inq[q[qs] = v] = qs; qs++; }                 // bubble up                 for( int i = inq[v], j = ( i - 1 )/2, t;                     d[q[i]] < d[q[j]]; i = j, j = ( i - 1 )/2 )                     BUBL;             }         }     }     return d[t]; } //------- TESTING -------- #include <stdio.h> #include <stdlib.h> #include <time.h> int main() {     FILE *in=fopen("girdi.in","r");     int n, m;     while( fscanf(in, " %d %d\n", &n, &m ) == 2 )     {         memset( deg, 0, sizeof( deg ) );         while( m-- )         {             int u, v, w;             fscanf(in, " %d %d %d", &u, &v, &w );             graph[u][v] = graph[v][u] = w;             adj[u][deg[u]++] = v;             adj[v][deg[v]++] = u;         }         clock_t start = clock(), end;         int ans = dijkstra( n, 1, n );         end = clock();         printf("sure : %f\n",(float)(end-start)/CLOCKS_PER_SEC);         printf( "%d\n", ans );     }         //end = clock();         //printf("sure : %f\n",(float)(end-start)/CLOCKS_PER_SEC);     return 0; }```
• 04-11-2007
anon
May-be the speed difference has to do with some compiler options. Did you try an optimized release version? May-be it is possible to turn off range-checking or something?

The C version with all the bubbling (does this mean copying an array forward and backward?) going on doesn't really look a killer at all.

By the way, does your code give the right output? This is most important.
• 04-11-2007
dwks
Code:

`printf("sure : &#37;f\n",(float)(end-start)/CLOCKS_PER_SEC);`
You shouldn't do this. You're not guaranteed to be able to subtract time_t's. Use difftime(): http://www.cplusplus.com/reference/c.../difftime.html

Never mind, I see you didn't write it.  Oh, you did use code like it though. [/edit]
• 04-11-2007
kolistivra
Yes, both give the same and the right result. The bubbling thing is doing heap's job, I guess.

After your post, I compiled with -O3 parameter, but the runtimes didn't change much.(~0.01 seconds maybe)

I just saw your post dwks, I didn't write the C code with hand-coded heap, but the other one and input generator are mine. I will use difftime() from now on, thanks.
• 04-11-2007
anon
I'm not familiar with the algorithm, but are you sure you are not doing extra work here. The Wikipedia article seems to indicate that if you are only interested in the shortest path, you can leave earlier.

Other than that, insert's seem to be expensive, but they can't be that bad, considering that bubbling is expensive too.
• 04-12-2007
kolistivra
I had an error in my STL! The problem was my mistake! now the runtimes are:

STL: 0.047
Heap: 0.031

I inserted the the items in the Set in a wrong way, that's why the runtime difference was huge =)

thanks all
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last