2

一部の C++ プロジェクトでは、さまざまな性質のグラフを表すオブジェクトを扱っています。これらはすべて、共通の抽象的なインターフェースを実装しています。この投稿では、これを 1 つの関数に減らします。

class graph {
public:
   ...
   // Create an iterator over the successors of v
   virtual succ_iterator* succ(const vertex* v) const = 0;
   ...
};

このsucc_iteratorクラスは、 の後続の頂点を反復処理できるようにする抽象クラスでもありvます。

class succ_iterator {
public:
   virtual void first() = 0;               // reset the iterator
   virtual void next() = 0;                // move to next successor
   virtual bool done() const = 0;          // no more successor left?
   virtual const vertex* dest() const = 0; // destination vertex
};

vしたがって、グラフ内のすべての後継に対するループは次のgようになります。

succ_iterator* i = g->succ(v);
for (i->first(); !i->done(); i->next()) {
   // use i->dest()
}
delete i;

私はこのようなループを頻繁に使用して、グラフ アルゴリズムを実装しています。コードをプロファイリングすると、これらの小さな反復子インスタンスにメモリを割り当てるのに多くの時間を費やしていることが明らかになったので、これを改善するためのアイデアを聞きたいです。

残念ながら、私のグラフは非常に異なる実装を持つ可能性があるため、各グラフには独自のsucc_iteratorインターフェース実装がある可能性があります。基本的に、階層内の各クラスには、graph階層内に対応するクラスがありsucc_iteratorます。たとえば、std::vector隣接リストを明示的に格納するために 1 つのグラフを実装することができます (この場合、succ_iteratorは上の単純なラッパーですstd::vector::const_iterator)。一方、別のグラフはオンザフライで計算される場合があります (その場合、そのsucc_iteratorインスタンスは進行するにつれて実際にサクセサーを計算します)。 ）。コンパイル時のグラフの性質がわからないので、これは STL のベースの実装を除外しtemplateます。

各グラフが のプールを処理できるようにすることを考えましたsucc_iterator。これにはgraph::succ_release(succ_iterator*)、イテレータを削除するのではなく、プールに戻すための追加のメソッドが必要なようです。私が見たほとんどのプールはメモリ レベルで行われます。つまり、オブジェクトを解放すると、そのデストラクタが呼び出されますが、占有されているメモリは保持されるため、次のオブジェクトが (インプレース コンストラクタを使用して) 同じ場所に作成されます。ブロック。インプレースコンストラクターが前のオブジェクトと同じ仮想テーブルポインターをセットアップする必要があるため、これでも時間が無駄になるようです。そのようなプールでは、delete+をコンストラクターと同じプロトタイプを持つメソッドにnew置き換える必要があると思います。recycle()コード ベースが非常に大きく、これにはインターフェイスの変更が必要なため、これを実装する前に、他のデザインのアイデアや改善点について聞きたいです。

編集：スレッドは使用しません。

4

1 に答える 1

0

グラフ インスタンスごとに succ_iterators をキャッシュし、必要に応じて検索して再利用できますか?

//static or member:
std::map<graph*,succ_iterator*> graph_iterator_cache;

しかし、スレッドセーフの問題があるかどうかはわかりません。

于 2012-07-04T09:42:04.800 に答える