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?

Thanks in advance

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

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.

Well, it did indeed increase the performance by about ~%7-8. thanks. do you have any other suggestions?

Use more descriptive variable names? It is difficult to read the code with all the one and two letter variables.

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

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

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.

Could you may-be post the input file? ... Mm, that would be enormous... May-be code that generates the input file?

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

---

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.

Code:

---

printf("sure : %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. [edit] Oh, you did use code like it though. [/edit]

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.

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.

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

Why not post your corrected code? That way we all can learn too.

the main problem of mine was that, i put the items in the set, and the way i put sorted the items according to their node number, instead of the cost. some little modifications corrected the code. here is the corrected 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() {

    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(d[startv],startv));

    while (!Q.empty()) {
        ii cur = *Q.begin();
        Q.erase(Q.begin());
        int v = cur.second;
        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(d[v2],v2));
                    if (var != Q.end()) Q.erase(var);
                }
                d[v2] = d[v] + cost;
                Q.insert(ii(d[v2],v2));
            }
        }
    }
    printf("%d\n",d[nvertex]);
}

---

the bolds fixed the problem.