基于特定距离（阈值）的两个列表的交集

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))

基于特定距离（阈值）的两个列表的交集

Intersection of two lists based on a specific distance (threshold)

python

performance

intersection