Difference in iteration

Question

I was trying to solve problem D from this competition (it's not really important to read the task) and I noted that these two codes that make the same thing are slightly different in time of execution:

map < string, vector <string> > G;

// Version 1
bool dfs(string s, string t) {
    if( s == t ) return true;

    for(int i = 0; i < int(G[s].size()); i++) {
        if( dfs( G[s][i], t ) ) return true;
    }
    return false;
}
// Version 2
bool dfs(string s, string t) {
    if( s == t ) return true;

    for(auto r: G[s]) {
        if( dfs( r, t ) ) return true;
    }
    return false;
}

In particular Version 1 gets TLE in evaluation, instead Version 2 pass without any problem. According to this question it's strange that Version 1 is slower, and testing on my PC with the largest testcase I get same time of execution... Can you help me?

Version 1 performs a lookup `G[s]` twice per iteration. Version 2 only does it once, total. — Igor Tandetnik, Aug 20 '18 at 20:12

score 1 · Accepted Answer · answered Aug 20 '18 at 20:15

1

In version one you have int(G[s].size()) In the for loop, which calls the size function on the variable for every iteration of the loop. Try creating a variable before the for loop that evaluates that size function once, and use it for your comparison in the loop. This Will be faster than the version 1 you currently have.

answered Aug 20 '18 at 20:15

DJHenjin

87
4

Thanks! I've tried your suggestion and it got Accepted, but it is still slower near 0.2 seconds than Version 2 – L.A. Aug 20 '18 at 20:24
Yeah, version 2 iterates over the array rather than indexing into it, which from what I recall is slightly faster in certain cases. But at least you know why the version 1 failed. – DJHenjin Aug 20 '18 at 20:26

Difference in iteration

1 Answers1