Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   C++ (http://www.programmingforums.org/forum15.html)
-   -   Feedback On Algorithm With C++ (http://www.programmingforums.org/showthread.php?t=15638)

Sane Apr 16th, 2008 9:42 PM
Feedback On Algorithm With C++
 
This is my first time trying to use the features of C++ to write an algorithm. I program in C. But I came across a question that required hashing, and thought it would be smartest to use C++'s associative containers.

The problem itself is pretty simple. You just need to compute the distance of every node from one node in particular. I chose to implement a BFS. So I gave myself a crash course on hash maps, vectors, and queues.

This is the question in case you're curious:
http://www.programming-challenges.co...06&format=html

Now, could any one give me some constructive feedback on my code? I want succinct, simple, and stable code that can get all of the following jobs done quickly. So are these aspects of the code optimal?
  • My method of parsing
  • My method of constructing/representing the tree
  • My BFS implementation

Mine took 2 seconds to solve all of the input files. Which is fairly decent, but I'd like to know if I'm using some slow bits of code, or if there are ways to shorten what I have.

Any feedback pertaining to my use of C++'s features in general would also be appreciated. I'm a C programmer, so I'm not aiming to "learn" C++, but I'd be more than happy to learn whether or not I'm using the features of C++ effectively and correctly.

Thanks.

Note: To test the program, it's easiest to redirect the input/output to a file by uncommented the two lines at the top of main, and using the input file at the bottom.

:
/* Programming Challenge #110206 - Erdos Numbers
  http://www.programming-challenges.com/
*/

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>

using namespace std;
const string start = "Erdos, P.";

int main() {
    //freopen("erdos.txt", "rt", stdin);
    //freopen("erdos.out", "wt", stdout);
   
    vector<string> names;
    map< string, vector<string> > tree;
    map< string, int > depths;
    queue<string> bfs;
   
    string buff, name;
    int t, n, p;
    int h, i, j, k, s, depth;
   
    cin >> t;
    for(h=0; h<t; h++) {
        cin >> p >> n;
        cin.get();
       
        for(i=0; i<p; i++) {
            getline(cin, buff);

            j = 0;
            while( ( k = buff.find(".,", j) ) != string::npos ) {
                name.assign(buff, j, k-j+1);
                names.push_back(name);
                j = k+3;
            }
            name.assign(buff, j, buff.find(".:")-j+1);
            names.push_back(name);
           
            s = names.size();
            for(j=0; j<s; j++) for(k=0; k<s; k++) if(j!=k)
                        tree[names[j]].push_back(names[k]);
            names.clear();
        }
       
        depths[start] = 1;
        bfs.push(start);
       
        while(!bfs.empty()) {
            s = tree[bfs.front()].size();
            for(j=0; j<s; j++) {
                name = tree[bfs.front()][j];
                if(!depths[name]) {
                    depths[name] = depths[bfs.front()] + 1;
                    bfs.push(name);
                }
            }
            bfs.pop();
        }
       
        cout << "Scenario " << h+1 << endl;
        for(i=0; i<n; i++) {
            getline(cin, buff);
           
            depth = depths[buff];
            cout << buff << " ";
            if(depth == 0) cout << "infinity";
            else cout << depth-1;
            cout << endl;
        }
       
        depths.clear();
        tree.clear();
    }
   
    return 0;
}

Example Input:

:
6
4 3
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First order derivatives
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
Smitty, Q.
Hsueh, Z.
Chen, X.
4 3
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First order derivatives
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Erdos, P.
8 8
4, 5.6., n, m.o., X, Y.Z.: ---
A, B.C., Erdos, P.: ---
A, B.C., a, b.c.: ---
X, Y.Z., x, y.z.: ---
1, 2.3., 4, 5.6.: ---
a, b.c., X, Y.Z.: ---
N, M.O., n, m.o.: ---
1, 2.3., Erdos, P.: ---
1, 2.3.
4, 5.6.
a, b.c.
A, B.C.
n, m.o.
N, M.O.
x, y.z.
X, Y.Z.
7 8
4, 5.6., n, m.o., X, Y.Z.: ---
A, B.C., a, b.c.: ---
X, Y.Z., x, y.z.: ---
1, 2.3., 4, 5.6.: ---
a, b.c., X, Y.Z.: ---
N, M.O., n, m.o.: ---
1, 2.3., Erdos, P.: ---
1, 2.3.
4, 5.6.
a, b.c.
A, B.C.
n, m.o.
N, M.O.
x, y.z.
X, Y.Z.
1 2
Smith, M.N.: ---
Erdos, P.
Smith, M.N.
2 3
Aaron, Voelker., C, Plus Plus.: ---
C, Plus Plus., Aaron, Voelker.: ---
C, Plus Plus.
Aaron, Voelker.
Smith, M.N.

Example Output:

:
Scenario 1
Smitty, Q. infinity
Hsueh, Z. infinity
Chen, X. 2
Scenario 2
Smith, M.N. 1
Hsueh, Z. infinity
Erdos, P. 0
Scenario 3
1, 2.3. 1
4, 5.6. 2
a, b.c. 2
A, B.C. 1
n, m.o. 3
N, M.O. 4
x, y.z. 4
X, Y.Z. 3
Scenario 4
1, 2.3. 1
4, 5.6. 2
a, b.c. 4
A, B.C. 5
n, m.o. 3
N, M.O. 4
x, y.z. 4
X, Y.Z. 3
Scenario 5
Erdos, P. 0
Smith, M.N. infinity
Scenario 6
C, Plus Plus. infinity
Aaron, Voelker. infinity
Smith, M.N. infinity

The Dark Apr 17th, 2008 10:28 AM
Re: Feedback On Algorithm With C++
 
A few things to consider:

The vector<string> in the tree map may end up with the same name in it several times (e.g. if two authors publish together more than once). It might be better to use a set<string> instead, although the overhead of the set might end up costing more than the data duplication.

Its not actually a problem, but I would normally declare the temporary variables local to the loop (such as names, in the paper reading loop). Again, this may end up begin less efficient as the variable has to be recreated each time, rather than just being cleared. It does prevent you accidentally using it later on though.

Looking up entries in a map can be a little costly, so it might be worth caching the result of a lookup. e.g. since you know tree and bfs.front() don't change in this loop:
:
          s = tree[bfs.front()].size();
            for(j=0; j<s; j++) {
                name = tree[bfs.front()][j];
                ...
            }
you could use a cached reference:
:
          vector<string> &coAuthors = tree[bfs.front()];
          s = coAuthors.size();
            for(j=0; j<s; j++) {
                name = coAuthors[j];
                ...
            }

Sane Apr 17th, 2008 2:31 PM
Re: Feedback On Algorithm With C++
 
I appreciate the reply.

I don't think switching from a map of vectors to a map of maps would help.

Data repetition would be less harmful, wouldn't it? The map needs to check for collisions during every single insertion. But data repetition only results in an extra lookup for every repeated vertex, into the map called "depths" inside the for loop (since same verticies are not visited twice in a BFS).

The Dark Apr 17th, 2008 6:08 PM
Re: Feedback On Algorithm With C++
 
It probably won't help, given the size of the input data. If you were talking millions of names, I think it would be faster though.
Note that vectors have to maintain their data in a contiguous block, so every time a vector has to grow (i.e gets too big for its capacity), it has to reallocate a larger block and then copy the whole vector over. This can be very costly, when you are talking about large vectors. I sometimes use the deque class instead, which doesn't keep everything in one block, so adding to the end (or the start) of the deque is fast. Again, it won't impact this problem, but it can cause problems with large data sets.


All times are GMT -5. The time now is 4:17 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC