CODEWITHSUNDEEP
c++loops
trikker
trikker

Reputation: 2709

Speed comparison of 2 loop styles

I'm reading about STL algorithms and the book pointed out that algorithms like find use a while loop rather than a for loop because it is minimal, efficient, and uses one less variable. I decided to do some testing and the results didn't really match up.

The forfind consistently performed better than the whilefind. At first I simply tested by pushing 10000 ints back into a vector, and then using find to get a single value from it and return it to the iterator. I timed it and output that time.

Then I decided to change it so that the forfind and whilefind functions were used multiple times (in this case 10000 times). However, the for loop find still came up with better performance than the while find. Can anyone explain this? Here is the code. 

#include "std_lib_facilities.h"
#include<ctime>

template<class ln, class T>
ln whilefind(ln first, ln last, const T& val)
{
    while (first!=last && *first!=val) ++first;
    return first;
}

template<class ln, class T>
ln forfind(ln first, ln last, const T& val)
{
    for (ln p = first; p!=last; ++p)
        if(*p == val) return p;
    return last;
}

int main()
{
    vector<int> numbers;
    vector<int>::iterator whiletest;
    vector<int>::iterator fortest;
    for (int n = 0; n < 10000; ++n)
        numbers.push_back(n);

    clock_t while1 = clock();   // start
    for (int i = 0; i < 10000; ++i)
        whiletest = whilefind(numbers.begin(), numbers.end(), i);
    clock_t while2 = clock();   // stop

    clock_t for1 = clock(); // start
    for (int i = 0; i < 10000; ++i)
        fortest = forfind(numbers.begin(), numbers.end(), i);
    clock_t for2 = clock(); // stop

    cout << "While loop: " << double(while2-while1)/CLOCKS_PER_SEC << " seconds.\n";
    cout << "For loop: " << double(for2-for1)/CLOCKS_PER_SEC << " seconds.\n";
}

The while loop consistently reports taking around .78 seconds and the for loop reports .67 seconds.

Upvotes: 3

Views: 675

Answers (1)

R&#252;diger Hanke
R&#252;diger Hanke

Reputation: 6255

if(*p = val) return p;

That should be a ==. So forfind will only go through the entire vector for the first value, 0, and return immediately for numbers 1-9999.

Upvotes: 11

Related Questions