python - 在距离最小的列表中找到 N 个最大的元素

Question

我想从列表中提取 N 个最大的元素，但我希望对任意两个元素都提取 x[i]和 x[j] , abs(i-j) > min_distance .

scipy.signal.find_peaks(x, distance=min_distance)提供此功能。但是我需要重复此操作数百万次，并且我正在尝试加快操作速度。

我注意到 find_peaks不接受参数 N指示要提取的峰数。它还不允许从最大到最小返回峰值，需要额外调用 l.sort()和 l = l[:N] .

我尝试编写一个惰性排序器，它只查找 N 个最大的元素而不对列表的其余部分进行排序。

得到以下结果here我选择了 heapq .这是我的尝试:

import heapq

def new_find_peaks(x, N, min_distance=0):
    x = enumerate(x)

    x = [(-val,i) for (i,val) in x]
    heapq.heapify(x)

    val, pos = heapq.heappop(x)
    peaks = [(-val, pos,)]

    while len(peaks)<N:

        while True:
            val, pos = heapq.heappop(x)
            d = min([abs(pos - pos_i) for _,pos_i in peaks])
            if d >= min_distance:
                break

        peaks.append((-val, pos,))

    return map(list, zip(*peaks)) #Transpose peaks into 2 lists

然而，这仍然比 find_peaks 慢 20 倍，可能是由于 find_peaks CPython 实现。另外，我注意到几乎一半的时间花在了

x = [(-val,i) for (i,val) in x]

你有什么更好的办法来加快这个操作吗？

--- 最小的可重现示例 ---

例如:

x = [-8.11, -7.33, -7.48, -5.77, -8.73, -8.73, -7.02, -7.02,
 -7.80, -10.92, -9.36, -9.83, -10.14, -10.77, -11.23, -9.20,
 -9.52, -9.67, -11.23, -9.98, -7.95, -9.83, -8.89, -7.33,
 -4.20, -4.05, -6.70, -7.02, -9.20, -9.21]

new_find_peaks(x, N=3, min_distance=5)

>> [[-4.05, -5.77, -7.8], [25, 3, 8]]

请注意 x[24]是-4.2，但由于x[25]更大并且25-24 < min_distance , 这被丢弃了。另请注意 x[8]不是真正的峰值，因为 x[7]更大，但由于与 x[3] 的距离而被丢弃.这是预期的行为。

Answer 1

用 Python 改进您的代码可能会给您带来一些改进，但由于您的代码看起来很干净并且算法的想法很合理，我认为您不会用 Python 方法击败 find_peaks。

因此，我建议您使用更接近金属的语言编写您自己的库，如果您需要 python 中的结果，则编写您自己的 python 包装器。例如，您可以使用 Swift。 Here是 Swift 中堆队列的实现，here你发现描述了一种与 python 交互的方法。

连接点留作练习。 ;)