1

125,000 ノード (最大 2 つの子) のツリーがあります。各ノードの子 (直接および間接) の数を決定しようとしています。ツリーは DAG ですが、各子へのリンクの数は無制限であるため、多くのノードは実質的に他のすべてのノードを子として持ちます。参考までに、ツリーの全体的な複雑さは、メモ化せずに表現すると 10^30 をはるかに超えます。これは、各子への単純なポインターを格納する (および出力をメモ化する) だけで、ハッシュ テーブル、メモリ アロケーター、およびその他のオーバーヘッドを無視しても、15.625 GB のデータの塊が生成されることを意味します。

これは望ましい出力ですが、達成するのに少し時間がかかりすぎて、メモリが少し多すぎます。私は 1 台のワークステーションしか持っていませんが、そこそこのパワーを備えていますが、最高レベルではありません (i7 930、6GB RAM)。

合理的な期間内にデータにアクセスできるように、テーブルをメモ化またはキャッシュする方法はありますか (データに対して数十万回のアクセスを行う可能性があります)。クエリを遅延評価することを検討しましたが、クエリにアクセスするのにどれくらいの時間がかかるかが心配です。

さらに、どのノードが子であるかには特に関心はありませんが、それらの数を知る必要があります。これは、同じ子を 2 回数えることはできないため、基本的には同じことです。

編集：ツリーは不変です。私がすることは、子供の数を読むことだけです。

4

5 に答える 5

1

すでに答えを見つけているようですが、この種の問題について考えている他の人にとっては、DAG の推移的な閉鎖が役に立つかもしれません。

Timothy Chanは 2005 年に、DAG の推移閉包の効率的な計算に関する脚注を含む論文を発表しました。論文からの引用：

...重み付けされていない有向グラフの推移閉包を計算するというより単純な問題について、Yuster と Zwick は最近の論文で O(mn) 時間アルゴリズムを求めましたが、O(mn/log n + n 2 ) 時間制限RAMという言葉に乗るのは実際には簡単です。2

...

2証明: 強連結成分を線形時間で事前に計算し、各成分を縮約できるため、グラフが非巡回であると仮定します。各頂点uから到達可能なすべての頂点で集合S uを見つけたいと考えています。逆トポロジー順の各頂点uについて、 uからのすべての頂点vインシデントでS vの結合をとることによって、 S uを計算できます。これらの O(m) 個の集合和演算のそれぞれは、集合を (n/log n) 語ベクトルとして表し、ビットごとの OR 演算を使用することにより、O(n/log n) 時間で実行できます。

明らかに、まだ解明すべき点が少しあります。「強く接続されたコンポーネント」を事前に計算し、トポロジーの逆順でノードを訪問できるようにする必要があります。 DAG 内の特定のノードの子の数をカウントする方法。

于 2012-06-04T02:22:06.517 に答える
1

ノードを 2 回通過せずに直接非巡回グラフをトラバースする場合 (たとえば、各ノードを 1 回カウントする場合)、mutable各ノードにブール値を追加して、以前にノードをトラバースしたことがあるかどうかを示すことができます。ノードをマークし、ノードを確認し、ノードのマークされていない子を再帰的にトラバースすることで、ノードのすべての子孫を確認できます。

于 2012-06-04T01:41:37.143 に答える
0

ノード自体にノードの子孫の数をキャッシュします。ノードは不変であるため、子孫の数を計算してキャッシュでき、キャッシュされた値が古くなる心配はありません。

特定のノードの子孫の数は、1に、その各子（間接の子孫ではなく、直接の子）の子孫の数の合計を加えたものです。各子はその子孫の数をキャッシュしているため、これは非常に高速な計算です。

于 2012-06-04T01:17:33.520 に答える
0

いくつかのアルゴリズムを破ろうとしていますか？：naughty：最も簡単な方法は、n / nlogn（一般的に機能する）n（一般的に参照する）ケースを使用することです。この場合、そのテーブルへのキー参照を格納し、特定のマップされたハッシュスタックが必要なときはいつでも検索します。したがって、たとえば、nルートノードにはn1とn2の子ノードがあり、n1子ノードは処理されませんが、参照されてディスク上のどこかに保持されますが、n1ルートノード（基本的にn1子ノードと同じですが、カウントされる）はさらに処理され、n11とn12の子ノードがあり、n11ルートノードはそのツリーへの参照としてマップされます。したがって、たとえば、他の参照キーへのポインタを含む125,000の参照キーしかなく、必要に応じて、PCが実際に処理するものを何でも使用できます。

于 2012-06-04T01:21:54.503 に答える
0

問題の一部は大規模なデータセットであるため、これは mapreduce アプローチを介して実行できます。これは、C++ ではなくテキスト ファイルとクラスターの領域にあるため、非常に異なる方法ですが、完了までの時間にあまり影響を与えずに、少なくともマシン数に合わせてスケーリングします。

この方法は、各有向エッジを示すキーと値のペアから開始し、それぞれが完了とマークされるまで、それぞれから派生するノードのセットを構築することです。2 つの子ノードから収集する場合は、子のセットの共通部分を使用し、不完全なノードのセットを個別に維持します。これには、深さのレベルごとに 2 つのマップと収集のようなものが必要ですが、グラフを上るにつれて明らかに作業負荷が軽減されます。

明らかに計算量が増えますが、スケーリングを容易にするために既存の Hadoop などのシステムを活用できます。

この答えには 2 つのレベルがあると思います。a) マルチパス アプローチを検討し、b) Hadoop などによる作業の分散を検討します。

于 2012-06-06T09:13:09.420 に答える