-
March 24th, 2010, 08:20 AM
#1
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?
-
March 24th, 2010, 08:38 AM
#2
Re: Efficiency
Probably depends on the compiler.
Why don't you just give it a try and time the differences?
-
March 24th, 2010, 08:44 AM
#3
Re: Efficiency
How do you time in C++? I have only done it in Java.
Thanks in advance
-
March 24th, 2010, 08:46 AM
#4
Re: Efficiency
Originally Posted by dietao234
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.
-
March 24th, 2010, 08:47 AM
#5
-
March 24th, 2010, 08:50 AM
#6
Re: Efficiency
Originally Posted by dietao234
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.
-
March 25th, 2010, 02:57 AM
#7
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.
-
March 25th, 2010, 04:10 AM
#8
Re: Efficiency
Originally Posted by dietao234
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
-
March 25th, 2010, 08:51 AM
#9
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.
-
March 25th, 2010, 12:36 PM
#10
Re: Efficiency
Originally Posted by dietao234
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.
-
March 25th, 2010, 01:26 PM
#11
Re: Efficiency
Originally Posted by dietao234
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|