はじめに
俗に言う「二次元配列」をpythonで表現しようとすると、listのlistで書くというのが一番最初に思いつくやり方だと思います。
速度のこととか考えるとどうやるのがいいのか？ ということは実はあまり知らなかったので、この際いろいろ試してみます。
調査対象
こんなのを考えます。
list of list(s)
リストのリスト。王道ですな。
dict of dict(s)
実はdictでもindexを整数にすれば、インデックスでアクセスするぶんにはlistと同じような使い方ができます。メモリ効率は悪いですが。
flat list
一つのリストで表現して、一行あたりのデータ数をnとして、i*n+jみたいな方法でアクセスする。
flat dict
listと同じやり方でもいいし、i, jのようなtupleをキーにするとnumpyっぽく使えます。d[0, 1]とか。
実験
要素取得の時間だけ見ることにします。
とりあえず、こうやって5種類のデータを作る。アクセス手段も用意する。
def generate_data(n, m): data1 = [[None for _ in range(m)] for _ in range(n)] data2 = {i:{j:None for j in range(m)} for i in range(n)} data3 = [None for _ in range(n*m)] data4 = {i:None for i in range(n*m)} data5 = {(i, j):None for i in range(n) for j in range(m)} return data1, data2, data3, data4, data5 def access1(a, i, j, m=None): return a[i][j] def access2(a, i, j, m=None): # 本当にmが要るのはこれだけだが、他も合わせないと面倒なのでキーワード引数に return a[i*m + j] def access3(a, i, j, m=None): return a[i, j]
あとは素直に時間を測る。
import time from itertools import product def generate_datas(n, m): data1 = [[None for _ in range(m)] for _ in range(n)] data2 = {i:{j:None for j in range(m)} for i in range(n)} data3 = [None for _ in range(n*m)] data4 = {i:None for i in range(n*m)} data5 = {(i, j):None for i in range(n) for j in range(m)} return data1, data2, data3, data4, data5 def access1(a, i, j, m=None): return a[i][j] def access2(a, i, j, m=None): return a[i*m + j] def access3(a, i, j, m=None): return a[i, j] def main(): names = ["list of list", "dict of dict", "flat list", "flat dict1", "flat dict2"] accessors = [access1, access1, access2, access2, access3] for n in [10, 100, 500, 1000]: print(n) datas = generate_datas(n, n) for name, data, acc in zip(names, datas, accessors): # 転置なし t1 = time.time() for _ in range(10): for i, j in product(range(n), range(n)): acc(data, i, j, n) t2 = time.time() print(f"{name:12}", "N", f"{t2 - t1:.6f}") # 転置してアクセス t1 = time.time() for _ in range(10): for i, j in product(range(n), range(n)): acc(data, j, i, n) t2 = time.time() print(f"{name:12}", "T", f"{t2 - t1:.6f}") if __name__ == "__main__": main()
結果。
10 list of list N 0.000175 list of list T 0.000168 dict of dict N 0.000190 dict of dict T 0.000174 flat list N 0.000170 flat list T 0.000171 flat dict1 N 0.000178 flat dict1 T 0.000197 flat dict2 N 0.000208 flat dict2 T 0.000206 100 list of list N 0.015498 list of list T 0.014792 dict of dict N 0.014171 dict of dict T 0.018824 flat list N 0.015062 flat list T 0.015838 flat dict1 N 0.018054 flat dict1 T 0.017563 flat dict2 N 0.017370 flat dict2 T 0.018839 500 list of list N 0.347277 list of list T 0.360864 dict of dict N 0.397702 dict of dict T 0.622734 flat list N 0.395908 flat list T 0.428421 flat dict1 N 0.463291 flat dict1 T 0.552635 flat dict2 N 0.568813 flat dict2 T 0.812436 1000 list of list N 1.410052 list of list T 1.541770 dict of dict N 1.608992 dict of dict T 2.762586 flat list N 1.595022 flat list T 1.725559 flat dict1 N 1.846365 flat dict1 T 2.526936 flat dict2 N 3.238760 flat dict2 T 4.195801
得られる知見としては、
- flatな表現は遅い。おそらくintのインデックス計算、またはtupleオブジェクトの生成が遅いから。
- dict表現版は小さいテーブルならそこそこいけるが、大きくなると辛い。また、転置してアクセスすると劇的に遅い（おそらくキャッシュなどの絡みで）
といったあたりがあり、いずれにせよほぼ常に最速だったのはlist of list(s)なので、結論としては素直にそれで良いということになりそうです。
つまらない結論ですね・・・
結論
list of list(s)が強かったです。