时间戳

首页 > 解决方案 > 通过允许容差匹配两个包含稍微不同的浮点值的列表

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

问题描述

我有两个包含浮点值的排序列表。第一个包含我感兴趣的值 ( 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: []}但实际上，当有匹配时，我会做更多的事情。

任何帮助表示赞赏！

标签： pythonpython-3.xlist

解决方案

我重新实现了 for 循环使用itertools. 为了使其正常工作，必须对输入进行排序。对于基准测试，我从 <130.0, 135.0> 生成了 1000 个项目，从 <130.0, 135.0> 生成了l1100_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

推荐阅读