2次元バイナリリストをPythonの10進数に変換するアルゴリズム

Question

2次元データの巨大な2Dリストを10進数に変換しようとしたときに、このパフォーマンスの問題が発生しました。各行で

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

、私は、各列のすべての最初の要素を組み合わせて、進数に変換したい：

例えばリストを考えると

行0で

、私は1行でint('101',2)すなわち5

をしたい、私はint('011',2)すなわち3

私の最終目標が何度も表示されますどのような整数カウント辞書を作成することですしたいです。上記の例では、与えられたデータを考慮すると、最終的な結果は、このような{a_int : appearance_count}よう{key:value}ペアと辞書でなければなりません：

{{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 

このループは、のために遅いです何千もの行のリストは、より良い解決策はありますか？

Answer 1

だけではなく、文字列、整数変換の整数値のビットを集める：（擬似コード）

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] 

Answer 2

最初に、joinで文字列からintへの変換を使用するのは便利ですが、遅いです。

セカンドを（ゼロをスキップ）sum、enumerateとするものでビットシフトを使用して、2 classicalyのべき乗の値を計算し、あなたは1行では、この

ため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％高速に動作します。

Answer 3

をあなたはパフォーマンスが必要な場合は、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)