隣接リストを使用して無向グラフを実装しようとしています。次のコードを使用しました。
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 コンパイラを使用しています。リストの末尾への挿入は一定時間で実行できることを知っていますが、最初のコードの実行が遅いのはなぜですか? リンクされたリストの実装を最適化する可能性はありますか?
前もって感謝します