logo标签列表

使用容差匹配两个包含略有不同的浮点值的列表

pythonpython-3.xlist
6

我有两个包含浮点数值的排序列表。第一个(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)

提示：作为匹配函数的替代方案，我也可以先创建一个字典，将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：[]}但实际上，当有匹配时，我做了更多事情。
感谢任何帮助！
2
l2中的元素是否可能匹配到l1中的多个元素？ - StardustGogeta
最小值和最大值的阈值是多少？通过减去您的阈值创建一个l1_min数组，通过添加您的阈值创建一个l1_max数组。然后可以搜索l1_min < l2 < l1_max吗？ - Ken Syme
1
@Godrebh 好的，我明白了。也许您可以先对每个列表进行排序，然后对于 l1 中的每个元素，在 l2 中使用两个二分搜索来查找包含所有可能匹配项的子列表的起始和结束索引。对于每个列表，排序的时间复杂度为 O(nlogn)。然后，二分查找的时间复杂度为 O(nlogm)，而在范围内迭代的时间复杂度为 O(nm)（其中 l1 的大小为 n，l2 的大小为 m）。总体而言，我认为 l2 的排序（具有 O(mlogm)）将是限制因素。 - StardustGogeta
1
@StardustGogeta 天才！幸运的是，这两个列表已经排序好了。 - Godrebh
1
提醒一下：我首先尝试了Alain T.的答案，它比我之前的答案快得多（而且很简短！）。我也会尝试Andrej Kesely的解决方案，然后等待几个小时以获取更多评论或投票，然后再选择接受一个答案。非常感谢你！你太棒了。 - Godrebh
显示剩余4条评论
3个回答
3

我使用 itertools 重新实现了 for 循环。为使其正常工作，输入必须经过排序。为了进行基准测试，我生成了来自 <130.0, 135.0> 的 1000 个项目作为 l1，以及来自 <130.0, 135.0> 的 100_000 个项目作为 l2：

from timeit import timeit
from itertools import tee
from random import uniform

#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 = sorted([uniform(130.00, 135.00) for _ in range(1000)])
l2 = sorted([uniform(130.00, 135.00) for _ in range(100_000)])

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

def method2():
    iter_2, last_match = tee(iter(l2))
    d = {}
    for i in l1:
        d.setdefault(i, [])
        found = False
        while True:
            j = next(iter_2, None)
            if j is None:
                break
            if matching(i, j):
                d[i].append(j)
                if not found:
                    iter_2, last_match = tee(iter_2)
                    found = True
            else:
                if found:
                    break
        iter_2, last_match = tee(last_match)
    return d

print(timeit(lambda: method1(), number=1))
print(timeit(lambda: method2(), number=1))

输出：

16.900722101010615
0.030588202003855258
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次，这样可以节省大量处理时间。
0

你的列表已经排序好了，因此你可以使用类似于归并排序中“归并”部分的范式：跟踪idx1和idx2的当前元素，并且当其中一个可接受时，处理它并仅推进该索引。

d = {i:[] for i in l1}
idx1, idx2 = 0, 0
while idx1 < len(l1):
    while matching(l1[idx1], l2[idx2]) and idx2 < len(l2):
        d[l1[idx1]].append(l2[idx2])
        idx2 += 1
    idx1 += 1

print(d)
# {132.0317: [132.0317, 132.0318], 132.8677: [132.8678], 132.8862: [132.8862, 132.8861], 133.5852: [133.5851999], 133.7507: []}

这是 O(len(l1) + len(l2))，因为它对两个列表的每个元素都只执行一次。

这里有一个很大的警告，就是它从不“回溯” - 如果l1的当前元素与l2的当前元素匹配，但l1的下一个元素也将与l2的当前元素匹配，则后者不会被列出。修复这个问题可能需要添加某种“回溯”功能（在最坏情况下会将复杂度类推高一个数量级n，但仍然比反复迭代两个列表要快）。但是，它确实适用于您提供的数据集。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接