Быстрого вычисление расстояния Хемминг между двоичными Numpy массивами

Question

у меня есть два Numpy массивов одинаковой длины, которые содержат двоичных значения

import numpy as np 
a=np.array([1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0]) 
b=np.array([1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1]) 

Я хочу, чтобы вычислить расстояние Хэмминга между ними как можно быстрее, так как у меня есть миллионы таких вычисления расстояния.

Простой, но медленный вариант это (взято из википедии):

%timeit sum(ch1 != ch2 for ch1, ch2 in zip(a, b)) 
10000 loops, best of 3: 79 us per loop 

Я придумал более быстрые варианты, вдохновленные ответы на некоторые вопросы здесь, на переполнение стека.

%timeit np.sum(np.bitwise_xor(a,b)) 
100000 loops, best of 3: 6.94 us per loop 

%timeit len(np.bitwise_xor(a,b).nonzero()[0]) 
100000 loops, best of 3: 2.43 us per loop 

Мне интересно, есть ли еще более быстрые способы вычислить это, возможно, используя cython?

Answer 1

Существует готовая функция NumPy, которая бьет len((a != b).nonzero()[0]);)

np.count_nonzero(a!=b) 

Answer 2

По сравнению с 1.07μs для np.count_nonzero (а = Ь) на моей платформе, gmpy2.hamdist получает ее вниз до 143ns после! преобразование каждого массива к МПЗ (множественного по точности целое число):

import numpy as np 
from gmpy2 import mpz, hamdist, pack 

a = np.array([1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0]) 
b = np.array([1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1]) 

на основании наконечника от @casevh, преобразование из массива 1D единиц и нулей к объекту gmpy2 МПЗ может быть сделано достаточно эффективно с gmpy2 .pack (список (негативы (список (массив))), 1).

# gmpy2.pack reverses bit order but that does not affect 
# hamdist since both its arguments are reversed 
ampz = pack(list(a),1) # takes about 4.29µs 
bmpz = pack(list(b),1) 

hamdist(ampz,bmpz) 
Out[8]: 7 

%timeit hamdist(ampz,bmpz) 
10000000 loops, best of 3: 143 ns per loop 

для относительного сравнения, на моей платформе:

%timeit np.count_nonzero(a!=b) 
1000000 loops, best of 3: 1.07 µs per loop 

%timeit len((a != b).nonzero()[0]) 
1000000 loops, best of 3: 1.55 µs per loop 

%timeit len(np.bitwise_xor(a,b).nonzero()[0]) 
1000000 loops, best of 3: 1.7 µs per loop 

%timeit np.sum(np.bitwise_xor(a,b)) 
100000 loops, best of 3: 5.8 µs per loop 

Answer 3

Использование pythran может принести дополнительную пользу здесь:

$ cat hamm.py 
#pythran export hamm(int[], int[]) 
from numpy import nonzero 
def hamm(a,b): 
    return len(nonzero(a != b)[0]) 

В качестве эталона (без pythran):

$ python -m timeit -s 'import numpy as np; a = np.random.randint(0,2, 100); b = np.random.randint(0,2, 100); from hamm import hamm' 'hamm(a,b)' 
100000 loops, best of 3: 4.66 usec per loop 

Во время кормления э pythran сборник:

$ python -m pythran.run hamm.py 
$ python -m timeit -s 'import numpy as np; a = np.random.randint(0,2, 100); b = np.random.randint(0,2, 100); from hamm import hamm' 'hamm(a,b)' 
1000000 loops, best of 3: 0.745 usec per loop 

Это грубо говоря, 6x убыстрения над реализацией Numpy, а pythran скачет создание промежуточного массива при оценке поэлементно сравнения.

Я также измерили:

def hamm(a,b): 
    return count_nonzero(a != b) 

И я получаю 3.11 usec per loop для версии Python и 0.427 usec per loop с Pythran один.

Отказ от ответственности: Я являюсь одним из разработчиков Pythran.