Skip to main content
 首页 » 编程设计

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

2024年11月01日15think

我想从列表中提取 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] 的距离而被丢弃.这是预期的行为。

请您参考如下方法:

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

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

连接点留作练习。 ;)