1

80513個のノードと5899882 個のエッジに対して隣接行列が機能しないと判断した後、adjacency listを適用することにしました。これは、隣接リストの最初の実装であり、基本的にはベクトルのベクトル メソッドを適用することにしました。

したがって、たとえば、vectorOfVectors[5]には、隣接ノード5を含む隣接ノードが含まれます。私が使用しているデータセットはここにあります

現在、私はこのコードを書き、エラーなしで動作しますが、私のコンピューターでは 26 秒かかります (6 GB RAM の i5 2.4、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

より良いアプローチはunordered_set、ノード インデックス ペアです (ペアは常に小さい方のノードを最初にリストします)。

于 2012-04-10T22:22:15.053 に答える
0

adjacencyList.reserve(numberOfNodes) を使用して、adjacencyList のメモリを事前に割り当てることができます。これにより、不要なメモリ割り当てとデータのコピーが削減されます。

また、デバッグ モードの Visual Studio では、STL ランタイムがすべての反復子を追跡するため、巨大なコンテナーの処理が遅くなることがあります。Debug/Release の桁違いは珍しくありません。詳細については、「デバッグ イテレータのサポート」を調べてください。

于 2012-04-10T22:49:30.170 に答える