Самый быстрый способ получить расстояние hamming для целочисленного массива

Question

Пусть a и b - векторы того же размера с 8-битными целыми числами (0-255). Я хочу вычислить количество бит, где эти векторы различаются, т. Е. Расстояние Хэмминга между векторами, образованное путем конкатенации двоичных представлений этих чисел. Например:

a = [127,255] 
b= [127,240] 

Использование Numpy библиотеки

np.bitwise_xor(a,b) 
# Output: array([ 0, 15]) 

Что мне нужно теперь двоичный представляют каждый элемент массива выше и подсчитать количество 1s во всех элементах массива. Вышеприведенный пример даст расстояние hamming 0 + 4 = 4. Любое быстрое и элегантное решение для этого в Python?

Answer 1

подход № 1: Мы могли бы транслировать их в двоичные биты & подсчета числа различных битов, например, так -

def hamming_distance(a, b): 
    r = (1 << np.arange(8))[:,None] 
    return np.count_nonzero((a & r) != (b & r)) 

Sample пробег -

In [144]: a = [127,255] 
    ...: b = [127,240] 
    ...: 

In [145]: hamming_distance(a, b) 
Out[145]: 4 

Подход № 2: Использование bitwise-xor операции, можно узнать количество различных двоичных разрядов между a и b -

def hamming_distance_v2(a, b): 
    r = (1 << np.arange(8))[:,None] 
    return np.count_nonzero((np.bitwise_xor(a,b) & r) != 0) 

Answer 2

может быть, не самый эффективный способ, но самый простой имо, чтобы преобразовать массив ouptut в строки в двоичном виде, а затем взять сумму всех символов преобразуется обратно в Интс ...

import numpy as np 

output = np.random.randint(0,63,10) 
hamming = ['{:b}'.format(x).count('1') for x in output] 

Answer 3

sum(bin(x).count("1") for x in np.bitwise_xor(a,b)) 

Answer 4

Если вы собираетесь вызвать функцию расстояния многих раз в течение одного выполнения вашей программы, вы можете получить некоторую скорость, используя предварительно вычисленную таблицу бит. Вот (еще одна) версия функции расстояния Хэмминга:

# _nbits[k] is the number of 1s in the binary representation of k for 0 <= k < 256. 
_nbits = np.array(
     [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 
     4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 
     4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 
     3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 
     4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 
     5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 
     3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 
     3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 
     4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 
     6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 
     5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 
     7, 7, 8], dtype=np.uint8) 


def hamming_distance1(a, b): 
    c = np.bitwise_xor(a, b) 
    n = _nbits[c].sum() 
    return n 

В дальнейшем a и b являются списки Python длины 32, приведенные в комментарии к этому вопросу. divakar_hamming_distance() и divakar_hamming_distance_v2() от ответа Дивакара.

Вот тайминги @ функции Divakar в:

In [116]: %timeit divakar_hamming_distance(a, b) 
The slowest run took 5.57 times longer than the fastest. This could mean that an intermediate result is being cached. 
100000 loops, best of 3: 11.3 µs per loop 

In [117]: %timeit divakar_hamming_distance_v2(a, b) 
The slowest run took 5.35 times longer than the fastest. This could mean that an intermediate result is being cached. 
100000 loops, best of 3: 10.3 µs per loop 

hamming_distance1(a, b) немного быстрее:

In [118]: %timeit hamming_distance1(a, b) 
The slowest run took 6.04 times longer than the fastest. This could mean that an intermediate result is being cached. 
100000 loops, best of 3: 7.42 µs per loop 

На моем компьютере инициализации _nbits занимает около 11 мкс, так что нет никаких преимуществ используя hamming_distance1, если вы вызываете функцию только один раз. Если вы называете это три или более раз, есть чистая прибыль в производительности.

Если входы уже Numpy массивы, все функции значительно быстрее:

In [119]: aa = np.array(a) 

In [120]: bb = np.array(b) 

In [121]: %timeit divakar_hamming_distance_v2(aa, bb) 
The slowest run took 8.22 times longer than the fastest. This could mean that an intermediate result is being cached. 
100000 loops, best of 3: 5.72 µs per loop 

In [122]: %timeit hamming_distance1(aa, bb) 
The slowest run took 12.67 times longer than the fastest. This could mean that an intermediate result is being cached. 
100000 loops, best of 3: 2.77 µs per loop 

Конечно, если вы всегда можете сделать это непосредственно перед вычисления расстояния Хэмминга, время, чтобы сделать преобразование должно быть включен в общее время.Однако, если вы напишете код, который генерирует и b, чтобы воспользоваться преимуществами numpy ранее, вы можете уже иметь их в виде массивов numpy к тому времени, когда вы вычислите расстояние Хэмминга.

---

(Я также экспериментировал немного с 2-й массивом предварительно вычисленных расстояний Хэмминга между 8-битовыми значениями - массив с формой (256, 256), - но стоимость инициализации выше, и выигрыш в производительности являются небольшими.)