int main (int argc, char * const argv[]) {
std::vector<int> myvec;
for (int i = 0; i < 100000000; ++i) {
myvec.push_back(i);
}
typedef std::vector<int>::iterator IT_int;
clock_t start,end;
start = std::clock();
for (IT_int it = myvec.begin(); it != myvec.end(); ++it) {
*it += 1;
}
end = std::clock();
std::cout << end - start << std::endl;
start = std::clock();
for (int i = 0; i < myvec.size(); ++i) {
myvec[i] += 1;
}
end = std::clock();
std::cout << end - start << std::endl;
return 0;
}
output:
1st try:
2858863
1135227
2nd try:
2461235
1139648
3rd try:
2618116
1133062
compiled with XCode 3.2.5, GCC 4.2
Name:
Anonymous2012-04-11 18:05
Just use an array.
Name:
Anonymous2012-04-11 18:11
>>1
Strictly speaking you should use iterators. It has the advantage of just being a pointer, but that said, I think C++ ideologies like these are just plain silly.
>>5
With the vector, you're potentially doing 100,000 reallocs and bounds checks, but with the array, you're just storing at an offset to a register.
Name:
Anonymous2012-04-12 0:16
>>6
push_back has order one amortized time according to the best resource to seeples on the internat http://www.cplusplus.com but I agree that it should be avoided in favor of performing a single call to resize and then modification by the [] operator.
>>5
one way to implement a vector iterator would be a direct pointer to a place in the vector's array. And then the tests, it == vec.end() can be performed by comparing the value of the pointer to the address just after the end of the used part of the array. If you were to use indexing on a C array, the compiler can handle optimizing away the index if necessary.
>>9
That's really sad. There's no reason for vector iteration to be so much more inefficient than c array iteration. Although, to be fair, >>5 should do a test with a non statically allocated array. And >>5 should check the assembly output to see if the compiler is just culling out the c array iteration code, because the compiler might know that the code doesn't do anything meaningful or used later, whereas with the vector it might not be able to figure that out.
should be
for(std::vector<int>::iterator i = myvec.begin(), e = myvec.end(); i < e; i++) {
but it doesn't matter for the other one. This will probably make a difference even in release mode since myvec.end() isn't guaranteed to be invariant between calls (mutation by other threads, &c)
>>17 is just screaming please give me some toilets to scrub!
Name:
Anonymous2012-04-12 6:46
>>15
Too bad it has GC. Haskell is not the best. GC is shit.
Name:
Anonymous2012-04-12 7:24
would someone bugger me?
Name:
Anonymous2012-04-12 8:25
Wow. I'm surprised that there is really difference in speed between these versions. I thought optimizers in -O3 already could optimize out differences. Alas.
Well, anyway I prefer iterator approach as in debug mode it checks ranges.
Name:
Anonymous2012-04-12 8:45
Well, anyway I prefer index approach as in /prog/ mode it checks dubs.
Name:
Anonymous2012-04-12 12:58
What kind of shitty compilers are you using to get results like that?
With gcc traversing a vector with an iterator or an unsigned int as well as traversing an array are all equally fast. Iterating with signed int is about 20% slower which I guess is because gcc doesn't change the < comparison to != then, and equality comparisons are often a bit faster.
Name:
Anonymous2012-04-12 13:42
>>23 equality comparisons are often a bit faster.
Stop it, I'm crying.
>>29
that can actually be O(log(n)) where n is the number of bits, by using a balanced tree of or gates. And the same applies to x == y operation, except you would use and gates.
Name:
Anonymous2012-04-12 22:54
>>35 I'm gonna pursue my BA in toilet scrubbing at anywhere that will hire me forever.
Total of elements: 200000
Heap array:
using index: 0.001267s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
using std::for_each: 0.000275s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
Stack array:
using index: 0.000295s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
using std::for_each: 0.000270s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
using BOOST_FOREACH: 0.000995s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (n/a%)
Vector:
using index: 0.000296s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
using iterators: 0.000549s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
using std::for_each: 0.000533s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
using BOOST_FOREACH: 0.000582s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
List:
using iterators: 0.004329s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
using std::for_each: 0.009227s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (169.1%)
using BOOST_FOREACH: 0.007076s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
int main() {
std::cout << "Total of elements: " << maxsz << std::endl;
boost::random::mt19937 rng;
{
unsigned int* harr = new unsigned int[maxsz];
for (int i = 0; i < maxsz; ++i) {
harr[i] = rng();
}
std::cout << "Heap array:\n using index: ";
{
boost::timer::auto_cpu_timer t;
for (int i = 0; i < maxsz; ++i) {
harr[i] /= 100;
}
}
std::cout << " using std::for_each: ";
{
boost::timer::auto_cpu_timer t;
std::for_each(harr, harr+maxsz, X = X / 100);
}
std::cout << std::endl;
delete[] harr;
}
{
unsigned int arr[maxsz];
for (int i = 0; i < maxsz; ++i) {
arr[i] = rng();
}
std::cout << "Stack array:\n using index: ";
{
boost::timer::auto_cpu_timer t;
for (int i = 0; i < maxsz; ++i) {
arr[i] /= 100;
}
}
std::cout << " using std::for_each: ";
{
boost::timer::auto_cpu_timer t;
std::for_each(arr, arr+maxsz, X = X / 100);
}
std::cout << " using BOOST_FOREACH: ";
{
boost::timer::auto_cpu_timer t;
BOOST_FOREACH(unsigned int& i, arr) {
i /= 100;
}
}
std::cout << std::endl;
}
{
std::vector<unsigned int> vec(maxsz);
for (int i = 0; i < maxsz; ++i) {
vec.push_back(rng());
}
std::cout << "Vector:\n using index: ";
{
boost::timer::auto_cpu_timer t;
for (int i = 0; i < maxsz; ++i) {
vec[i] /= 100;
}
}
std::cout << " using iterators: ";
{
boost::timer::auto_cpu_timer t;
const std::vector<unsigned int>::iterator end = vec.end();
for (std::vector<unsigned int>::iterator it = vec.begin(); it != end; ++it) {
*it /= 100;
}
}
std::cout << " using std::for_each: ";
{
boost::timer::auto_cpu_timer t;
std::for_each(vec.begin(), vec.end(), X = X / 100);
}
std::cout << " using BOOST_FOREACH: ";
{
boost::timer::auto_cpu_timer t;
BOOST_FOREACH(unsigned int& i, vec) {
i /= 100;
}
}
std::cout <<std::endl;
}
{
std::list<unsigned int> list(maxsz);
for (int i = 0; i < maxsz; ++i) {
list.push_back(rng());
}
std::cout << "List:\n using iterators: ";
{
boost::timer::auto_cpu_timer t;
const std::list<unsigned int>::iterator end = list.end();
for (std::list<unsigned int>::iterator it = list.begin(); it != end; ++it) {
*it /= 100;
}
}
std::cout << " using std::for_each: ";
{
boost::timer::auto_cpu_timer t;
std::for_each(list.begin(), list.end(), X = X / 100);
}
std::cout << " using BOOST_FOREACH: ";
{
boost::timer::auto_cpu_timer t;
BOOST_FOREACH(unsigned int& i, list) {
i /= 100;
}
}
std::cout << std::endl;
}
return 0;
}
Name:
Anonymous2012-04-13 1:07
Money are dopamine of the hive mind, while central banks, like IMF, are the dopamine emitters, which are controlled mostly by the Jews. Kill all the Jews and you'll kill the globalization Hydra. There should be no mercy to the Jews, because they are the neurons of our Enemy.
Remember: it's these dollars, the Jews print, make your life bad, so every Jew you kill will make your country better. Help your nation's economic and culture - kill Jewish internationalists.
Name:
Anonymous2012-04-13 2:40
>>24 >>25
Why is that wrong? On x86 gcc uses cmp to implement < and test-instruction to implement !=. What else do think causes the difference in speed if the only difference in generated loops is that one uses cmp and one uses test?
Equality could be tested for with n XOR gates and a dumb population count of OR gates (lg n)-1 levels deep. This gives you a time complexity of (lg n) to do a comparison.
Less than could be tested for by doing a simple subtraction and looking at the sign bit. How would you do this? Put one number through a line of NOT gates, then feed it into a CPA (Carry Propagating Adder) with a '1' set on the carry input. The CPA used will be, with almost 100% certainty, be one with a prefix network, giving a time complexity of (lg n).
So both of these operations are equally fast, but here's the fun part:
CPUs are CLOCKED DIGITAL CIRCUITS and these operations, sometimes even including multiplication, are all done in ONE CLOCK CYCLE