CODEWITHSUNDEEP
c++c
user1669844
user1669844

Reputation: 763

what is the most efficient way to determine if any one of the number from given set of numbers is zero?

In my project, I have to perform certain operations only if one or more numbers from the particular set are zero. I want this check to be the efficient one and don't want to perform multiple AND operations.

e.g. if there are 10 elements I need to perform following operation before getting the final answer

var_and= A1 && A2;
var_and=var_and && A3;..
.
.
var_and=var_and && A10;

This is how assembly code will look like(?).

Is there any better solution to this?

Upvotes: 0

Views: 162

Answers (2)

Ap31
Ap31

Reputation: 3324

The most efficient way to do that is most definetly 

std::any_of(v.begin(),v.end(),[](int x) { return x==0; });

Some compilers would even be able to vectorize it, so it's going to be hard to optimize it any further.

But the most important thing here is that you're saving your time that could be wasted on counting assembler instructions (which hardly even makes sense) and the time of potential readers of your code.

After you've finished your whole program, you can profile it and determine your bottlenecks. In the unlikely case this line is one of them, you'll have to figure out what exactly is going on - cache misses, IO, wrong branch prediction - and fix that specific problem.

Also another close option is 

std::find(v.begin(),v.end(),0)!=v.end();

Upvotes: 4

fearless_fool
fearless_fool

Reputation: 35229

The first thing to point out is that "most efficient" is in the eye of the beholder. Do you mean fastest? Smallest code space? Easiest to maintain?

If your compiler and hardware supports vector operations, I'd say take the product of the set and if it equals zero, you know that at least one element is zero.

So perhaps I'm missing something -- the following seems too simple -- but does this do what you want?

bool has_a_zero(int *values, int n) {
  while (n--) {
    if (!*values++) return true;
  }
  return false;
}

If that's not fast enough, you can do tricks like unrolling the loop to do chunks of N tests at a time (e.g. Duff's Device). Or if your set of values has an out-of-band value, you can use that to terminate the loop rather than manipulate extra registers.

But, as it is, you'd need to explain a bit more what you mean by "most efficient".

Upvotes: 2

Related Questions