【python】標準データ型での二次元配列の表現あれこれのアクセス速度

はじめに

　俗に言う「二次元配列」を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)が強かったです。