python - 用于在相同长度的一维 numpy 数组上评估一维函数数组的高效算法

Question

我有一个(大)长度为 N 的 k 不同函数数组，以及一个长度为 N 的横坐标数组。我想计算横坐标处的函数以返回一个长度为 N 的纵坐标数组，关键是，我需要非常快地完成它。

我已经尝试通过以下循环调用 np.where，这太慢了:

创建一些假数据来说明问题:

def trivial_functional(i): return lambda x : i*x
k = 250
func_table = [trivial_functional(j) for j in range(k)]
func_table = np.array(func_table) # possibly unnecessary

我们有一个包含 250 个不同函数的表。现在我创建了一个大数组，其中包含这些函数的许多重复条目，以及一组相同长度的点，这些点应在这些点上进行计算。

Npts = 1e6
abcissa_array = np.random.random(Npts)
function_indices = np.random.random_integers(0,len(func_table)-1,Npts)
func_array = func_table[function_indices]

最后，遍历数据使用的每个函数并在相关点集上对其进行评估:

desired_output = np.zeros(Npts)
for func_index in set(function_indices):
    idx = np.where(function_indices==func_index)[0]
    desired_output[idx] = func_table[func_index](abcissa_array[idx])

这个循环在我的笔记本电脑上大约需要 0.35 秒，这是我代码中最大的瓶颈一个数量级。

有人知道如何避免对 np.where 的盲目查找调用吗？是否可以巧妙地使用 numba 来加速此循环？

Answer 1

这与您的(非常棒!) self 回答几乎相同，但不那么繁琐。在我的机器上它似乎也稍微快了一点——基于粗略的大约 30 毫秒 test .

def apply_indexed_fast(array, func_indices, func_table):
    func_argsort = func_indices.argsort()
    func_ranges = list(np.searchsorted(func_indices[func_argsort], range(len(func_table))))
    func_ranges.append(None)
    out = np.zeros_like(array)
    for f, start, end in zip(func_table, func_ranges, func_ranges[1:]):
        ix = func_argsort[start:end]
        out[ix] = f(array[ix])
    return out

与您的一样，这会将一系列 argsort 索引分成多个 block ，每个 block 对应于 func_table 中的一个函数。然后它使用每个 block 为其对应的函数选择输入和输出索引。为了确定 block 边界，它使用 np.searchsorted 而不是 np.unique —— 其中可以想到 searchsorted(a, b)作为二分搜索算法，返回 a 中第一个值的索引等于或大于给定值或 b 中的值。

然后 zip 函数简单地并行迭代它的参数，从每个参数返回一个项目，将它们收集在一个元组中，然后将它们串在一起成一个列表。 (所以 zip([1, 2, 3], ['a', 'b', 'c'], ['b', 'c', 'd']) 返回 [(1, 'a', 'b'), (2, 'b', 'c'), (3, 'c', 'd')].) 这个，连同 for 语句内置的“解包”这些元组的能力，允许以简洁但富有表现力的方式并行迭代多个序列。

在这种情况下，我用它来遍历 func_tables 中的函数以及 func_ranges 的两个不同步副本。这可确保 end 变量中 func_ranges 中的项目始终比 start 变量中的项目领先一步。通过将 None 附加到 func_ranges，我确保最终 block 得到妥善处理——zip 在其任何一个参数用完项目时停止，它切断了序列中的最终值。方便的是，None 值也用作开放式切片索引!

另一个做同样事情的技巧需要多几行，但内存开销较低，尤其是当与 itertools 等价于 zip 一起使用时，izip :

range_iter_a = iter(func_ranges)   # create generators that iterate over the 
range_iter_b = iter(func_ranges)   # values in `func_ranges` without making copies
next(range_iter_b, None)           # advance the second generator by one
for f, start, end in itertools.izip(func_table, range_iter_a, range_iter_b):
    ...

但是，这些基于生成器的低开销方法有时可能比普通列表慢一点。另外请注意，在 Python 3 中，zip 的行为更像 izip。