1

隣接行列 (100k x 100k 以上) として表している大規模なスパース グラフがあり、エッジの配列として格納されています。(非スパース) 4 x 4 行列の例:

0 7
4 0

example_array = [ [7,1,2], [4,2,1] ]

たとえば、[4,1,2] は、ノード 1 からノード 2 への値/重み 4 の有向エッジがあることを示します。マトリックス用語では、これは本質的に [値、行、列] です。

また、この「エッジの配列」は最初の要素でソートされます。上記の例では、ソート後、配列は次のようになります。

example_array = [ [4,2,1], [7,1,2] ]

問題

特定の値 について、iこの並べ替えられた「エッジの配列」内のすべての要素を、2 番目の値が に等しいものとして検索する必要がありますi。jつまり、そのようなものを見つけますexample_array[j][1] = i。

これの私の予備的な実装は、各要素の 2 番目の値を と比較して、配列内のすべての要素を単純に反復することiです。これは、ループする要素がまだたくさん (たとえば 500k) ある可能性があるため、計算コストが高くなります。

質問

これを行うより効率的な方法はありますか？マトリックス/グラフの別の表現を使用してもかまいません。私はこれをCで書いています。

追加情報

これは本質的に、ノードのすべての隣接ノードiとそれらのエッジの重みを見つけることです。iつまり、エッジ リストから、別のノードへのすべての有向エッジを検索します。

4

3 に答える 3

1

そのためには、おそらくスパース圧縮行ストレージを使用する必要があります。簡単に言えば、行列を行ごとに格納するため、2 つの (行、列) インデックスを保持する必要はありません。代わりに、行ポインタ、つまり特定の行がメモリ内のどこから始まるかを示す配列を保持します。次に、その行のゼロ以外の列の位置を示す列ベクトル (col_ind) を保持し、対応する値 (val) を格納します。これにより、ストレージ要件が削減されますが、すべての行の col_ind がソートされるため、マトリックス検索も高速化されます。したがって、行列のすべての行に直接アクセスでき、二分法または選択したその他のソートされたリスト検索を使用して、すべての行内のエントリをすばやくローカライズできます。

CRS マトリックスは、ソートされたリストへの挿入を使用してすばやく作成できます。たとえば、すべてのマトリックス エントリの (i,j) 座標を明示的に作成した場合は、バケット ソートを使用できます。MATLAB では、'sparse' 関数を使用してこれを行うことができます。自分でコーディングしたくなくてライブラリが必要な場合は、Tim Davis による SuiteSparseをご覧ください。

CRS 形式の簡単な説明については、たとえばここを参照してください。ただし、他にも何千ものソースがあります。

編集変更された CRS ストレージを使用して、必要なことを簡単に行うことができます。まず、通常行われているように、列インデックスではなく値で各行内の列を並べ替えて、マトリックスを作成する必要があります。これは、各行の最小値がすべての行の最初のエントリとして格納されることを意味します。次に、グローバルに最小の値を見つけるために、すべての行の最初のエントリを検索します (O(n) の複雑さ)。最小値を含む行の最初の列インデックスを読み取ることにより、対応する列インデックスを一定時間で取得することがわかっています。行ポインタのおかげで行がメモリ内のどこから始まるかを知っているので、すべてを行うことができます。

このコードを見ることができます。Cで実装されたmatlab用のmexファイルのセットです。興味があるのはsparse_create_mex.cです。ソートされたリストへの (i, j, 値) の反復加算を使用して、疎行列構造を作成します。ソートされたリストを少し変更する必要があります-現在、整数の列インデックスと double 値に対して実装されています。ソート済みリストはマクロ テンプレートとして実装されているため、新しいソート済みリスト タイプを宣言するだけで済みます (sorted_list.h および sorted_list_templates.h を参照)。

于 2012-09-26T08:01:46.107 に答える
0

ポインターを使用することの何が問題になっていますか?

// A list of edges emanating from one node.
typedef struct {
    int weight;    
    int nodeId;    // The target node
    Edge *next;    // Next edge in the list
} Edge;

typedef struct {
    int nodeId;
    Edge *edges;   // This node's edge list
} Node;

// Now just store all your nodes in an array
Node *example_array[MAX_NODES];

ノードにエッジを挿入するときは、そのedgesリストに重みで順序付けされた挿入を行います。ここで、あるノードから始まるすべてのエッジの検索に関する質問に答えるには、配列内でそのノードを検索し、そのエッジ リストをトラバースするだけです。ボーナスは、グラフの他の部分を検索することなく、ソートされた順序でエッジにアクセスできることです。

于 2012-09-25T22:39:24.573 に答える
0

表現を変更してもかまわない場合は、2 番目の要素で並べ替えると、計算量が少なくなります。これは、ステップスルーして i よりも大きい要素を見つけたら完了だからです。最悪の場合、考えられる最良のアルゴリズムは O(n) ですが、2 番目の要素で並べ替えると、予想どおり n/2 時間で実行されます。

于 2012-09-25T22:14:35.140 に答える