具有高效的「刪除」功能的數據結構

Question

我正在尋找方法來改善我的代碼中的性能瓶頸。 在我的代碼中，我構建了一個圖形，其中每個頂點維護傳出和傳入邊的列表。什麼是殺死我的代碼的表現是這些邊緣經常從列表中移除。

目前，我的實現是使用C++的STL庫中可用的列表。所以我想知道是否有任何數據結構提供了有效的刪除功能。

以下是代碼的部分，其中頂點的刪除發生。您可以在外循環的每次迭代中看到
（* 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() 
{ 

} 

Answer 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; 

Answer 2

的最有效方式，以delete \ compare \ insert \ search正在使用HashTables。在STL中有一個#include <map>。那麼你需要兩個Map對象而不是你的vectors。實現類似，但是當你執行比較時，它會更容易，而且你也只能有一個循環。您的編碼目前爲O(n^3)，最多可減至O(n * log n)，最差情況下可減至O(n^2)。

Answer 3

可能會更有效地存儲由值邊緣在vector，當你需要刪除edge說在指數i您可以通過最後一個在vector更換i邊緣和彈出最後做一個

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

如果使用move semantics爲edge