1

在确定邻接矩阵不适用于80513个节点和5899882 个边之后，我决定应用adjacency list。这是我第一次实现邻接表，基本上我决定应用向量方法的向量。

因此，例如，vectorOfVectors[5]将包含邻居节点5的邻居。我正在使用的数据集可以在这里找到

目前我已经编写了这段代码，它可以正常工作，但是在我的计算机上需要 26 秒（i5 2.4，6 gb ram，运行 Win7）。我想知道是否可以改进我的代码以降低分配速度。

PS：我正在使用fstream库并从.csv文件中读取。

#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>

using namespace std;

int main()
{
    ifstream file("edges.csv");
    string word="",data="";
    getline(file,word);
    int arrTemp[3];
    int numberOfNodes=atoi(word.c_str());
    vector<int>temp;
    vector< vector<int> >adjacencyList;

    for(int i=0;i<numberOfNodes;i++)
    {
        adjacencyList.push_back(temp);
    }
    while(file.good() && getline(file,word))
    {
        //cout<<word<<endl;
        if(word.size()>0)
        {
            for(int i=0;i<3;i++)
            {
                int cutFrom=word.find_first_of(',');
                arrTemp[i]=atoi(word.substr(0,cutFrom).c_str());
                word=word.substr(cutFrom+1,word.length());
            }
            //cout<<arrTemp[0]<<" "<<arrTemp[1]<<endl;
            adjacencyList[arrTemp[0]-1].push_back(arrTemp[1]-1);

        }
        else
            break;
    }

    cout<<"Vector size:"<<adjacencyList[1].size()<<endl;
    return 0;
}
4

2 回答 2

0

您可以使用 adjacencyList.reserve(numberOfNodes) 为 adjacencyList 预分配内存。这将减少不必要的内存分配和数据复制。

同样在调试模式下的 Visual Studio 中，STL 运行时会跟踪所有迭代器，这有时会使处理大型容器的速度变慢。调试/发布之间的数量级并不少见。研究“调试迭代器支持”以获取更多信息。

于 2012-04-10T22:49:30.170 回答
0

更好的方法是unordered_set节点索引对（其中对总是首先列出较小的节点）。

于 2012-04-10T22:22:15.053 回答