PythonでCの拡張子を持たない高速の2次元配列（行列）

Question

Python 2.7を使って拡張可能なアプリケーションのプラグインを書く必要があります。これは、整数の直角行列上で動作する、かなり複雑な動的アルゴリズムを実行する必要があります。

そのアプリケーションに付属するデフォルトのPythonインストールにはnumpyのような数値ライブラリが含まれていないので、残念ながらPythonのstdlibだけを使用して実装する必要があります。

Iメモリに行列を表すために、いくつかの異なるアプローチを試みた：

values = defaultdict(int) 
values = [[0 for _ in range(width)] for _ in range(height)] 
values = [0] * (width * height) # access like values[j*width + i] later 
values = [[0] * width for _ in range(height)] 

辞書アプローチは完全性のためにだけ存在し、すべての要素がアクセスされるので、それは実際には非常に有益ではありません。

私の測定では、最後のものがビルドとアクセスが最も速いようです。しかし、私は組み込みの行列機能がないことに驚いています。これまでに私がPythonについて学んだことから、stdlibで明白な機能が見つからない場合は、あなたが一生懸命見ていない可能性が最も高いでしょう。

これは、例えばarrayモジュールや私が気付いていない他の機能を使って、これをさらに最適化できるかどうか疑問です。

Answer 1

がarrayモジュールは、速いかもしれませんが。それはvalues[j*width + i]の規則で使用することができます。しかし、おそらく、（a）Numpyがすでにそのニッチを効果的に埋めているため、（b）パフォーマンスが最優先でない場合にリストのリストを作ることができるため、Python標準ライブラリには多次元配列はありません。

最も速いオプションは実際にアルゴリズムに依存します。 dictベースのアプローチは、処理している行列が非常にまばらな（実際にはDPアルゴリズムでは、少なくとも私が見たものではない）ときに、実際には最も速いかもしれません。

Answer 2

あなたは、Pythonの配列で、デフォルトの辞書を使用して、インデックスとして2タプルを使用するか、またはカスタムクラスを実装し、指標として2つのタプルに対処する__getitem__と__setitem__メソッドを実装し、その結果を格納することができ、次のいずれか

を

from array import array 
class Array2D(object): 
    def __init__(self, w, h): 
     self.data = array("f", [0] * w * h) 
     self.width = w 
    def __getitem__(self, index): 
     return self.data[index[1] * self.width + index[0]] 
    def __setitem__(self, index, value): 
      self.data[index[1] * self.width + index[0]] = value 

または、defaultdictを使用して、あなたがより良いパフォーマンスを得る可能性があります：行列が大きくなるとき、それはよりコンパクトに値をパックすることができますので、

>>> from collections import defaultdict 
>>> d = defaultdict(lambda : 0) 
>>> d[0,0] 
0 
>>> d[0,0] = 2.5 
>>> d[0,0] 
2.5 
>>>