Python：如何在两个单独的数组之间找到两个相等/最接近的值？

Question

假设我们有两个长度相等的数组：

arr1 = (21, 2, 3, 5, 13)
arr2 = (10, 4.5, 9, 12, 20)

哪个变量从arr1IS 等于/最接近把变量arr2？

查看这两个列表，我们可以轻松地说出最接近的数字是4.5和5。我试图实现一个函数，该函数在给定两个列表的情况下返回两个最接近的值，并且它对于上面的示例还算有效，但是这并不是一个解决方案，因为它不是最佳的。而且，当我们对数组进行如下更改时，您可以轻松地检查函数是否失败：

arr1 = (21, 2, 3, 5, 13)
arr2 = (10, 4.5, 9, 12, 18)

函数返回的值是13和18

这是函数：

def get_nearest(arr1, arr2):
    lr = [[0, 0, 0]]
    for x1 in arr1:
        for x2 in arr2:
            r = (x1 / x2 % (x1 + x2))
            print x1, x2, r
            if r <= 1 and r >= lr[0][2]:
                lr.pop()
                lr.append([x1, x2, r])
    return lr

你能提出更好的选择吗？

Answer 1

速度是问题吗？你在乎关系吗？如果没有，那么简单的东西怎么样

from itertools import product
sorted(product(arr1, arr2), key=lambda t: abs(t[0]-t[1]))[0]

对彼此而言

arr1 = (21, 2, 3, 5, 13)
arr2 = (10, 4.5, 9, 12, 20)

和

arr1 = (21, 2, 3, 5, 13)
arr2 = (10, 4.5, 9, 12, 18)

这产生

(5, 4.5)

解释：

product(arr1, arr2) = [(a1, a2) for (a1, a2) in product(arr1, arr2)]

产生所有N**2数字对的列表：

[(21, 10), (21, 4.5), ..., (13, 12), (13, 20)]

然后我们|a1 - a2|使用sorted. 通过传递sorted的key关键字，我们告诉sorted使用排序标准lambda t: abs(t[0] - t[1])。绝对差最小的一对被放置在已排序数组的第一个索引中，因此我们可以通过添加[0]到末尾来获取它。

编辑：

正如 Piotr 在评论中所建议的，您可以提供一个key=functo minand max，这可以大大加快速度。试试吧：

from itertools import product
min(product(arr1, arr2), key=lambda t: abs(t[0]-t[1]))[0]

Answer 2

这是我能够编写的最快算法，它的n * log（n）复杂度比其他答案中提到的朴素的n * n方法要快得多。它在处理之前对数组进行排序（这是最耗时的部分），然后尝试最小化差异（在最坏的情况下需要2 * n）：

def closest_array_items(a1, a2):
    if not a1 or not a2:
        raise ValueError('Empty array')
    a1, a2  = iter(sorted(a1)), iter(sorted(a2))
    i1, i2 = a1.next(), a2.next()
    min_dif = float('inf')
    while 1:
        dif = abs(i1 - i2)
        if dif < min_dif:
             min_dif = dif
             pair = i1, i2
             if not min_dif:
                  break
        if i1 > i2:
            try:
                i2 = a2.next()
            except StopIteration:
                break
        else:
            try:
                i1 = a1.next()
            except StopIteration:
                break
    return pair