ポップカウント計算速度の比較[numpy]

# ポップカウント計算速度の比較

numpyで、m1,m2,m3の３種類の方法でポップカウント（uintのbitの１の数）の計算速度を比較した。

# 実験・結果
```python
import numpy as np
import cupy as cp
import time
import pandas as pd
```


```python
# 参考　https://stackoverflow.com/questions/63954102/numpy-vectorized-way-to-count-non-zero-bits-in-array-of-integers
#@Ehsan's solution
def m1(a):
  return np.unpackbits(a.view('uint8')).sum()

#@Valdi_Bo's solution
def m2(a):
  return sum([ bin(n).count('1') for n in a ])

def m3(a):  # ※uint8しか処理できない
    return np.count_nonzero(np.unpackbits(a))

# in_ = [np.random.randint(100000,size=(n)) for n in [10,100,1000,10000,100000]]
```

## uint8の場合


```python
ret = []
for name,func in zip('m1,m2,m3'.split(','),[m1,m2,m3]):
    for n in [10**2,10**3,10**4,10**5,10**6]:
        arr = np.random.randint(255,size=(n), dtype=np.uint8)
        ts = time.perf_counter()
        func(arr) # 実行
        ret.append({
                'name':name,
                'count':n,
                'time':time.perf_counter()-ts,
            })
df_result = pd.DataFrame(ret)
df_result
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }
    
    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>name</th>
      <th>count</th>
      <th>time</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>m1</td>
      <td>100</td>
      <td>0.000041</td>
    </tr>
    <tr>
      <th>1</th>
      <td>m1</td>
      <td>1000</td>
      <td>0.000032</td>
    </tr>
    <tr>
      <th>2</th>
      <td>m1</td>
      <td>10000</td>
      <td>0.000162</td>
    </tr>
    <tr>
      <th>3</th>
      <td>m1</td>
      <td>100000</td>
      <td>0.000326</td>
    </tr>
    <tr>
      <th>4</th>
      <td>m1</td>
      <td>1000000</td>
      <td>0.003844</td>
    </tr>
    <tr>
      <th>5</th>
      <td>m2</td>
      <td>100</td>
      <td>0.000058</td>
    </tr>
    <tr>
      <th>6</th>
      <td>m2</td>
      <td>1000</td>
      <td>0.000174</td>
    </tr>
    <tr>
      <th>7</th>
      <td>m2</td>
      <td>10000</td>
      <td>0.001542</td>
    </tr>
    <tr>
      <th>8</th>
      <td>m2</td>
      <td>100000</td>
      <td>0.015132</td>
    </tr>
    <tr>
      <th>9</th>
      <td>m2</td>
      <td>1000000</td>
      <td>0.162051</td>
    </tr>
    <tr>
      <th>10</th>
      <td>m3</td>
      <td>100</td>
      <td>0.000035</td>
    </tr>
    <tr>
      <th>11</th>
      <td>m3</td>
      <td>1000</td>
      <td>0.000004</td>
    </tr>
    <tr>
      <th>12</th>
      <td>m3</td>
      <td>10000</td>
      <td>0.000013</td>
    </tr>
    <tr>
      <th>13</th>
      <td>m3</td>
      <td>100000</td>
      <td>0.000109</td>
    </tr>
    <tr>
      <th>14</th>
      <td>m3</td>
      <td>1000000</td>
      <td>0.001422</td>
    </tr>
  </tbody>
</table>
</div>




```python
df_result.pivot(index='count', columns='name', values='time').plot.line(legend=True, logx=True, logy=True)
```





![output_5_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186338/1f83a01b-0769-9ea8-196b-c970b8f8586e.png)



## uint32の場合

m3はuint8しか処理できなかったので実行してない

```python
ret = []
for name,func in zip('m1,m2'.split(','),[m1,m2]):
    for n in [10**2,10**3,10**4,10**5,10**6]:
        arr = np.random.randint(2**32-1,size=(n), dtype=np.uint32)
        ts = time.perf_counter()
        func(arr) # 実行
        ret.append({
                'name':name,
                'count':n,
                'time':time.perf_counter()-ts,
            })
df_result = pd.DataFrame(ret)
df_result
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }
    
    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>name</th>
      <th>count</th>
      <th>time</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>m1</td>
      <td>100</td>
      <td>0.000032</td>
    </tr>
    <tr>
      <th>1</th>
      <td>m1</td>
      <td>1000</td>
      <td>0.000099</td>
    </tr>
    <tr>
      <th>2</th>
      <td>m1</td>
      <td>10000</td>
      <td>0.000216</td>
    </tr>
    <tr>
      <th>3</th>
      <td>m1</td>
      <td>100000</td>
      <td>0.001684</td>
    </tr>
    <tr>
      <th>4</th>
      <td>m1</td>
      <td>1000000</td>
      <td>0.017679</td>
    </tr>
    <tr>
      <th>5</th>
      <td>m2</td>
      <td>100</td>
      <td>0.000047</td>
    </tr>
    <tr>
      <th>6</th>
      <td>m2</td>
      <td>1000</td>
      <td>0.000283</td>
    </tr>
    <tr>
      <th>7</th>
      <td>m2</td>
      <td>10000</td>
      <td>0.002625</td>
    </tr>
    <tr>
      <th>8</th>
      <td>m2</td>
      <td>100000</td>
      <td>0.026185</td>
    </tr>
    <tr>
      <th>9</th>
      <td>m2</td>
      <td>1000000</td>
      <td>0.258491</td>
    </tr>
  </tbody>
</table>
</div>



m1 10**6件は、uint8の４倍より遅くなってる。（効率悪化）


```python
df_result.pivot(index='count', columns='name', values='time').plot.line(legend=True, logx=True, logy=True)
```




![output_9_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186338/03dbd002-0936-2fea-300a-a7ba5354daeb.png)






## 結論

m3でuint8を処理するのが早そう

# GPUの場合

10e9はout of memoryなので実施してない

```python
def m4(a):  # ※uint8しか処理できない
    return cp.count_nonzero(cp.unpackbits(a))

ret = []
for name,func in zip('m1,m3,m4'.split(','),[m1,m3,m4]):
    for n in [10**2,10**3,10**4,10**5,10**6,10**7,10**8]:
        # arr = np.random.randint(255,size=(n), dtype=np.uint8)
        arr = cp.random.randint(255,size=(n), dtype=np.uint8)
        ts = time.perf_counter()
        func(arr) # 実行
        ret.append({
                'name':name,
                'count':n,
                'time':time.perf_counter()-ts,
            })
df_result = pd.DataFrame(ret)
df_result
```

```python
df_result.pivot(index='count', columns='name', values='time').plot.line(legend=True, logx=True, logy=True)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186338/93bf079f-f2e5-a75c-3bfd-7e2d9cc11a8b.png)

10e8 (100MB)でも0.1ms前後で、ほとんど差が出ない。