比较两个大列表以查找满足 python 中条件的元素对

Question

我有两个大的数字列表（每个列表可能有一百万个元素）。我想按元素比较它们，以确定差异小于 0.5 的元素对。我知道两个嵌套的 for 循环不是一个选项。有什么快速的方法可以使用 sets 或 zip 来做到这一点？

例如。如果我的列表是 list1 = [1,2,3,4] 和 list2 = [3,4,5,6] 并且条件差为 1，那么解决方案会将这些对排列在列表中 [来自 list1 的元素，来自 list2 的元素，区别]。解决方案是 [[2,3,1],[3,3,0],[3,4,1],[4,3,1],[4,4,0],[4,5,1]]

谢谢

Answer 1

使用numpy的广播

import numpy as np
x = np.array([1, 2, 3, 4]).reshape(-1, 1)
y = np.array([3, 4, 5, 6]).reshape(1, -1)
diff = x - y

但是，你无法避免 N^2 次比较，只能利用 numpy 的速度优化。

Answer 2

这应该有效。（批评指正）

基本上，我的想法是对两个列表 O(nlogn) 进行排序，然后遍历列表，在内存中保留与下一个元素的距离，因此，不计算所有对，而只计算一个子集给我一个 O(2*m*n) m 是允许的最大距离

x = sorted([0, 2, 3, 4])
y = sorted([1,3, 4, 5, 6])
index = 0
delta = 1
output = []
j = 0
value_2 = y[0]
no_more = False
number_of_operation = 0
for i,value_1 in enumerate(x[:]):
    print(f'Testing for this {value_1}')
    skip = False
    try:
        next_value_at = x[i+1] - value_1 
        if next_value_at > delta:
            skip = True
            print('We can directly skip to next')
    except:
        print('At the end of list')
    while value_2 - value_1 <= delta:
        number_of_operation+=1
        print(value_1,value_2)
        try:
            if abs(value_1 - value_2) <= delta:
                output += [[value_1,value_2,value_1-value_2]]
            j+=1
            value_2 = y[j]
            print(value_1,value_2) 
            continue
        except:
            no_more = True
            print('end of list')
            break
    if not skip:
        print("Going back")
        j=index
        value_2 = y[index]
    else:
        index = j
    if no_more:
        print('end')
        break
    print(number_of_operation)

Answer 3

如果您先对列表进行排序（或者如果您的列表已经排序，则更好），您可能能够避免 O(N²) 行为。然后你可以明智地逐步通过它们。这将为您提供 O(nLogn) 的排序加上 O(n) 来遍历元素。例如：

list1 = range(0, 1000000)
list2 = range(999999, 1999999)

def getClose(list1, list2):
    c1, c2 = 0, 0
    while c1 < len(list1) and c2 < len(list2):
        if abs(list1[c1] - list2[c2]) <= 1:
            yield (list1[c1], list2[c2], abs(list1[c1] - list2[c2]))
        if list1[c1] < list2[c2]:
            c1 += 1
        else:
            c2 += 1

for n in getClose(list1, list2):
    print(n)

产生...

999998 999999 1
999999 999999 0
999999 1000000 1

...相对来说比较快，比先找产品要快很多

比较两个大列表以查找满足 python 中条件的元素对

Comparing two large lists to find element pairs that meet a condition in python

python

element

list

这应该有效。（批评指正）

比较两个大列表以查找满足 python 中条件的元素对

Comparing two large lists to find element pairs that meet a condition in python

python

element

list

这应该有效。 （批评指正）

这应该有效。（批评指正）