0

コードのパフォーマンスのボトルネックを改善する方法を探しています。私のコードでは、各頂点が発信エッジと着信エッジのリストを維持するグラフを作成します。そして、私のコードのパフォーマンスを低下させているのは、これらのエッジがリストから頻繁に削除されるという事実です。

現在、私の実装では、C++のSTLライブラリで利用可能なリストを使用しています。そこで、効率的な削除機能を提供するデータ構造があるかどうか疑問に思いました。

以下は、頂点の削除が行われるコードのセクションです。外側のforループ
（* inedge_it）-> src-> out_edges.remove（* inedge_it）が呼び出されるたびに、着信エッジのリストから（* inedge_it）が削除されることがわかります。同様に、内側のforループ（* outedge_it）-> tgt-> in_edges.remove（* outedge_itが呼び出され、出力エッジのリストから（* outedge_it）が削除されます。

int dag_vertex::eliminate( int & edge_counter )
{
    int nMults = 0;

    list<dag_edge*>::iterator inedge_it;
    list<dag_edge*>::iterator outedge_it;

    int m = in_edges.size();
    int n  = out_edges.size();

    for( inedge_it=in_edges.begin() ; inedge_it!=in_edges.end() ; inedge_it++ )
    {
        (*inedge_it)->src->out_edges.remove(*inedge_it);

        for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )
        {
            (*outedge_it)->tgt->in_edges.remove(*outedge_it);

            double cij = (*inedge_it)->partial*(*outedge_it)->partial;

            nMults++;

            dag_edge * direct_link = NULL;

            list<dag_edge*>::reverse_iterator src_outedge_it;

            for( src_outedge_it=(*inedge_it)->src->out_edges.rbegin() ; src_outedge_it!=(*inedge_it)->src->out_edges.rend() ; src_outedge_it++ )
            {
                if( (*src_outedge_it)->tgt==(*outedge_it)->tgt )
                {
                    direct_link = (*src_outedge_it);
                    break;
                }
            } 

            if(direct_link)
            {
                direct_link->partial += cij;
            }else
            {
                (*outedge_it)->tgt->add_in_edge( (*inedge_it)->src , cij );
                edge_counter++;
            }
        }

        delete (*inedge_it);    
    }

    for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )
    {   
        delete (*outedge_it);
    }

    in_edges.clear();
    out_edges.clear();

    edge_counter -= (m+n);

    return nMults;
}

着信エッジを追加するための関数の定義は次のとおりです

dag_edge* dag_vertex::add_in_edge(dag_vertex* src , double partial)
{
    dag_edge* the_in_edge= new dag_edge(src, this, partial);
    in_edges.push_back(the_in_edge);
    src->out_edges.push_back(the_in_edge);
    return the_in_edge;
}

以下はdag_edgeの定義です。 

dag_edge::dag_edge(class dag_vertex* s, class dag_vertex* t, double cij) : 
src(s), tgt(t), partial(cij),alive(true)
{

}

dag_edge::~dag_edge()
{
     //std::cout<<"~dag_edge("<<src->idx<<","<<tgt->idx<<")"<<std::endl;
}

dag_vertex* dag_edge::getsrc()
{
    return src;
}

dag_vertex* dag_edge::gettgt()
{
    return tgt;
}

void dag_edge::dump_to_dot(FILE* file)
{
    fprintf(file,"%d->%d [label=\"%f\"]\n",src->idx, tgt->idx, partial); 
}

void dag_edge::display() 
{

}
4

3 に答える 3

2

delete\ compare\ insert\への最も効率的な方法searchは、HashTablesを使用することです。STLには。があり#include <map>ます。Map次に、の代わりに2つのオブジェクトが必要ですvectors。実装は似ていますが、比較を実行すると簡単になり、ループを1つだけ持つことができます。あなたのコードは現在、せいぜい、そして最悪の場合O(n^3)に削減されるでしょう。O(n * log n)O(n^2)

于 2012-07-19T12:46:24.323 に答える
2

おそらく、エッジを a の値で保存する方が効率的であり、 say at インデックスvectorを削除する必要がある場合は、エッジを a の最後のものに置き換えて最後のものをポップすることでそれを行うことができますedgeiivector

edges[i] = edges.back();
edges.pop_back();

move semanticsforを使用すると、さらに効率的になります。edge

于 2012-07-19T12:58:54.100 に答える
1

あなたは実際に必要以上にremoveを呼び出しています：

for( inedge_it=in_edges.begin() ; inedge_it!=in_edges.end() ; inedge_it++ )
{
    (*inedge_it)->src->out_edges.remove(*inedge_it);

    for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )
    {
        (*outedge_it)->tgt->in_edges.remove(*outedge_it); // This has no dependence on inedge_it

基本的に、ターゲットから入力エッジを複数回削除しようとするため、すでに削除されているエッジを見つけるのに多くの時間がかかります。

別のループに抽出できます。

for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )
{
   (*outedge_it)->tgt->in_edges.remove(*outedge_it);
}

for( inedge_it=in_edges.begin() ; inedge_it!=in_edges.end() ; inedge_it++ )
{
    (*inedge_it)->src->out_edges.remove(*inedge_it);

    for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )
    {
        double cij = (*inedge_it)->partial*(*outedge_it)->partial;
于 2012-07-19T13:10:29.410 に答える