Thread: Array of Vectors amd other STL questions

  1. #1
    Registered User
    Join Date
    Jul 2006
    Posts
    25

    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

  2. #2
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by kolistivra View Post
    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

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Jul 2006
    Posts
    25
    Well, it did indeed increase the performance by about ~%7-8. thanks. do you have any other suggestions?

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Use more descriptive variable names? It is difficult to read the code with all the one and two letter variables.

  6. #6
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    >> 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?

  7. #7
    Registered User
    Join Date
    Jul 2006
    Posts
    25
    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..

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Could you may-be post the input file? ... Mm, that would be enormous... May-be code that generates the input file?

  10. #10
    Registered User
    Join Date
    Jul 2006
    Posts
    25
    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;
    }

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.

  12. #12
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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. [edit] Oh, you did use code like it though. [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  13. #13
    Registered User
    Join Date
    Jul 2006
    Posts
    25
    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.
    Last edited by kolistivra; 04-11-2007 at 04:24 PM.

  14. #14
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.

  15. #15
    Registered User
    Join Date
    Jul 2006
    Posts
    25
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 09:51 AM
  2. dynamic array of vectors
    By axr0284 in forum C++ Programming
    Replies: 8
    Last Post: 02-26-2006, 12:01 AM
  3. 2 Array questions
    By f97tosc in forum C Programming
    Replies: 2
    Last Post: 03-23-2003, 06:22 PM
  4. Replies: 72
    Last Post: 11-25-2002, 05:55 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM