獲得整數數組的漢明距離的最快方法

設a和b是具有8位整數（0-255）的相同大小的向量。我想計算那些向量不同的位數，即通過這些數字的二進制表示的串聯形成的向量之間的漢明距離。例如：獲得整數數組的漢明距離的最快方法

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

使用numpy的庫

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

我需要的是現在二進制表示上述陣列的每個元素，並在陣列中的所有元素計數的1的數量。上面的例子將使漢明距離爲0 + 4 = 4。Python中的任何快速和優雅的解決方案？

來源

2016-11-29 Debasish Mitra

那不'0 + 1'代替因爲254是除了在一個位全爲1，而255是全1？ – Divakar

大概只需要一個標準的popcount配方，在陣列上播放它，然後對結果進行求和。您可以通過將數組的緩衝區視爲更大的dtype來獲得加速。 – user2357112

@Divakar這是我的錯誤。接得好。樣本數據中的數字更新爲240。 –

方法1：我們可以進行廣播爲二進制位不同位的&計數，像這樣 -

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

採樣運行 -

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)

來源

2016-11-29 21:01:27 Divakar

方法2時拋出異常：類型錯誤 - ：「名單」和「名單」 –

@DebasishMitra添加一個更好的用'xor'那裏。 – Divakar

也許不是最有效的方式，但最簡單的海事組織您ouptut數組轉換爲二進制形式的字符串，然後把所有的字符和轉換回整數...

import numpy as np 

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

來源

2016-11-29 20:50:00 Aaron

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

來源

2016-11-29 21:21:00 ely

如果你要調用的距離函數多在您執行程序的一次執行期間，您可以通過使用預計算的位計數表獲得一些速度。這裏的（另一個）版本的漢明距離函數：

# _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在這個問題評論給定長度32的Python列表。 divakar_hamming_distance()和divakar_hamming_distance_v2()來自@ Divakar的回答。

這裏有定時@ 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

當然，如果你總是這樣，你計算的漢明距離之前，做轉換的時候一定要包括在總體時間中。但是，如果您編寫生成a和b的代碼以便早日利用numpy，則在計算海明距離時，可能已將它們作爲numpy陣列。

（I也試驗了一下與預先計算的漢明距離的8個值之間的2-d陣列 - 具有形狀（256陣列，256） - 但初始化成本較高和性能增益小。）

來源

2016-11-29 22:16:22

獲得整數數組的漢明距離的最快方法

回答

相關問題