なぜlil_matrixとdok_matrixはdictsの一般的なdictに比べて遅いのですか？

Question

私は繰り返しスパース行列を構築したい、とscipyのダウンロードのドキュメントによると、このために2つの適切なオプションがあることに気づい：

LiL matrix：

クラスscipy.sparse.lil_matrix（引数1、形状=なし、dtype = None、 copy = False）[ソース]行ベースのリンクリストの疎行列

これは、疎行列 を段階的に構築するための効率的な構造です。

DoK matrix

：

クラスscipy.sparse.dok_matrix（ARG1、形状=なし、DTYPE =なし、 コピー=偽）[ソース]キーの辞書ベースの疎行列。

これは、疎行列 を段階的に構築するための効率的な構造です。

しかし、私は（後で簡単に疎行列に変換することができます）値の辞書の辞書を構築することに比較するベンチマークを実行しているとき、後者は約10〜20倍の速さのいずれかを使用してよりであることが判明疎行列モデル：

from scipy.sparse import dok_matrix, lil_matrix 
from timeit import timeit 
from collections import defaultdict 

def common_dict(rows, cols): 
    freqs = defaultdict(lambda: defaultdict(int)) 
    for row, col in zip(rows, cols): 
     freqs[row][col] += 1 

    return freqs 

def dok(rows, cols): 
    freqs = dok_matrix((1000,1000)) 
    for row, col in zip(rows, cols): 
     freqs[row,col] += 1 

    return freqs 

def lil(rows, cols): 
    freqs = lil_matrix((1000,1000)) 
    for row, col in zip(rows, cols): 
     freqs[row,col] += 1 

    return freqs 


def benchmark(): 
    cols = range(1000) 
    rows = range(1000) 

    res = timeit("common_dict({},{})".format(rows, cols), 
       "from __main__ import common_dict", 
       number=100) 

    print("common_dict: {}".format(res)) 

    res = timeit("dok({},{})".format(rows, cols), 
       "from __main__ import dok", 
       number=100) 

    print("dok: {}".format(res)) 

    res = timeit("lil({},{})".format(rows, cols), 
       "from __main__ import lil", 
       number=100) 

    print("lil: {}".format(res)) 

結果：

benchmark() 

common_dict: 0.11778324202168733 
dok: 2.2927695910912007 
lil: 1.3541790939634666 

それは行列モデルのためのそのようなオーバーヘッドが発生し、それをスピードアップするためにいくつかの方法があることは何ですか？ dokまたはlilのいずれかがdictsの一般的なdictよりも好む場合があります。それぞれの時間が半分にカットされている

for row, col in zip(rows, cols): 
    #freqs[row,col] += 1 
    freqs[row,col] = 1 

：私はあなたの2つのスパース配列のためのあなたの+=にちょうど=を変更

Answer 1

。最も時間を消費するのはインデックス作成です。 +=では、__getitem__と__setitem__の両方を実行する必要があります。

dokとlilが反復的な構成に適していると言われると、基本的なデータ構造を他の形式よりも拡張しやすくなります。

私はあなたのコードでcsr行列を作るしようとすると、私が手：

/usr/lib/python2.7/dist-packages/scipy/sparse/compressed.py:690：SparseEfficiencyWarning ：csr_matrixのスパース性構造を変更するのは高価です。 lil_matrixがより効率的です。 スパースエグゼクティブウォーニング）

と30倍の遅い速度です。

スピードの主張は、csrのようなフォーマットに相対的であり、純粋なPythonやnumpy構造に比べて相対的ではありません。

freq[r,c]を実行したときの動作を確認するには、dok_matrix.__get_item__とdok_matrix.__set_item__のPythonコードを参照してください。あなたのdokを構築する

---

より高速な方法は、次のようになります。

freqs = dok_matrix((1000,1000)) 
d = dict() 
for row, col in zip(rows, cols): 
    d[(row, col)] = 1 
freqs.update(d) 

dokがサブクラス化辞書であるという事実を利用して。 dokマトリックスは辞書の辞書ではありません。そのキーは(50,50)のようなタプルです。

同じスパースアレイを構築する別の高速な方法である：すなわち

freqs = sparse.coo_matrix((np.ones(1000,int),(rows,cols))) 

、すでに、rowsとcolsアレイ（または範囲）を有する対応dataアレイを計算し、次に構築以来希薄な配列。

ただし、漸進的な成長ステップの間にマトリックス上でスパース操作を実行する必要がある場合は、dokまたはlilが最適です。

---

スパース行列は、大きなスパース行列を持つ線形方程式を解くなどの線形代数問題のために開発されました。私は数年前にMATLABで有限差分問題を解くためにそれらを使用しました。その作業のためにフレンドリーな計算csrフォーマットが最終目標であり、cooフォーマットは便利な初期化フォーマットでした。

ここでは、多くのSO scipy sparse questionsがscikit-learnとテキスト解析の問題から発生しています。それらはまた生物学的データベースファイルでも使用されます。しかし、依然として(data),(row,col)定義方法が最適です。

スパース行列は高速インクリメンタル作成を意図したものではありませんでした。辞書やリストのような伝統的なPythonの構造は、そのためにはるかに優れています。

---

ここでは、辞書のメソッドを利用するより高速なdokの繰り返しがあります。 updateは普通の辞書ほど速く動作するようです。 getは、等価インデックス（freq[row,col]）の約3倍高速です。インデックス作成ではおそらくgetが使用されますが、オーバーヘッドが大きくなる必要があります。

def fast_dok(rows, cols): 
    freqs = dok_matrix((1000,1000)) 
    for row, col in zip(rows,cols): 
     i = freqs.get((row,col),0) 
     freqs.update({(row,col):i+1}) 
    return freqs 

getをスキップし、ちょうど

  freqs.update({(row,col): 1) 

を行うことでも高速です - （{(r, c):1 for r,c in zip(rows, cols)}）defaultdict例のdefaultdictよりも速く、そしてほぼ同じ速さで簡単な辞書の初期化

Answer 2

ありますあなたのテストが公正ではない様々な理由。まず、時間を計られたループの一部としてスパース行列を構築するオーバーヘッドを含めます。

第2に、おそらくもっと重要なのは、使用するように設計されたデータ構造を使用し、アレイ全体の操作を一度に行うことです。つまり、行と列を繰り返して毎回1を追加するのではなく、配列全体に1を加えるだけです。