2

隣接リストを使用して無向グラフを実装しようとしています。次のコードを使用しました。

int v,e;
scanf("%d%d",&v,&e);
list<int> graph[3000];
for(int i=0;i<e;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    graph[a].push_back(b);
    graph[b].push_back(a);
}

コードの実行時間をテストするために、3000 個の頂点と考えられるすべてのエッジを含む入力ファイルを作成しました。実行に2.2秒かかりました。以下のように二次元配列に変えて最適化してみました

int graph[3000][3000];

for(int i=0;i<e;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    graph[a][p[a]]=b;
    graph[b][p[b]]=a;
    p[a]++;
    p[b]++;
}

ここで、'p' はすべてゼロで初期化されたサイズ 3000 です。このコードは、同じ入力ファイルに対してわずか 0.35 秒で実行されました。gcc-4.3.2 コンパイラを使用しています。リストの末尾への挿入は一定時間で実行できることを知っていますが、最初のコードの実行が遅いのはなぜですか? リンクされたリストの実装を最適化する可能性はありますか?

前もって感謝します

4

3 に答える 3

7

避けてくださいstd::list。これは二重にリンクされたリストであり、キャッシュに非常に適さず (ノードはメモリ内でランダムに分散されます)、大きなオーバーヘッド (要素ごとに 2 つのポインター) を伴います。したがって、何かを追加するたびに、リストは2*sizeof(void*)+sizeof(int)バイトを割り当て、さらにメモリ管理オーバーヘッドoperator new.

アルゴリズムの後半で、値を反復処理するときに、文字通りメモリ全体をジャンプすることになり、これはさらに遅くなります。

2 次元配列にはこの問題はありませんが、いくらかのメモリを浪費します。

私は通常、隣接リストをベクトルのベクトルとして表します。

std::vector<std::vector<int> > graph;

vector もpush_back値を指定できることに注意してくださいO(1)( と同様に、std::dequeより高速に追加できますが、トラバース時は遅くなります)。グラフが密であることが予想される場合は、隣接行列を選択することをお勧めします。

于 2013-04-06T20:31:11.363 に答える
6

Insertion into a list requires allocating a new node. So when you're doing your 6000 push-backs, you have to do 6000 memory allocations. In the array case, you don't have to do any allocations at all, so that's a lot faster. That's the full difference.

于 2013-04-06T20:21:44.517 に答える
0

ここでの回答を拡張するには、リンクされたリスト クラスを自分で実装すると、遅い理由がわかります。

容量値、サイズ値、および実際のリストの最初のノードを指すポインターを含むリストを実装するなど、実行できることがあります。そのポインターは実際には動的配列であり、size==capacity の場合、配列のサイズが変更され、容量が何らかの係数 (たとえば 10) だけ増加します。

欠点は、2^(sizeof capacity * CHAR_BIT) - 1 要素に制限されることです。これに対して、毎回ノードを割り当てるだけでは挿入時間が長くなり、理論的に無制限のノード数という利点があります。より高速なリスト実装の容量を使い切る前にメモリが不足する可能性が最も高いですが、その保証はありません。言うまでもなく、リストのサイズ変更には通常、リストのコピーを作成する必要があるため、容量の最大値が突然大きくなりますとにかく制限が小さい。

リンクされたリストは一般的に遅いです。それらには用途がありますが、高速な実行時間が必要な場合は、より良い実装を見つけるか、std::vector などの別のコンテナーを使用するか、自分でソリューションを作成しますが、正直なところ、標準のコンテナーはかなりうまく機能します。

于 2013-07-04T17:22:14.220 に答える