Najszybszy sposób uzyskania odległości Hamminga dla tablicy całkowitej

Question

Niech aib będą wektorami o tym samym rozmiarze z liczbami całkowitymi 8-bitowymi (0-255). Chcę obliczyć liczbę bitów, w których różnią się te wektory, tj. Odległość Hamminga między wektorami utworzoną przez konkatenację reprezentacji binarnych tych liczb. Na przykład:

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

Korzystanie numpy bibliotekę

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

Co potrzebne jest teraz na binarny reprezentować każdy element powyższej tablicy i policzyć liczbę 1s we wszystkich elementach tablicy. Powyższy przykład daje odległość Hamminga 0 + 4 = 4. Jakiekolwiek szybkie i eleganckie rozwiązanie tego w Pythonie?

Answer 1

podejście nr 1: mogliśmy transmitować je do bitów binarnych & numer zliczania różnych bitów, tak jak - bieg

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 

Podejście nr 2: Korzystanie bitwise-xor operację, możemy dowiedzieć się wiele różnych bitów binarnych pomiędzy a i 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

może nie najbardziej skuteczny sposób, ale najłatwiej imo jest przekształcenie tablicę ouptut do strun w postaci binarnej, a następnie podjąć sumę wszystkich znaków przekształcony z powrotem do int ...

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

Jeśli masz zamiar wywołać funkcję odległość wielu razy podczas jednej z realizacji programu, można uzyskać pewną prędkość za pomocą wstępnie obliczonej tabeli bitów. Oto (kolejny) wersja funkcji odległości Hamminga:

# _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 

Poniżej a i b są listy Python o długości 32 podane w komentarzu na pytanie. divakar_hamming_distance() i divakar_hamming_distance_v2() są z odpowiedzi @ Divakara.

Oto czasy z @ funkcje Divakar za:

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) jest nieco szybciej:

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 

Na moim komputerze, inicjowanie _nbits trwa około 11 mikrosekund, więc nie ma zaletę używając hamming_distance1, jeśli wywołasz funkcję tylko raz. Jeśli nazwiesz to trzy lub więcej razy, osiągniesz zysk netto.

Jeżeli wejścia są już numpy tablice, wszystkie funkcje są znacznie szybsze:

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 

Oczywiście, jeśli zawsze to zrobić bezpośrednio przed obliczyć odległość Hamminga, czas zrobić konwersję muszą być uwzględnione w ogólnym harmonogramie.Jednakże, jeśli napiszesz kod, który generuje a i b, aby móc korzystać z numpy wcześniej, możesz już mieć je jako tablice numpy przed obliczeniem odległości Hamminga.

---

(również eksperymenty trochę z 2-d tablicy precomputed odległości Hamminga pomiędzy wartościami 8-bitowych - tablica z kształtu (256, 256), - inicjowanie ale koszt jest wyższa i wzrost wydajności są małe.)