Velocity Reviews > C++ > multiple branches in an if test

# multiple branches in an if test

Hicham Mouline
Guest
Posts: n/a

 08-04-2009
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,

Guest
Posts: n/a

 08-04-2009
Hicham Mouline wrote:
> 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
Guest
Posts: n/a

 08-04-2009
On 4 août, 10:00, "Hicham Mouline" <(E-Mail Removed)> wrote:
> 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 ;

--
Michael

Pascal J. Bourguignon
Guest
Posts: n/a

 08-04-2009
"Hicham Mouline" <(E-Mail Removed)> writes:

> 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/){

}else{

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

}else{

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

}else{

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

}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.

--
__Pascal Bourguignon__

Ian Collins
Guest
Posts: n/a

 08-04-2009
Pascal J. Bourguignon wrote:
> "Hicham Mouline" <(E-Mail Removed)> writes:
>
>> 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...

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

--
Ian Collins

Pascal J. Bourguignon
Guest
Posts: n/a

 08-04-2009
Ian Collins <(E-Mail Removed)> writes:

> Pascal J. Bourguignon wrote:
>> "Hicham Mouline" <(E-Mail Removed)> writes:
>>
>>> 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...

>
> 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.

--
__Pascal Bourguignon__