multiple branches in an if test

[Hicham Mouline]

Hello,

I have code that resembles:

double Get(...) {

double var1;
double bound1.... boundN; // N is of the order of 7/8

double output;
if (var1< bound1)
output = ...;
else if (var1< bound2)
output = ...;
....
else if (var1< boundN)
output = ...;
else
output = ...;

return output;

}


is there a more efficient way of writing this?
rds,

 

[Vladimir Jovic]

Hello,

I have code that resembles:

double Get(...) {

double var1;
double bound1.... boundN; // N is of the order of 7/8

double output;
if (var1< bound1)
output = ...;
else if (var1< bound2)
output = ...;
...
else if (var1< boundN)
output = ...;
else
output = ...;

return output;

}


is there a more efficient way of writing this?

Yes. Here it is:

double Get(...) {

double var1;
double bound1.... boundN; // N is of the order of 7/8

double output = ...;
if (var1< bound1)
output = ...;
else if (var1< bound2)
output = ...;
....
else if (var1< boundN)
output = ...;

return output;

}

 

[Michael Doubez]

Hello,

I have code that resembles:

double Get(...) {

double var1;
double bound1.... boundN;  // N is of the order of 7/8

double output;
if (var1< bound1)
  output = ...;
else if (var1< bound2)
  output = ...;
...
else if (var1< boundN)
   output = ...;
else
   output = ...;

return output;

}

is there a more efficient way of writing this?

Yes, stores yours bounds in a array and use std::lower_bound to
identify the bound it belongs to and act on it.
Example:
double bounds[]={0.0,0.1,0.4,...1.0};
double* const bounds_begin = bounds;
double* const bounds_end = bounds + sizeof(bounds)/sizeof(bounds
[0]);

double* const it = std::lower_bound(bounds_begin,bounds_end,var1);
size_t index = it - bounds_begin ;

 

[Pascal J. Bourguignon]

Hello,

I have code that resembles:

double Get(...) {

double var1;
double bound1.... boundN; // N is of the order of 7/8

double output;
if (var1< bound1)
output = ...;
else if (var1< bound2)
output = ...;
...
else if (var1< boundN)
output = ...;
else
output = ...;

return output;

}


is there a more efficient way of writing this?

If N is really big and the bounds don't change, and you have to test
several times, Michael's solution could be a good one.
But there is quite an over head in building the vector...

The problem is that writting a discriminating tree you will be able to
determine the output in log2(N) cmp+jlt, while allocating the vector,
copying the bounds there, will take a lot of instructions in O(N),
before you start searching (which will be O(log2(N)) but with bigger
constants than the discriminating tree of ifs...

So:


if(var1<bound(N/2)){
if(var1<bound(N/4)){
if(var1<bound(N/8)){

}else{

}
}else{
if(var1<bound(N/4+N/8)){

}else{

}
}
}else{
if(var1<bound(N/2+N/4)){
if(var1<bound(N/2+N/8)){

}else{

}
}else{
if(var1<bound(N/2+N/4+N/8)){

}else{

}
}
}



That is, in the case where N=8:

if(var1<bound4){
if(var1<bound2){
if(var1<bound1){

}else{

}
}else{
if(var1<bound3){

}else{

}
}
}else{
if(var1<bound6){
if(var1<bound5){

}else{

}
}else{
if(var1<bound(7)){

}else{

}
}
}


It is easy to write a little emacs function to generate such a
discriminating if tree for any value of N.

 

[Ian Collins]

If N is really big and the bounds don't change, and you have to test
several times, Michael's solution could be a good one.
But there is quite an over head in building the vector...

He didn't build a vector, he used an array.

 

[Pascal J. Bourguignon]

He didn't build a vector, he used an array.

Indeed, I didn't read his post carefully enough and I've been misled
by std::lower_bound, sorry.