"Bill Woessner" <wo******@cs.umd.edu> wrote:

Suppose I have a mathematical step function like this:

f(x) = { 0, x <= x_1

1, x_1 <= x < x2

...

n, x >= x_n }

What's an efficient way to evaluate this in C++?

If the x_ values are reasonably spread out and are not too sparse (eg. 1.5,

2.8, 5.7, 8.9 ...), then one way might be to create an array that can be

used to map the integer part of (x times a constant K) (where K is the

minimum difference between any pair of x_ values; see below if this value is

small) to a struct like:

struct StepData

{

int value;

double cutOffPoint;

};

Then you can have something like:

StepData stepData[] = { ... };

const double minXValue = ...;

const double maxXValue = ...;

const double K = ...;

int f(double x)

{

assert(x >= minXValue && x <= maxXValue);

int index = floor((x - minXValue) / K); // (use floor() instead of

casting to int so negative values are handled OK)

const StepData &s = stepData[index];

return (x < s.cutOffPoint ? s.value : s.value + 1);

}

The value of "cutOffPoint" should be the next highest x value if it does not

apply (ie. if there is no "step" between (minXValue + index * K) and

(minXValue + (index + 1) * K).

If the minimum difference between any pair of x_ values is relatively small,

then multiple steps will map to the same index of stepData[] ... maybe have

a smaller StepData array again ? (ie. a recursive data structure that is

locally more fine grained where necessary). If the elements are mostly far

apart (eg. 1.0, 1000.0, 1000000.0 ...), then this approach might help as

well (to avoid creating an array with a million entries which are mostly

duplicates). Another space saving could be to have a single definition of

each StepData value (in a separate array) and to fill the stepData[] array

with pointers into it.

Obviously lots of refinements possible ...

Hope this helps,

David F