問題タブ [graph-reduction]

依存関係についていくつかのコードを分析しています。次のように、いくつかの織り交ぜられた依存関係があるとしましょう。

B は A と C に依存する C は B と F に依存する E は C と F に依存する D は B と C と E に依存する

B と C に問題があります。これらは相互に依存しています。それらはスーパーノードに結合する必要があります。C と E と F に問題があります。それらにはサイクルがあります。それらはスーパーノードに結合する必要があります。

あなたはで終わるだろう

そのような削減を可能にする優れたライブラリまたはアルゴリズムのソース (Java が推奨されますが、提案を受け付けています) はありますか?

サイクル内のすべてのノードは、1 つのノードに結合されます。新しいノード内の任意のノードを指しているノードはすべて、新しいノードを指している必要があります。新しいノード内の任意のノードが指すノードは、新しいノードがそのノードを指すようにする必要があります。

ありがとう！

私はhaskellのスペースの複雑さについて考える正式な方法を見つけようとしています。私は、グラフ還元（GR）手法についてのこの記事を見つけました。しかし、場合によっては適用に問題があります。次の例を考えてみましょう。

二分木があるとしましょう：

ツリーをトラバースする2つの関数。1つ（count1）は適切にストリーミングし、もう1つ（count2）はメモリ内にツリー全体を一度に作成します。プロファイラーによると。

count1の場合、それがどのように機能するかを理解していると思います。グラフ還元の観点から、次のようになります。

シーケンスからは一定の空間で実行されていることは明らかだと思いますが、count2の場合はどうなりますか？

私は他の言語のスマートポインターを理解しているので、 count2関数の余分なrパラメーターがどういうわけかツリーのノードが破壊されるのを防ぐことを漠然と理解していますが、正確なメカニズム、または少なくとも私が使用できる正式なメカニズムを知りたいです他の場合も同様です。

見てくれてありがとう。

fromスタックレス言語はどのように機能しますか?

本当に？興味深いことに、私自身は経験したことがありませんが、フォールド関数の厳密なバージョンを使用せずに無限フォールドの評価を強制すると、スタック オーバーフローが発生することを読んだことがあります。確かに、それはスタックの存在を示しています。誰でも明確にできますか？

私はHaskellで半明示的な並列処理を読んでいて、混乱しています。

このアプローチにより、Haskell プログラムのすべての部分式を並列に評価することで、自動的に並列化を行うことができると言われています。しかし、このアプローチには次の欠点があります。

1) 作業の小さな項目が多すぎるため、効率的にスケジュールを立てることができません。私が理解しているように、Haskell プログラムのすべての行に par 関数を使用すると、あまりにも多くのスレッドが作成され、まったく実用的ではありません。そうですか？

2) このアプローチでは、並列処理はソース プログラム内のデータの依存関係によって制限されます。私の理解が正しければ、すべての部分式が独立していなければならないということです。同様に、par 関数では、a と b は独立している必要があります。

3) Haskell ランタイム システムは、式 a の値を計算するためのスレッドを必ずしも作成しません。代わりに、親スレッドとは異なるスレッドで実行される可能性があるスパークを作成します。

だから、私の質問は次のとおりです。最終的に、ランタイム システムは a を計算するスレッドを作成しますか? または、式 b を計算するために式 a が必要な場合、システムは a を計算するための新しいスレッドを作成しますか? そうでなければ、そうはなりません。これは本当ですか？

私は Haskell の初心者なので、私の質問はまだ基本的なものかもしれません。ご回答有難うございます。

現在、Python を使用して「ツリーの要約」の問題を解決しています。私のツリーは、重みと子を持つノードで構成されています。例

エッジ収縮によって得られるすべての可能なグラフを見つけることに興味があります。2 つのエッジを縮小すると、古い頂点が新しい頂点に置き換えられます。重みは古い頂点の合計です。たとえば、子 2 を孫 1 と契約すると、次のようになります。

もちろん、これは可能なエッジ収縮の 1 つにすぎません。この小さなツリーでも、もっと多くの短縮形があります (例: (child 1, child 2), (child 1, parent), (child 2, parent))。

これらの新しいツリーのそれぞれについて、1 つのノードを縮小することによって得られるすべてのツリーを再度見つける必要があります (最終的に、問題は n ノード ツリーを m ノード ツリーに縮小することです)。

私は現在、適切なノード サイズのツリーに到達するまで、edge_contract() を再帰的に呼び出して「ブルート フォーシング」を行っています。しかし、コードは適度なサイズのツリー (~25 ～ 50 ノード) で機能する必要があり、現在の実装はそうではありません。

このタイプの木の収縮は解決済みの問題ですか。問題に取り組むための良い方法は何ですか?

このページで読んだスペースリークの例について疑問に思っています（残念ながら、そこでは説明されていませんでした）： https://en.wikibooks.org/wiki/Haskell/Graph_reduction

トリッキーなスペースリークの例:

(\xs -> 先頭の xs + 最後の xs) [1..n]

(\xs -> 最後の xs + 先頭の xs) [1..n]

最初のバージョンは O(1) 空間で実行されます。O(n) の 2 番目。

私が正しく理解しているかどうかはわかりません（助けていただければ幸いです）。私の知る限り、遅延評価は左端の最も外側の評価を意味します。したがって、これらの例では、これらの redex を次のように減らします。

(\xs -> 先頭の xs + 最後の xs) [1..200]

=> ([1..200] -> 先頭の x + 最後の x)

=> 先頭 [1..200] + 末尾 [1..200]

=> 1 + 最後 [1..200]

=> 1 + 最後 [2..200]

=> ... ...

=> 1 + 最後 [199..200]

=> 1 + 最後 [200]

=> 1 + 200

=> 201

と

(\xs -> 最後の xs + 先頭の xs) [1..200]

([1..200] -> 最後の xs + 先頭の xs)

ラスト [1..200] + ヘッド [1..200]

ラスト [2..200] + ヘッド [1..200]

... ... ...

ラスト [199..200] + ヘッド [1..200]

ラスト [200] + ヘッド [1..200]

200 + ヘッド [1..200]

200 + 1

201

間違った方法で縮小したのかもしれませんが (間違っている場合は訂正してください)、ここではスペースリークの可能性は見られません。そこで、最初に ghci でランタイム (スペースではない) をテストしました。

ウィキブックによると、2 番目のバージョンではスペース リークが発生するはずですが、ランタイムははるかに高速です (可能かもしれませんが、ここでは何もおかしくありません)。

次のソースコードがあります。

...そして、最適化なしでコンパイルしてから、プログラムを呼び出しました：

これは良い結果です。2.3% のガベージ コレクションがあり、使用メモリは約 1 MB です。次に、最適化なしで他のケースをコンパイルしたところ、次の結果が得られました。

これはさらに悪いことです。大量のガベージ コレクションが行われ、メモリ使用量がはるかに高くなります。

ここで実際に何が起こっているのですか？スペースリークが発生する理由がわかりません。

PS 両方のケースを完全最適化 (O2) でコンパイルすると、両方のプログラムの効率はほぼ同じになります。

Is there an algorithm that shortens paths (and removes nodes) based on edge cost? I can't put it into words too well so I hope these images sum it up well enough:

直接ハミルトン パス (DHP) を無向ハミルトン パス (UHP) に縮小したいのですが、そのための標準アルゴリズムは、DHP の v などの各頂点を vIN、vMID、vOUT の 3 つの頂点に分割することです。 私の質問は、なぜ中央の頂点、つまり vMID が必要なのですか? とにかく、これらすべての頂点は互いに接続されています。