Python: How to find two equal/closest values between two separate arrays?

Question

Let's say we have two arrays of equal length:

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

Which variable from arr1 is equal / closest to a variable from arr2?

Looking at these two lists we can easily say that the closest numbers are 4.5 and 5. I've tried to implement a function that returns two closest values given two lists and it kinda works for the examples above, but it is barely a solution because it is not optimal. And you can easily check that the function fails when we slightly change the arrays like this:

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

the values the function returns are 13 and 18

Here is the function:

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

Can you come up with a better one?

For me its seems 5 and 4.5 are closest ? – Tanveer Alam Dec 02 '14 at 00:19 — Tanveer Alam, Dec 02 '14 at 00:19

wflynny · Accepted Answer · 2014-12-08T17:00:15.903

Is speed an issue? Do you care about ties? If not, what about something simple like

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

For both

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

and

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

this yields

(5, 4.5)

Explanation:

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

yields a list of all N**2 pairs of numbers:

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

Then we sort them by the absolute difference (|a1 - a2|) using sorted. By passing sorted the key keyword, we tell sorted to use the sorting criteria lambda t: abs(t[0] - t[1]). The pair with the smallest absolute difference is placed in the first index of the sorted array, so we can grab it by tacking [0] on the end.

Edit:

As suggested by Piotr in the comments, you can feed a key=func to min and max, which speeds this up considerably. Try instead:

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

nice indeed, but I need some time to understand what's going on here. — minerals, Dec 02 '14 at 00:29

Piotr Dabkowski · Answer 2 · 2014-12-02T03:48:59.330

This is the fastest algorithm I was able to write, it has n*log(n) complexity which is much faster than naive n*n approach presented in other answers. It sorts arrays before processing ( it is the most time consuming part ) and later tries to minimize the difference (this takes 2*n in the worst case):

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

Tanveer Alam · Answer 3 · 2014-12-02T00:47:43.783

>>> arr1 = (21, 2, 3, 5, 13)
>>> arr2 = (10, 4.5, 9, 12, 20)
>>> for a1 in arr1:
...     for a2 in arr2:
...         if a1 > a2:
...             result.append([a1, a2, a1-a2])
...         else:
...             result.append([a1, a2, a2-a1])
>>> sorted(result, key=lambda i:i[-1])[0][:2]
[5, 4.5]

A simple way could be get difference between both arrays and sort them by their difference and get the first element.

>>> sorted([[a1,a2,a1-a2] if(a1>a2) else [a1,a2,a2-a1] for a1 in arr1 for a2 in arr2], key=lambda i:i[-1])[0][:2]
[5, 4.5]

score 1 · Answer 4 · answered Dec 02 '14 at 00:58

What about simply saving the difference and the values in each iteration...

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

diff = float("inf")

for a1 in arr1:
    for a2 in arr2:
        if abs(a1-a2) < diff:
            diff = abs(a1-a2)
            values = (a1, a2)

print(values)

score 1 · Answer 5 · answered Jan 26 '17 at 10:27

Here a function which solves this problem in ~0.01s for an two vectors with the length 1000, 2000:

def get_closest_elements(arr_1, arr_2):
    """
    The function finds the two closest elements in two arrays

    Returns
    -------
    idx_1 : int
        index of element in arr_1
    idx_2 : int
        index of element in arr_2
    min_diff : float
        minimal difference between arrays
    """

    # get array with all differences between arrays
    diff_arr = x[:, np.newaxis] - y

    # get absolute value
    diff_arr = np.abs(diff_arr)

    # get minimum difference
    min_diff = np.min(diff_arr)

    # get the indexes for the elements of interest in arr_1 and arr_2
    idx_1, idx_2 = np.where(diff_arr == min_diff)

    return idx_1, idx_2, min_diff


# apply function
x = np.array([21, 2, 3, 5, 13])
y = np.array([10, 4.5, 9, 12, 20])
# n = 1000
# x = np.random.rand(n)
# y = np.random.rand(2*n)

idx_1, idx_2, min_diff = get_closest_elements(x, y)
print "x{} - y{} = {}".format(idx_1, idx_2, min_diff)

Python: How to find two equal/closest values between two separate arrays?

5 Answers5

Linked