CODEWITHSUNDEEP
databasealgorithmmathdata-structures
MTANG
MTANG

Reputation: 516

data structure to store piece-wise function

I want to implement a function that:

f(x) = a0   -inf < x < b0
       a1    b0 <= x < b1
       a2    b1 <= x < b2
       ...
       an    bn-1 <= x < bn
       an+1  bn <= x < +inf

Rather than the plain if-else implementation.

def func(x):
    if x<b0: return a0
    elif x<b1: return a1
    .....

Do I have a better data structure to organize this?

Also, how could I write a 'meta-function' that return the optimized 'func(x)' given the two sequences {an},{bn}.

Upvotes: 0

Views: 72

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59253

You could just store arrays of the a's and b's. Then to look up a value, you can do a binary search in the b array to find the index of the value to return in the a array.

That actually performs pretty well, but I came up with a faster way to do this that I think is pretty cool, when I had to implement the state machine for this lexical analysis package (https://github.com/mtimmerm/dfalex).

The representation of your function would be a binary tree stored sequentially in an array, like we commonly do for heaps: https://www.geeksforgeeks.org/array-representation-of-binary-heap/

The root of the tree is in array[0], the left child of any array[i] is at array[2i+1], and the right child of array[i] is at array[2i+2]. The leaves of the tree are all the a (result) values in order, and the internal node between each pair of adjacent a values is the b (argument) value at which you switch from one to another.

The heap-tree-order in the array ensures that all the a values occur contiguously at the end.

The benefit of this representation is that you can use this function to look up the appropriate value, which is simpler and faster than a binary search:

def lookup(x, array, num_internal_nodes)
    i=0
    while (i < num_internal_nodes):
        i = i*2 + (1 if x<array[i] else 2)
    return array[i]

Apologies if I made a mistake with the python syntax -- it's not a language I know well.

If you need to construct a function that just takes the input value, then you can build the array representation and call a function that makes a closure like this:

def makeF(array, num_internal_nodes):
    def f(x):
        return lookup(x, array, num_internal_nodes)
    return f

To build the array representation of your function in the first place, just make an array of the appropriate size (num_internal_nodes*2+1), and then do a pre-order traversal of the tree, filling in the a (leaf) and b (internal) values in order.

Upvotes: 0

Rory Daulton
Rory Daulton

Reputation: 22564

If n is large, you want to reduce the number of if statements. In Python, this could be done by storing your data in a dictionary:

fx = {b0: a0, b1: a1, b2: a2, ..., bn: an, math.inf: an+1}

For a given value of x, do a binary search on the key values of the dictionary. That gives you the appropriate key to use, then use the dictionary itself to get the related value. If your language does not allow inf as a key, you could keep the value of an+1 separate from the dictionary, perhaps keeping both in a 2-tuple.

This reduces the maximum number of tests from n to log2(n).

The 'meta-function' is easy in Python, since functions are first-class objects in Python. You do not state a preferred language: Let me know if you need an example of the 'meta-function' in Python.

Upvotes: 2

Related Questions