Efficiency question

[oLC9216C]

Hi,

just want to know which one will be faster,

vector<int> temp;
temp[n]=temp[n+1];

or

vector<int> temp;
if(temp[n]!=0)
temp[n]=temp[n+1];

I have moving a lot of data, like 5000, and I just want to move the data not equals to 0, but it doesn't matter i move the one equals to 0 or not.

move everything no matter what the value is or make a if statement will be faster?

[Peter87]

My guess is that the first one will run faster.

[benbalach]

My advice is to time it. In programming speculating about what code should do is wrong, until you try it hands on you have no way of knowing. Time the first example 3 times, get the average time. And do the same thing for the second example. That's how you will for sure know which one is faster.

[giblit]

I don't think something that small you should even be bothered with efficiency. Anyways, depending on how many 0's there are the second method could be slower.

[MatthewRock]

Instead of timing something - which can give you false results, if did wrong - you can check assembly code created by each code. :)

Cheers!

[Smac89]

If efficiency is really a factor, then you can decide to store only the indexes containing a value in a symbol table such as std::map. Then your key, value pair is made up of an index and the value at that index so std::pair<int, int>.

Note that the use of std::unordered_map will not work in this case since you want the indices to be in their natural order, which std::unordered_map does not guarantee

http://www.cplusplus.com/reference/map/map/map/
http://www.cplusplus.com/reference/unordered_map/unordered_map/unordered_map/

[JLBorges]

> move everything no matter what the value is or make a if statement will be faster?

std::copy() would do it in the fastest possible way.

In practice, implementations of std::copy avoid multiple assignments and use bulk copy functions such as std::memmove if the value type is TriviallyCopyable

When copying overlapping ranges, std::copy is appropriate when copying to the left (beginning of the destination range is outside the source range) while std::copy_backward is appropriate when copying to the right (end of the destination range is outside the source range).
http://en.cppreference.com/w/cpp/algorithm/copy

std::vector<int> seq(5000) ;

// ...

// copy/move left
std::copy( std::begin(seq)+1, std::end(seq), std::begin(seq) ) ;
std::move( std::begin(seq)+1, std::end(seq), std::begin(seq) ) ;

// copy/move right
std::copy_backward( std::begin(seq), std::end(seq)-1, std::end(seq) ) ;
std::move_backward( std::begin(seq), std::end(seq)-1, std::end(seq) ) ;