database - 存储分段函数的数据结构

Question

我想实现一个功能：

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

而不是简单的 if-else 实现。

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

我有更好的数据结构来组织它吗？

另外，在给定两个序列 {an}、{bn} 的情况下，我如何编写一个返回优化的“func(x)”的“元函数”。

标签： databasealgorithmmathdata-structures

Answer 1

如果n很大，则要减少if语句数。在 Python 中，这可以通过将数据存储在字典中来完成：

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

对于给定的值x，对字典的键值进行二进制搜索。这为您提供了适当的键来使用，然后使用字典本身来获取相关值。如果您的语言不允许inf作为键，您可以将值an+1与字典分开，也许将两者都保存在 2 元组中。

这将最大测试次数从 减少n到log2(n)。

“元函数”在 Python 中很容易，因为函数是 Python 中的一等对象。您没有说明首选语言：如果您需要 Python 中的“元函数”示例，请告诉我。