multiple branches in an if test

Discussion in 'C++' started by Hicham Mouline, Aug 4, 2009.

  1. 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,
    Hicham Mouline, Aug 4, 2009
    #1
    1. Advertising

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

    }
    Vladimir Jovic, Aug 4, 2009
    #2
    1. Advertising

  3. On 4 août, 10:00, "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, 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
    Michael Doubez, Aug 4, 2009
    #3
  4. "Hicham Mouline" <> 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/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.


    --
    __Pascal Bourguignon__
    Pascal J. Bourguignon, Aug 4, 2009
    #4
  5. Hicham Mouline

    Ian Collins Guest

    Pascal J. Bourguignon wrote:
    > "Hicham Mouline" <> 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
    Ian Collins, Aug 4, 2009
    #5
  6. Ian Collins <> writes:

    > Pascal J. Bourguignon wrote:
    >> "Hicham Mouline" <> 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__
    Pascal J. Bourguignon, Aug 4, 2009
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John Malek

    Help in optimizing branches

    John Malek, Sep 30, 2003, in forum: C++
    Replies:
    4
    Views:
    436
    Ron Natalie
    Oct 1, 2003
  2. Piet
    Replies:
    1
    Views:
    799
    Josiah Carlson
    Apr 4, 2004
  3. Jeff Newman
    Replies:
    5
    Views:
    435
    James Kanze
    Oct 30, 2008
  4. rembremading
    Replies:
    5
    Views:
    303
    Tim Prince
    Feb 19, 2009
  5. s
    Replies:
    6
    Views:
    348
    Jerry Coffin
    Jan 7, 2010
Loading...

Share This Page