python - 基于特定距离(阈值)的两个列表的交集

Question

我想找到 list1 中与 list2 中的值足够接近的值(基于指定的阈值)，即与下面的代码类似的功能。然而，与 pyhton 的 set 交集相比，下面的 intersect_with_threshold() 的实现非常慢(慢了许多数量级!)不幸的是，python 的 set 交集对我的目的没有帮助，因为我需要使用阈值来选择相交的值。谁能指导我如何加速 intersect_with_threshold() 函数？提前非常感谢

import time
import random

ln=100
list1=[]
list2=[]
#generating the two lists
for i in range(1000):
    list1.append(round(random.random()*ln))
    list2.append(round(random.random()*ln))

# custom intersection function with a threshold    
def intersect_with_theshold(lst1, lst2, threshold):
    intersected_list=[]
    for j in lst1:
        for i in lst2:
            d = abs(i - j)
            if(d < threshold):
                intersected_list.append(j)
    return list(set(intersected_list))  

## using the custom made intersection function    
t1=time.time()
out1=intersect_with_theshold(list1, list2, 0.001)
t2=time.time()
print(t2-t1)    

## using inbuilt python intersection function 
t1=time.time()
out2=(list(set(list1).intersection(list2)))
t2=time.time()
print(t2-t1)

Answer 1

尽量避免将一个列表中的每一项与另一列表中的每一项进行比较。

在这种情况下，它有助于对列表进行排序。我希望代码中的想法是清楚的。一个或另一个索引递增。 (像您一样，使用 i 为 lst2 建立索引，使用 j 为 lst1 建立索引。)

def intersect_with_theshold(lst1, lst2, threshold):
    intersected_list=[]
    lst2 = sorted(lst2)
    i = 0
    for j in sorted(lst1):
        lower = j - threshold
        try:
            while not lower < lst2[i]:
                i += 1
        except IndexError:
            break
        if lst2[i] < j + threshold:
            intersected_list.append(j)
    return list(set(intersected_list))