我有两个包含浮点值的排序列表。第一个包含我感兴趣的值(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: []}但是，当有匹配项时，我实际上要做的更多。任何帮助表示赞赏!
最佳答案
如果您对公式进行转置以生成给定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/M应用于公差/范围公式，而不是N * M，这将节省大量处理。