1

重み行列の値から始まる行列を作成する必要があります。マトリックスを作成するときと反復するときの両方の速度の観点から、マトリックスを保持するのに最適な構造はどれですか? リストのリストまたはnumpy 2D配列について考えていましたが、どちらも遅いようです。必要なもの:

numpy array
A = np.zeros((dim, dim))
for r in range(A.shape[0]):
    for c in range(A.shape[0]):
        if(r==c):
            A.itemset(node_degree[r])
        else:
            A.itemset(arc_weight[r,c])

また

list of lists
l = []
for r in range(dim):
    l.append([])
    for c in range(dim):
        if(i==j):
            l[i].append(node_degree[r])
        else:
            l[i].append(arc_weight[r,c])

ここで、dim は 20000 にすることもできます。node_degree はベクトルで、arc_weight は別の行列です。私はC ++で書きました.0.5秒未満しかかかりませんが、他の2つはPythonで20秒以上かかります. Python が C++ ではないことは知っていますが、できるだけ速くする必要があります。皆さん、ありがとうございました。

4

3 に答える 3

4

1 つのことは、リストのサイズが既にわかっている場合は、リストに追加するべきではないということです。

Python < 3.x を使用しているため、リスト内包表記を使用して最初にメモリを事前に割り当て、代わりに をr, c使用して値を生成します (こちらを参照)。xrange()range()

l = [[0 for c in xrange(dim)] for r in xrange(dim)]

さらに良いことに、以下を使用して、必要なものを一発で構築できます。

l = [[node_degree[r] if r == c else arc_weight[r,c] 
            for c in xrange(dim)] for r in xrange(dim)]

元の実装と比較すると、メモリの使用量が少なくなり (xrange()ジェネレータが原因で)、事前に次元を指定してメモリを再割り当てする必要がなくなるため、時間も短縮されます。

于 2014-05-29T17:47:05.187 に答える
0

Numpy 行列は、次元とエントリ タイプを知っているため、一般的に高速です。

あなたの特定の状況では、arc_weight と node_degree の行列が既に作成されているため、arc_weight から直接行列を作成し、対角線を置き換えることができます。

A = np.matrix(arc_matrix)
np.fill_diagonal(A, node_degree)

もう 1 つのオプションは、二重ループを、各位置に正しい要素を配置し、関数から行列を作成する関数に置き換えることです。

def fill_matrix(r, c):
    return arc_weight[r,c] if r != c else node_degree[r]

A = np.fromfunction(fill_matrix, (dim, dim))

経験則として、numpy を使用すると、ループを何としてでも回避する必要があります。最初の方法の方が高速ですが、両方をプロファイリングして、どちらが適切かを確認する必要があります。また、メモリ内でデータセットを複製しているように見えることも考慮に入れる必要があります。そのため、データセットが本当に巨大な場合、問題が発生する可能性があります。最良のアイデアは、arc_weight と node_degree を完全に回避して、マトリックスを直接作成することです。

編集：リストの理解とnumpyマトリックスの作成の間のいくつかの簡単な時間比較。arc_weight と node_degree がどのように定義されているかわからないので、2 つのランダム関数を作成しました。numpy.fromfunction関数に条件があると少し不満があるように見えるので、2 つのステップで行列を作成します。

import numpy as np

def arc_weight(a,b):
    return a+b

def node_degree(a):
    return a*a

def create_as_list(N):
    return [[arc_weight(c,r) if c!=r else node_degree(c) for c in xrange(N)] for r in xrange(N)]

def create_as_numpy(N):
    A = np.fromfunction(arc_weight, (N,N))
    np.fill_diagonal(A, node_degree(np.arange(N)))
    return A

そして、ここでのタイミングN=2000：

time A = create_as_list(2000)
CPU times: user 839 ms, sys: 16.5 ms, total: 856 ms
Wall time: 845 ms

time A = create_as_numpy(2000)
CPU times: user 83.1 ms, sys: 12.9 ms, total: 96 ms
Wall time: 95.3 ms
于 2014-05-29T18:10:11.007 に答える
0

のコピーを作成しarc_weight、対角線を の値で埋めますnode_degree。20000 x 20000 の出力の場合、私のマシンでは約 1.6 秒かかります。

>>> import numpy
>>> dim = 20000
>>> arc_weight = numpy.arange(dim**2).reshape([dim, dim])
>>> node_degree = numpy.arange(dim)
>>> import timeit
>>> timeit.timeit('''
... A = arc_weight.copy()
... A.flat[::dim+1] = node_degree
... ''', '''
... from __main__ import dim, arc_weight, node_degree''',
... number=1)
1.6081738501125764

配列を取得したら、それを繰り返し処理しないようにしてください。ブロードキャストされたオペレーターや NumPy の組み込み関数と比較すると、Python レベルのループはパフォーマンスの惨事です。

于 2014-05-31T09:31:36.377 に答える