Пересечение двух списков на основе определенного расстояния (порога) - PullRequest
Новая
       11

Пересечение двух списков на основе определенного расстояния (порога)

0 голосов
/ 24 июня 2018

Я хочу найти значения из list1, которые достаточно близки к значениям из list2 (на основе указанного порогового значения), т. Е. Функциональность, аналогичная приведенному ниже коду. Однако реализация intersect_with_threshold() ниже является очень медленной по сравнению с пересечением set в Pyhton (на много порядков медленнее!) К сожалению, пересечение set в python не подходит для моей цели, так как мне нужно использовать порог для выбора пересеченных значений. Кто-нибудь может подсказать, как ускорить работу 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)

1 Ответ

0 голосов
/ 24 июня 2018

Старайтесь не сравнивать каждый элемент из одного списка с каждым элементом из другого списка.

В этом случае это помогает сортировать списки. Я надеюсь, что идея ясна из кода. Либо тот, либо другой индекс увеличивается. (Используя 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))
...