Быстрое вычисление расстояния хэмминга между двоичными массивами numpy

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

np.count_nonzero(a!=b)

По сравнению с 1,07 мкс для np.count_nonzero (a! = B) на моей платформе, gmpy2.hamdist снижает его примерно до 143 нс после преобразования каждого массива в mpz (целое число с множественной точностью):

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, преобразование из одномерного массива единиц и нулей в объект gmpy2 mpz может быть выполнено достаточно эффективно с помощью gmpy2.pack (list (reverse (list (array))), 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   

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

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

Для справки (без питрана):

$ 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.

для струн это работает быстрее

def Hamm(a, b):
    c = 0
    for i in range(a.shape[0]):
        if a[i] != b[i]:
            c += 1
    return c

Я предлагаю вам преобразовать массив numpy bit в массив numpy uint8, используя np.packbits

Взгляните на scipy space.distance.hamming: https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.hamming.html

в противном случае вот небольшой фрагмент, который требует только numpy, вдохновленный Быстрый способ подсчета ненулевых бит в положительном целом числе:

bit_counts = np.array([int(bin(x).count("1")) for x in range(256)]).astype(np.uint8)
def hamming_dist(a,b,axis=None):
    return np.sum(bit_counts[np.bitwise_xor(a,b)],axis=axis)

с axis = -1, это позволяет взять расстояние хаммига между записью и большим массивом; например:

inp = np.uint8(np.random.random((512,8))*255) #512 entries of 8 byte
hd = hamming_dist(inp, inp[123], axis=-1) #results in 512 hamming distances to entry 123
idx_best = np.argmin(hd)    # should point to identity 123
hd[123] = 255 #mask out identity
idx_nearest= np.argmin(hd)    # should point entry in list with shortest distance to entry 123
dist_hist = np.bincount(np.uint8(hd)) # distribution of hamming distances; for me this started at 18bits to 44bits with a maximum at 31