Efficiency
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: Efficiency

  1. #1
    Join Date
    Mar 2010
    Posts
    13

    Efficiency

    I know I can iterate through a vector using:

    for(vector::size_type i = 0; i < vec.size(); i++){
    cout << vec[i];
    }
    (vec is the name of the vector)

    I also know that I can use an iterator to go through the vector. My question is: which one is more efficient?

  2. #2
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,060

    Re: Efficiency

    Probably depends on the compiler.
    Why don't you just give it a try and time the differences?

  3. #3
    Join Date
    Mar 2010
    Posts
    13

    Re: Efficiency

    How do you time in C++? I have only done it in Java.

    Thanks in advance

  4. #4
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,275

    Re: Efficiency

    Quote Originally Posted by dietao234 View Post
    I know I can iterate through a vector using:

    for(vector::size_type i = 0; i < vec.size(); i++){
    cout << vec[i];
    }
    (vec is the name of the vector)

    I also know that I can use an iterator to go through the vector. My question is: which one is more efficient?
    well for starters, if you want efficiency, then using a more static check would already net you some gains:

    Code:
    const int vect_size = vec.size()
    for(vector::size_type i = 0; i < vect_size; i++){
          cout << vec[i];
    }
    Here, you don't have to evaluate vec.size() every time (same thing if you use vec.end()).

    I would say iterators are faster, because *it is a single operation, wereas vec[i] is actally a double operation (it really *(vector_begin+i), where vector_begin is the vector's internal pointer)

    That said, I'm pretty sure all modern processors, can deference a shift address in a single operation ( as in do *(a+i)).

    Not to mention I'm pretty sure that your compiler will probably just optimize both methods to be exactly the same.

    Regardless, benchmarks show that the net gain is so insignificant, you should not even think about it.

    I prefer to use iterators, because "it is the C++ way" whereas indexes "is the C way". At the end of the day, especially with the tools we have today, the most important is to have clear code, simple and maintainable code. Your code should clearly translate what you want to do.

    - If you just want to iterate through elements, use iterators.
    - If you want to go through elements in your vector, and do things relative to their index, use indexes.

  5. #5
    Join Date
    Mar 2010
    Posts
    13

    Re: Efficiency

    Thank you very much.

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,275

    Re: Efficiency

    Quote Originally Posted by dietao234 View Post
    How do you time in C++? I have only done it in Java.

    Thanks in advance
    The simplest way is to use the "std::clock" function from ctime (http://www.cplusplus.com/reference/clibrary/ctime/)

    Keep in mind though that clock_t (typically) represents milliseconds (which is a lot), and that most of the time, clock is only every 8 or so milliseconds.

  7. #7
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,060

    Re: Efficiency

    Under Windows you can use the High Performance Timers to get high precision results.
    See here for an example.
    Note, if you are timing a loop, make sure it loops enough so it runs for a few seconds to get meaningful results.

  8. #8
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,694

    Re: Efficiency

    Quote Originally Posted by dietao234 View Post
    I know I can iterate through a vector using:

    for(vector::size_type i = 0; i < vec.size(); i++){
    cout << vec[i];
    }
    (vec is the name of the vector)

    I also know that I can use an iterator to go through the vector. My question is: which one is more efficient?
    I'd go along with the 'use the method that best fits the problem' idea.

    One of the best ways to improve efficiency is to familiarise yourself with all of the STL's algorithms. They are written in such a way that the compiler can often optimise them much better than your own hand written loops. See Effective STL, Chapter 7, Item 43 'Prefer algorithm calls to hand written loops'

    Your 'for' loop example could easily have been written as...

    Code:
    vector<int> vec;
    
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, ""));
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  9. #9
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,885

    Re: Efficiency

    There's another thing to consider: Output is slow, relatively speaking, either to a file or to a console. Any gains you might get by changing the iteration method could be overwhelmed by the time necessary to do the output.

  10. #10
    Join Date
    May 2009
    Posts
    2,413

    Re: Efficiency

    Quote Originally Posted by dietao234 View Post
    I also know that I can use an iterator to go through the vector. My question is: which one is more efficient?
    In the next C++ standard (coming up soon) there's a for_each command (like in Java). Using for_each probably will be the best combination of clarity and efficiency. In the meantime one can always use Foreach from Boost,

    http://www.boost.org/doc/libs/1_42_0...l/foreach.html

    Also note that sequencial iteration isn't always the fastest option. In times when multicore processors are common different types of concurrent iteration usually is faster. I'm using the Intel TBB package for this but I think also this kind of lightweight multithreading will be better supported in the next C++ standard.

    http://www.threadingbuildingblocks.org/

    This package also offers a fast object allocation replacement.
    Last edited by nuzzle; March 25th, 2010 at 12:38 PM.

  11. #11
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb Re: Efficiency

    Quote Originally Posted by dietao234 View Post
    I know I can iterate through a vector using:

    for(vector::size_type i = 0; i < vec.size(); i++){
    cout << vec[i];
    }
    (vec is the name of the vector)

    I also know that I can use an iterator to go through the vector. My question is: which one is more efficient?
    I am not convinced that the difference would be so significant that it would matter one way or the other. Another option is to study the assembly code yourself (in addition to timing the functions). If you are using visual studio you can view interlaced assembly with the C++ code and see if there is any significant difference in the two functions.

    I did that and the initialization of the two iterators was actually a pretty large chunk of code. However the for loop body was smaller for the one that uses iterators. Overall I didn't see anything that made be believe that I should prefer one method over the other. Here is the example that I compiled.

    Code:
    #include <iostream>
    #include <vector>
    int main()
    {
        const int SIZE(10);
        std::vector<int> theData(SIZE);
        std::generate(theData.begin(), theData.end(), rand);
    
        for(int i = 0; i < SIZE; ++i)
        {
    	std::cout << theData[i];
        }
    
        std::vector<int>::iterator curr(theData.begin());
        std::vector<int>::iterator end(theData.end());
        for( ; curr < end; ++curr)
        {
    	std::cout << *curr;
        }
    
        std::cout << std::endl;
        
    }
    Last edited by kempofighter; March 25th, 2010 at 01:28 PM. Reason: added example

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center