Programming Forums > Application Development > C++

Sane · Apr 16th, 2008, 8:42 PM

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.

(Toggle Plain Text)

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

/* 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:

(Toggle Plain Text)

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:

(Toggle Plain Text)

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, 9:28 AM

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:

(Toggle Plain Text)

           s = tree[bfs.front()].size();
            for(j=0; j<s; j++) {
                name = tree[bfs.front()][j];
                ...
            }

you could use a cached reference:

(Toggle Plain Text)

           vector<string> &coAuthors = tree[bfs.front()];
           s = coAuthors.size();
            for(j=0; j<s; j++) {
                name = coAuthors[j];
                ...
            }

Sane · Apr 17th, 2008, 1:31 PM

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, 5:08 PM

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.

Apr 17th, 2008, 9:28 AM	#2
The Dark Expert Programmer Join Date: Jun 2005 Posts: 852 Rep Power: 4	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: (Toggle Plain Text) s = tree[bfs.front()].size(); for(j=0; j<s; j++) { name = tree[bfs.front()][j]; ... } s = tree[bfs.front()].size(); for(j=0; j<s; j++) { name = tree[bfs.front()][j]; ... } you could use a cached reference: (Toggle Plain Text) vector<string> &coAuthors = tree[bfs.front()]; s = coAuthors.size(); for(j=0; j<s; j++) { name = coAuthors[j]; ... } vector<string> &coAuthors = tree[bfs.front()]; s = coAuthors.size(); for(j=0; j<s; j++) { name = coAuthors[j]; ... }

Apr 17th, 2008, 1:31 PM	#3
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,884 Rep Power: 5	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). __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Apr 17th, 2008, 5:08 PM	#4
The Dark Expert Programmer Join Date: Jun 2005 Posts: 852 Rep Power: 4	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.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Recursive to Procedural Algorithm Conversion	Jessehk	C++	5	Oct 31st, 2007 10:18 PM
Programming Contest Site - Feedback Appreciated	Shane	Coder's Corner Lounge	0	Jan 22nd, 2007 5:02 AM
SpcFileWipe algorithm in Secure Programming Cookbook not working	c0ldshadow	C++	1	Aug 7th, 2005 7:40 PM
rsa encrption decrption algorithm	justdoit	C	2	May 4th, 2005 9:16 AM
Help with some algorithm questions	mapster123	Assembly	3	Feb 14th, 2005 4:55 AM

Apr 16th, 2008, 8:42 PM	#1
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,884 Rep Power: 5	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. (Toggle Plain Text) /* 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; } / 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: (Toggle Plain Text) 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. 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*: (Toggle Plain Text) 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 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 __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Feedback On Algorithm With C++