Python: Fastest Way to Compare Arrays Elementwise

Python: Fastest Way to compare arrays elementwise

For lists this works:

from itertools import zip_longest

def find_first_diff(list1, list2):
    for index, (x, y) in enumerate(zip_longest(list1, list2, 
                                               fillvalue=object())):
        if x != y:
            return index

zip_longest pads the shorter list with None or with a provided fill value. The standard zip does not work if the difference is caused by different list lengths rather than actual different values in the lists.

On Python 2 use izip_longest.

Updated: Created unique fill value to avoid potential problems with None as list value. object() is unique:

>>> o1 = object()
>>> o2 = object()
>>> o1 == o2
False

This pure Python approach might be faster than a NumPy solution. This depends on the actual data and other circumstances.

1. Converting a list into a NumPy array also takes time. This might actually
   take longer than finding the index with the function above. If you are not
   going to use the NumPy array for other calculations, the conversion
   might cause considerable overhead.

2. NumPy always searches the full array. If the difference comes early,
   you do a lot more work than you need to.

3. NumPy creates a bunch of intermediate arrays. This costs memory and time.

4. NumPy needs to construct intermediate arrays with the maximum length.
   Comparing many small with very large arrays is unfavorable here.

In general, in many cases NumPy is faster than a pure Python solution.
But each case is a bit different and there are situations where pure
Python is faster.

Comparing two NumPy arrays for equality, element-wise

(A==B).all()

test if all values of array (A==B) are True.

Note: maybe you also want to test A and B shape, such as A.shape == B.shape

Special cases and alternatives (from dbaupp's answer and yoavram's comment)

It should be noted that:

• this solution can have a strange behavior in a particular case: if either A or B is empty and the other one contains a single element, then it return True. For some reason, the comparison A==B returns an empty array, for which the all operator returns True.
• Another risk is if A and B don't have the same shape and aren't broadcastable, then this approach will raise an error.

In conclusion, if you have a doubt about A and B shape or simply want to be safe: use one of the specialized functions:

np.array_equal(A,B)  # test if same shape, same elements values
np.array_equiv(A,B)  # test if broadcastable shape, same elements values
np.allclose(A,B,...) # test if same shape, elements have close enough values

numpy arrays: fast element wise compare and set?

The for loop can be replaced with a slice and assignment, like so:

arr[apos:apos+64] = np.clip(arr[apos:apos+64], a_min=num, a_max=None)

Can also use np.maximum:

arr[apos:apos+64] = np.maximum(arr[apos:apos+64], num)

Timing:

import numpy as np
import random
​
tsize = 1000
arr = np.zeros(tsize, dtype=np.uint32)

%%timeit
for rounds in range(tsize):
    num = random.randint(1, 123456)        # generate a random number
    apos = random.randint(0, tsize - 64)   # a random position
    for kpos in range(apos, apos + 64):    # loop to compare and set 64 elements
        if arr[kpos] < num:
            arr[kpos] = num
# 10 loops, best of 3: 107 ms per loop

%%timeit
for rounds in range(tsize):
    num = random.randint(1, 123456)        # generate a random number
    apos = random.randint(0, tsize - 64)   # a random position
    arr[apos:apos+64] = np.clip(arr[apos:apos+64], a_min=num, a_max=None)
# 100 loops, best of 3: 4.14 ms per loop

%%timeit
for rounds in range(tsize):
    num = random.randint(1, 123456)        # generate a random number
    apos = random.randint(0, tsize - 64)   # a random position
    arr[apos:apos+64] = np.maximum(arr[apos:apos+64], num)
# 100 loops, best of 3: 4.13 ms per loop

# @Alexander's soln
%%timeit
for rounds in range(tsize):
    num = random.randint(1, 123456)        # generate a random number
    apos = random.randint(0, tsize - 64)   # a random position
    arr[apos:apos+64] = arr[apos:apos+64].clip(min=num)
# 100 loops, best of 3: 3.69 ms per loop

How to do element-wise comparison between two NumPy arrays

a= np.array([[1,2],[3,4]])
b= np.array([[3,2],[1,4]])

#1) find out which values are the same
a==b
# array([[False,  True],
#        [False,  True]])

#2) get the index of the same values?
np.where((a==b) == True) # or np.where(a==b)
#(array([0, 1]), array([1, 1]))

# Adding on to the previous question, is there a way for me to return 1 if the values are the same and 0 otherwise
(a==b).astype(int)
# array([[0, 1],
#        [0, 1]])

Check if two numpy arrays are identical

Until this is implemented in numpy natively you can write your own function and jit-compile it with numba:

import numpy as np
import numba as nb


@nb.jit(nopython=True)
def arrays_equal(a, b):
    if a.shape != b.shape:
        return False
    for ai, bi in zip(a.flat, b.flat):
        if ai != bi:
            return False
    return True


a = np.random.rand(10, 20, 30)
b = np.random.rand(10, 20, 30)


%timeit np.all(a==b)  # 100000 loops, best of 3: 9.82 µs per loop
%timeit arrays_equal(a, a)  # 100000 loops, best of 3: 9.89 µs per loop
%timeit arrays_equal(a, b)  # 100000 loops, best of 3: 691 ns per loop

Worst case performance (arrays equal) is equivalent to np.all and in case of early stopping the compiled function has the potential to outperform np.all a lot.

Efficient element-wise matching of two arrays in python

The algorithm is clearly inefficient (all methods): checking all items of rowB to find the one that is the closest is expensive and results in several billions of floating-point operations. Not to mention Numpy creates an expensive unnecessary temporary array for each call to elementA - rowB and np.abs.

You can speed up this by doing a sort followed by binary searches. The complexity in time of this approach is O(n**2 log n), while for the initial approach it is O(n**3). You can also write a parallel implementation of this algorithm easily using Numba. Moreover, you do not need to store the output in a float64-typed array: an integer-based array is enough (faster and possibly smaller).

Here is the resulting implementation:

import numba as nb
import numpy as np

@nb.njit('int_[:,::1](float64[:,::1],float64[:,::1])', parallel=True)
def method4(A,B):
    mB = B.shape[1]
    output = np.empty(A.shape, dtype=np.int_)

    # Parallel loop
    for r in nb.prange(A.shape[0]):
        rowA = A[r]
        rowB = B[r]

        # Sort a row
        index_rowB = np.argsort(rowB)
        sorted_rowB = rowB[index_rowB]

        # Fast binary search in the sorted row
        # See: https://stackoverflow.com/a/46184652/12939557
        idxs = np.searchsorted(sorted_rowB, rowA)
        left = np.fabs(rowA - sorted_rowB[np.maximum(idxs-1, 0)])
        right = np.fabs(rowA - sorted_rowB[np.minimum(idxs, mB-1)])
        prev_idx_is_less = (idxs == mB) | (left < right)

        # Find the position in the original unsorted array
        output[r] = index_rowB[idxs - prev_idx_is_less]

    return output

output4 = method4(A,B)

This is 482 times faster than the fastest initial implementation (method1) on my 10-core machine:

method1:  4341 ms
method2:  5839 ms
method4:     9 ms

---

Related Topics