[Numpy]2次元行列(ndarray)の要素にlistを持たせる方法


# TL;DR
openCVで画像データを取り扱っていたとき、「各ピクセルごとに何かしらの情報を持たせたい」というケースが生じました。
処理の高速化を図るため画像データに対応した2次元行列を作り、ハッシュ法のように座標を要素数としO(1)でリストの最初の要素にアクセスできるようなデータの取扱いが理想です。
しかし、持たせるデータが各ピクセルに対してただ一つの数値型であれば普通にndarrayを利用できますが、持たせたいデータが辞書型やData Classesのときはそうは行きません。

さらにピクセルごとに複数の情報を持たせたいという今回ケースでは、可変な配列を扱いたくなります。次元を増やすというアプローチは適切ではないでしょう。

2次元行列の要素にlistを持たせる方法が存在したので記事にまとめました。
# 実装
numpy行列を初期化する際、要素の型を指定できます。浮動小数を取り扱いたい場合、dtype=floatなどと指定しますが引数をdtype=objectとすることでオブジェクト型の指定が可能です。

```python
arr = np.empty((3, 4), dtype=object)
```

## np.frompyfunc()で行列定義と要素をlistで初期化する
frompyfunc()を利用することで、全要素をpythonのlistオブジェクトで初期化できるようです

https://stackoverflow.com/questions/57364197/how-to-initialize-numpy-array-of-list-objects/

```python
import numpy as np

arr = np.frompyfunc(list, 0, 1)(np.empty((3, 4), dtype=object))
print(arr)
```
- 結果
```
[[list([]) list([]) list([]) list([])]
 [list([]) list([]) list([]) list([])]
 [list([]) list([]) list([]) list([])]]
```


## インデックス(座標)を指定してリストに要素を追加する
```python
import numpy as np

arr = np.frompyfunc(list, 0, 1)(np.empty((3, 4), dtype=object))
# インデックスを指定して行列要素であるlistに要素を追加
arr[2, 3].append({"a": 50, "b": 100}) #辞書型の要素を追加している
arr[0, 0].append({"a": 50, "b": 100})

print(arr)
```
- 結果
```
[[list([{'a': 55, 'b': 100}]) list([]) list([]) list([])]
 [list([]) list([]) list([]) list([])]
 [list([]) list([]) list([]) list([{'a': 55, 'b': 100}])]]
```

## インデックス(座標)を指定してlist取得・リスト要素を取得する
前置きでも述べたように、ある座標のピクセルの情報を取得したい時O(1)でそのリストにアクセスできます。
```python
import numpy as np

arr = np.frompyfunc(list, 0, 1)(np.empty((3, 4), dtype=object))

# インデックスを指定してlistに要素を
arr[2, 3].append({"a": 50, "b": 100})
arr[2, 3].append({"a": 150, "b": 200})

# a[2, 3]でlistにアクセス可能
for item in a[2, 3]:
    print(item)# listの要素ごとに出力
```
```
{'a': 50, 'b': 100}
{'a': 150, 'b': 200}
```


# スライスでインデックス範囲指定してlist取得する
今回なぜ、2Darray in listでのデータ管理が出来ないか調査したかというと
「クリック座標の周辺で、ピクセルの持つ情報がある条件を満たすもののみ取得する」というロジックが必要で、総当たりをせず処理を高速化するにはどうするか、ということを考えたためでした。

このケースは「クリック座標の周辺」ということでスライスが有効に利用できました。
```python
import numpy as np

arr = np.frompyfunc(list, 0, 1)(np.empty((3, 4), dtype=object))

arr[0, 0].append({"color": "red"})
arr[1, 1].append({"color": "green"})
arr[1, 1].append({"color": "blue"})
arr[2, 0].append({"color": "red"})
arr[2, 3].append({"color": "blue"})

for item in np.ravel(arr[0:3, 0:2]): # スライスで範囲切り出し(x座標0~2px、y座標0~1pxの範囲 )
    print(item)
```

```
[{'color': 'red'}]
[]
[]
[{'color': 'green'}, {'color': 'blue'}]
[{'color': 'red'}]
[]
```


# メモリ使用量が多すぎる問題

```python
import numpy as np

get_size = sys.getsizeof(
    np.empty((3, 4), dtype=object)
)

print(get_size)
# 224
```
試してみてわかったことですが、2Darray in listという実装ではメモリ消費量が結構エグいです。
pythonオブジェクトを要素とした3x4行列で224バイトのメモリを消費するようです。
おそらく（128 + 要素数*8）byteのメモリを必要とするっぽい。
さらに要素ごとのlistオブジェクトの確保にメモリを消費することになります。空のlistであっても56byteは使ってるようです。

なおlistオブジェクトは線形リストなどではない動的配列であるという意見がありました。

https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented

2Darray in listをC言語で実装するとしたら、
listオブジェクトの部分は線形リストで実装し、ndarrayに該当するオブジェクトは　「横幅x縦幅xポインタサイズ(64bitOSで8byte)」のメモリを確保して、線形リストへのポインタを格納する、というような仕様が考えられます。

空のlistはインスタンス化しないため、余計なメモリを消費せずにすむ設計が可能であり、
また、2Darrayオブジェクトに行列サイズ等のメンバを持たせるとしても128byteも消費せずにすむはず…ですが、numpyを利用した2Darray in listの実装では「俺の考えた最強の設計」に即したものにはならないようです。

本記事の否定になってしまいますが😅2Darray in listのようなイレギュラーな実装はおすすめできないかもしれません。

ただ、np.empty()のdtypeの引数にpythonオブジェクトを指定できるため、listを要素にもたせることは間違っていることでは無いはず。

# おわりに
今回のような「各ピクセルごとに何かしらの情報を持たせたい」という特殊な事例で活用できると思います。

numpyではこのような実装も可能、という１つの事例をご紹介できたかなと思います。