在Python中將2d二進制列表轉換爲十進制數的算法

當我嘗試將二進制數據的巨大二維列表轉換爲十進制數時，遇到了這個性能問題。在Python中將2d二進制列表轉換爲十進制數的算法

給出一個列表：

biglist = [ 
    [[1,0],[0,0],[1,1]], 
    [[0,0],[1,1],[1,0]], 
    #... 
    #easily go to thousands of rows 
]

在每一行，我想結合各列的所有第一個元素，並將其轉換成十進制數：

例如

行0中，我想int('101',2)即5

在第1行，我想int('011',2)即3

我的最終目標是創建一個重要的東西整數出現多少次的字典。考慮到上面的例子中的給定的數據，最後的結果應與{key:value}對像{a_int : appearance_count}這樣的字典：

{{5:1},{3:1}}

現在我的解決辦法是這樣的：

result = {} 
for k in biglist: 
    num = int("".join(str(row[0]) for row in k), 2) 
    #count 
    if num not in result: 
     result[num] = 1 
    else: 
     result[num] += 1

這個循環爲慢成千上萬行的列表，是否有更好的解決方案？

來源

2017-10-15 tic30

我想，如果你的代碼工作正常，但要提高它，你應該在[代碼審查堆棧交易所（HTTPS發佈此/codereview.stackexchange.com/） – RoyaumeIX

整數值可能的範圍是多少？ – randomir

每個「行」的列數是否相同？即 - 你只在這裏處理3位......或者他們可能會更大？ –

僅僅收取整數值的位而不是字符串INT轉換：（僞）

for every row: 
    value = 0 
    for every col: 
     value = (value << 1) | biglist[row][col][0] # bitwise shift left and OR 

    #equivalent operation: 
     value = value * 2 + biglist[row][col][0]

來源

2017-10-15 16:41:11 MBo

謝謝。與使用字符串「join」相比，這提高了性能，並且在不使用額外的庫的情況下，對性能有很大的提升。 – tic30

首先，使用字符串與join進行int轉換很方便，但速度很慢。計算從2 classicaly的權力值，使用sum，enumerate並在那些位移位（跳過零）

其次，你應該使用collections.Counter這個

在一個行：

result = collections.Counter(sum(v[0]<<(len(k)-i-1) for i,v in enumerate(k) if v[0]) for k in biglist)

該代碼運行速度比我的機器上的原始代碼快30％。

來源

2017-10-15 16:27:27

謝謝。使用'collections.Counter'來計算確實是個好主意。性能提升非常顯着。 – tic30

如果您需要的性能，您應該使用numpy的或numba，而這一切低級程序完成後，在近C速度：

import numpy as np 
bigarray=np.random.randint(0,2,10**4*3*2).reshape(10**4,3,2) 
biglist=[[[e for e in B] for B in A] for A in bigarray] 
# [[[1, 0], [0, 0], [1, 0]], 
# [[0, 0], [0, 1], [0, 1]], 
# [[1, 0], [1, 0], [0, 0]], ... 

def your_count(biglist): 
    integers=[] 
    for k in biglist: 
     num = int("".join(str(row[0]) for row in k), 2) 
     integers.append(num) 
    return integers 

def count_python(big): 
    m=len(big) 
    integers=np.empty(m,np.int32) 
    for i in range(m): 
     n=len(big[i]) 
     b=1 
     s=0 
     for j in range(n-1,-1,-1): 
       s = s+big[i][j][0]*b 
       b=b*2 
     integers[i]=s 
    return integers 

def count_numpy(bigarray): 
integers=(bigarray[:,:,0]*[4,2,1]).sum(axis=1) 
return integers 

from numba import njit  
count_numba =njit(count_python)

和一些測試：

In [125]: %timeit your_count(biglist) 
145 ms ± 22.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

In [126]: %timeit count_python(biglist) 
29.6 ms ± 1.13 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

In [127]: %timeit count_numpy(bigarray) 
354 µs ± 10.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

In [128]: %timeit count_numba(bigarray) 
73 µs ± 938 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Numba讓你編譯一些python代碼的低級版本（不是你的，因爲Numba不管理字符串和列表，只有numpy數組）。 Numpy給你特殊的語法來在一個指令中創造出奇妙的東西，以獲得好的表演。

Numba解決方案在這裏比你的解決方案快2000倍。

計數被有效地collections.Counter或np.unique計算：/：

In [150]: %timeit {k:v for k,v in zip(*np.unique(integers,return_counts=True))} 
46.4 µs ± 1.55 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

In [151]: %timeit Counter(integers) 
218 µs ± 11.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

來源

2017-10-15 17:06:37

這工作，它確實幫助我理解numpy。謝謝。 – tic30

在Python中將2d二進制列表轉換爲十進制數的算法

回答

相關問題