通过允许公差匹配两个包含稍微不同的浮点值的列表

Question

我有两个包含浮点值的排序列表。第一个包含我感兴趣的值（l1），第二个列表包含我要搜索的值（l2）。但是，我不是在寻找完全匹配的内容，而是在容忍基于函数的差异。由于我经常进行此搜索（>> 100000），并且列表可能很大（〜5000和〜200000个元素），因此我对运行时非常感兴趣。起初，我以为可以使用numpy.isclose()，但是我的宽容度不是固定的，而是取决于兴趣的价值。几个嵌套的for循环可以工作，但是速度很慢。我确信有一些有效的方法可以做到这一点。

#check if two floats are close enough to match
def matching(mz1, mz2):
    if abs( (1-mz1/mz2) * 1000000) <= 2:
        return True
    return False

#imagine another huge for loop around everything
l1  = [132.0317, 132.8677, 132.8862, 133.5852, 133.7507]
l2  = [132.0317, 132.0318, 132.8678, 132.8861, 132.8862, 133.5851999, 133.7500]

d = {i:[] for i in l1}
for i in l1:
    for j in l2:
        if matching(i, j):
            d[i].append(j)

fyi：作为匹配函数的替代方法，我还可以先创建一个字典，将感兴趣的值映射l1到(min ,max)我允许的窗口中。例如{132.0317:(132.0314359366, 132.0319640634), ...}，但是我认为检查每个值l2是否位于该词典的窗口之一内会更慢...

这将是如何生成包含l1中每个值的最小值/最大值的字典的方法：

def calcMinMaxMZ(mz, delta_ppm=2):
    minmz = mz- (mz* +delta_ppm)/1000000
    maxmz = mz- (mz* -delta_ppm)/1000000
    return minmz, maxmz

minmax_d = {mz:calcMinMaxMZ(mz, delta_ppm=2) for mz in l1}

结果可能是这样的字典： d = {132.0317: [132.0317, 132.0318], 132.8677: [132.8678], 132.8862: [132.8862, 132.8861], 133.5852: [133.5851999], 133.7507: []}但是，当有匹配项时，我实际上要做的更多。

任何帮助表示赞赏！

Answer 1

如果您转置公式以生成给定 mz1 的一系列 mz2 值，则可以使用二分搜索来查找排序的 l2 列表中的第一个匹配项，然后按顺序向上查找，直到到达范围的末尾。

def getRange(mz1):
    minimum = mz1/(1+2/1000000) 
    maximum = mz1/(1-2/1000000)
    return minimum,maximum

l1  = [132.0317, 132.8677, 132.8862, 133.5852, 133.7507]
l2  = [132.0317, 132.0318, 132.8678, 132.8862, 132.8861, 133.5851999, 133.7500]

l2  = sorted(l2)
from bisect import bisect_left
d = { mz1:[] for mz1 in l1 }
for mz1 in l1:
    lo,hi = getRange(mz1)
    i = bisect_left(l2,lo)
    while i < len(l2) and l2[i]<= hi:
        d[mz1].append(l2[i])
        i+=1

对 l2 进行排序将花费 O(NlogN)，创建字典将花费 O(MlogN)，其中 N 是 len(l2)，M 是 len(l1)。您将仅应用公差/范围公式 M 次，而不是 N*M 次，这应该节省大量处理。