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在 STL 中有一个#include <map>. 然后你需要两个Map对象而不是你的vectors. 实现是相似的，但是当你执行比较时会更容易，而且你只能有一个循环。您的代码目前O(n^3)将减少到O(n * log n)最好的情况，O(n^2)在最坏的情况下。

于 2012-07-19T12:46:24.323 回答
2

可能在 a 中按值存储边会更有效vector，当您需要删除edge索引处的say时，i您可以通过用ia 中的最后一个替换边vector并弹出最后一个来做到这一点

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

move semantics如果使用for会更高效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 回答