mardi 27 octobre 2015

Interval branching

A project (C++11) I am working on involves a block of code that will be run somewhere in the trillions of times. I have an integer parameter B in [1,N] and points 1 = b1 < b2 < ... < bk = N where the code executes a different small block of code depending on which interval [bi, b(i+1)) B lies in. The bi's are fixed throughout the execution, B's value is the only thing changing.

The naive thing to do is to write a bunch of if and else if statements, which at worst case involves k comparisons. However one can do this in constant time: construct a vector myGotos of size N and on each interval [bi, b(i+1)) store the location of the corresponding code block. Then you just do goto myGotos[B].

The solution above seems to me like it would be on average quicker, but the code would be quite ugly. I was wondering if there is a better way to do this.

Aucun commentaire:

Enregistrer un commentaire