# Python: Scipy/numpy All Pairs Computation Between Two 1-D Vectors

I have two lists `l1`

and `l2`

containing integers that may be of different lengths, and I want to perform a computation between every possible pairing between these two vectors.

Specifically, I'm checking the Hamming distance between each pair and if the distance is sufficiently small I want to "count" it.

Naively, this could be implemented

```
def hamming_distance(n1: int, n2: int) -> float:
return bin(n1 ^ n2).count('1')/32.0
matches = 0
for n1 in l1:
for n2 in l2:
sim = 1 - hamming_distance(n1, n2)
if sim >= threshold:
matches += 1
```

But this is not very fast.

I've unsuccessfully tried to leverage `scipy.spatial.distance.cdist`

, where I figured that I would first compute the Hamming distance between all pairs, as the scipy.spatial.cdist documentation states that it will

Compute distance between each pair of the two collections of inputs.

and then count the number of elements satisfying the predicate that `1 - d >= threshold`

where `d`

is the Hamming distance, i.e.

```
from scipy.spatial.distance import cdist
l1 = l1.reshape(-1, 2) # After np.array
l2 = l2.reshape(-1, 2)
r = cdist(l1, l2, 'hamming')
matches = np.count_nonzero(1 - r >= threshold)
```

but the number of matches found by the respective solutions are different. I've noticed that it is possible to call `cdist`

with a function, `cdist(XA, XB, f)`

but I have not succeeded in writing my implementation of `hamming_distance`

so that it broadcasts properly.

I've looked at this question/answer but it presumes that both lists are of the same length which is not the case here.

## Answer

Here are three approaches using

`scipy.spatial.KDTree`

`scipy.spatial.distance.cdist`

- a lookup table

On a pair of 32bit int vectors of lengths 100 and 200 they all give the same result; speedwise they compare as follows:

```
count_sim_kd 16.408800622448325 ms
count_sim_cd 12.41896384395659 ms
count_sim_lu 0.8755046688020229 ms
```

So at this problem size look up wins by a huge margin.

Code:

```
import numpy as np
from scipy.spatial import cKDTree as KDTree
from scipy.spatial.distance import cdist
l1 = np.random.randint(0,2**32,100)
l2 = np.random.randint(0,2**32,200)
threshold = 10/32
def hamming_distance(n1: int, n2: int) -> float:
return bin(n1 ^ n2).count('1')/32.0
matches = 0
for n1 in l1:
for n2 in l2:
sim = 1 - hamming_distance(n1, n2)
if sim >= threshold:
matches += 1
def count_sim_kd(a,b,th):
A,B = (KDTree(np.unpackbits(x[:,None].view(np.uint8),axis=1))
for x in (a,b))
return A.sparse_distance_matrix(B,max_distance=32-int(32*th),p=1).nnz
def count_sim_cd(a,b,th):
A,B = (np.unpackbits(x[:,None].view(np.uint8),axis=1) for x in (a,b))
return np.count_nonzero(cdist(A,B,"minkowski",p=1)<=32-int(32*th))
lu = sum(np.unravel_index(np.arange(256),8*(2,)))
def count_sim_lu(a,b,th):
return np.count_nonzero(lu[(a[:,None,None]^b[None,:,None])
.view(np.uint8)].sum(2)<=32-int(32*th))
from timeit import timeit
for f in (count_sim_kd,count_sim_cd,count_sim_lu):
assert f(l1,l2,threshold)==matches
print(f.__name__,timeit(lambda:f(l1,l2,threshold),number=100)*10,'ms')
```

## Related Questions

- → What are the pluses/minuses of different ways to configure GPIOs on the Beaglebone Black?
- → Django, code inside <script> tag doesn't work in a template
- → React - Django webpack config with dynamic 'output'
- → GAE Python app - Does URL matter for SEO?
- → Put a Rendered Django Template in Json along with some other items
- → session disappears when request is sent from fetch
- → Python Shopify API output formatted datetime string in django template
- → Can't turn off Javascript using Selenium
- → WebDriver click() vs JavaScript click()
- → Shopify app: adding a new shipping address via webhook
- → Shopify + Python library: how to create new shipping address
- → shopify python api: how do add new assets to published theme?
- → Access 'HTTP_X_SHOPIFY_SHOP_API_CALL_LIMIT' with Python Shopify Module