6

アルゴリズムが進むにつれて大きくなる大きなツリーがあります。各ノードにはセットが含まれています。これは、平衡二分探索木として実装されていると思います。各ノードのセットは、そのノードの作成後、そのノードの子の作成に使用する前に、固定されたままになります。

ただし、各セットのコピーには法外な費用がかかるのではないかと心配しています。代わりに、新しく作成された各ノードのセットが、親ノードのセットの適切な部分をすべて利用することをお勧めします。要するに、私はセットのO（log n）をコピーするのは幸せですが、O（n）はコピーしません。

そのような部分的なコピーの最適化を提供するSTLの連想データ構造の変形はありますか？おそらくブーストで？もちろん、このようなデータ構造をHaskellやOCaMLに実装するのは簡単ですが、C++ではより多くの労力が必要になります。

4

3 に答える 3

1

別の言語を提案することは一般的に生産的ではないことを私は知っていますが、Haskellの標準コンテナライブラリはまさにこれを行います。この正確な問題について話しているビデオ（Simon Peyton Jonesでしたか？）を見て、Haskellソリューションが特定のプログラマーの努力に対してC++ソリューションよりもはるかに高速になったのを覚えています。もちろん、これは多くの共有要素を持つセットがたくさんある特定の問題のためでした。

この主題についてはかなりの量の研究があります。キーワードを探している場合は、「不変のデータ構造」ではなく「機能的なデータ構造」を検索することをお勧めします。ほとんどの機能パラダイムは、一般に不変性の恩恵を受けるからです。この問題を正確に解決するために、フィンガーツリーなどの構造が開発されました。

これらのデータ構造を実装するC++ライブラリはありません。関連する論文（またはテストを含めるための約1,000行であるHaskellソースコード）を読んでData.Setそれを自分で実装することを妨げるものは何もありませんが、それはあなたが聞きたいものではないことを私は知っています。また、共有ノードに対して何らかの参照カウントを行う必要があります。このような深い構造では、単純なガベージコレクターよりもオーバーヘッドが高くなる可能性があります。

于 2011-10-04T17:06:04.070 に答える
0

各ノードにはセットが含まれています。これは、平衡二分探索木として実装されていると思います。各ノードのセットは、そのノードの作成後、そのノードの子の作成に使用する前に、固定されたままになります。

これは非常にユニークなケースです。代わりにstd::vectorを使用することをお勧めします。（実際にはありません！）コードは、ノードが引き続き使用できるように作成し、最後の1秒でにset切り替えます。vectorただし、vectorは小さく、必要なメモリ割り当ての数はごくわずか（を使用する場合は1つreserve）であるため、アルゴリズムがはるかに高速になります。

typedef unsigned int treekeytype;
typedef std::vector<unsigned int> minortreetype;
typedef std::pair<treekeytype, minortreetype> majornode
typedef std::set<treekeytype, minortreetype> majortype;
majortype majortree;

void func(majortype::iterator perform) {
     std::set<unsigned int> results;
     results.assign(perform->second.begin(), perform->second.end());
     majortree[perform->first+1].assign(results.begin(), results.end()); //the only change is here
     majortype::iterator next = majortree.find(perform->first+1);
     func(next);
}

セットと同じようにソートされているため、O（log（n））メモリアクセスを使用して取得することもできstd::lower_bound、std::upper_bound効率が低下することはありません。頻繁に挿入/削除する必要がない限り、それは純粋な利益です。

ただし、各セットのコピーには法外な費用がかかるのではないかと心配しています。

各セットに親とほぼ同じノードが含まれていて、データにコストがかかり（コピーまたはメモリのいずれか）、変更されたノードが少ないためにこの恐れが生じる場合はstd::shared_pointers、データ自体の代わりにサブツリーに含まれるようにします。これは、データ自体はコピーされず、ポインタのみがコピーされることを意味します。

これはあなたが質問で目指していたものではないことを私は理解していますが、JamesKanzeが言ったように、私はそのようなコンテナを知りません。ropeおそらくSTLのクラスの奇妙で危険な使用以外。標準のC++ライブラリではなく、STLを意味していることに注意してください。それらは異なります。

于 2011-10-04T17:05:27.727 に答える
0

不変コンテナの概念が存在しないため、C++ では事実上不可能です。変更を加えないこと、およびある種の共有表現が望ましいことを知っているかもしれませんが、コンパイラとライブラリはそうではなく、これを伝える方法がありません。

于 2011-10-04T16:31:56.060 に答える