問題タブ [graph-algorithm]

アルゴリズムをインライン化する論文の議論を知っている人はいますか? そして密接に関連しているのが、親子グラフとコールグラフの関係です。

背景:主にこれと他のいくつかの最適化の結果として、関数を積極的にインライン化するコンパイラーを作成しましたOcaml。これは、多くの状況で他のほとんどのプログラミング言語よりも高速なコードを生成します ( C.

問題 #1:アルゴリズムに再帰の問題があります。このため、私のルールは、無限再帰を防ぐために、子を親にインライン化することだけですが、これにより、兄弟関数が相互にインライン化されることはなくなります。

問題 #2:インライン操作を最適化する簡単な方法を知りません。私のアルゴリズムは、関数本体の可変表現を使用することが不可欠です。効率的な関数型インライン化アルゴリズムを作成することは、リモートでさえ可能ではないように思われるからです。呼び出しグラフがツリーの場合、ボトムアップのインライン化が最適であることは明らかです。

技術情報:インライン化は、いくつかのインライン化ステップで構成されます。問題は、ステップの順序です。

各ステップは次のように機能します。

• 型パラメーターと値パラメーターの両方を引数に置き換えることにより、関数のコピーをインライン化してベータ削減します。
• 次に、return ステートメントを新しい変数への代入に置き換え、その後に関数本体の末尾にジャンプします。
• 関数への元の呼び出しは、この本体に置き換えられます。
• しかし、まだ終わっていません。また、関数のすべての子を複製し、それらもベータ削減し、複製を呼び出し元の関数に再親化する必要があります。

複製操作により、再帰関数をインライン化することが非常に困難になります。すでに進行中のもののリストを保持し、この呼び出しを既に処理しているかどうかを確認するだけの通常のトリックは、単純な形式では機能しません。関数、および再帰ターゲットが複製された子に変更された可能性があります。ただし、その子は、親を呼び出す際に、その子を呼び出す元の親を呼び出しているため、再帰の展開は停止しません。前述のように、子への再帰呼び出しのインライン化のみを許可し、兄弟の再帰がインライン化されないようにすることで、この回帰を打破しました。

インライン化のコストは、garbage collect未使用の関数が必要になるため、さらに複雑になります。インライン化は潜在的に指数関数的であるため、これは不可欠です。関数へのすべての呼び出しがインライン化されている場合、関数がまだインライン化されていない場合は削除する必要があります。そうしないと、使用されなくなった関数にインライン化する時間が無駄になります。誰が何を呼び出しているかを実際に追跡することは非常に困難です。なぜなら、インライン化するとき、実際の関数表現ではなく、「解明されていない」表現で作業しているためです。たとえば、命令のリストが順次処理され、新しいリストが構築されます。また、一貫した命令リストが存在しない可能性もあります。

彼の ML コンパイラで、Steven Weeks は繰り返し適用される多数の小さな最適化を使用することを選択しました。これにより、最適化が記述しやすく、制御しやすくなりましたが、残念ながら、これは再帰アルゴリズムと比較して多くの最適化の機会を逃しています。

問題 #3:関数呼び出しをインライン化しても安全なのはいつですか?

この問題を一般的に説明すると、遅延関数型言語では、引数がクロージャでラップされ、アプリケーションをインライン化できます。これは Haskell の標準モデルです。ただし、なぜHaskellこんなに遅いのかについても説明しています。引数が既知の場合、クロージャーは必要ありません。その場合、パラメーターは、発生する引数で直接置き換えることができます (これは通常の順序beta-reductionです)。

ただし、引数の評価が終了しないことがわかっている場合は、代わりに熱心な評価を使用できます。パラメーターには式の値が一度割り当てられ、その後再利用されます。これら 2 つの手法のハイブリッドは、クロージャーを使用するが、結果をクロージャー オブジェクト内にキャッシュすることです。それでも、GHC は非常に効率的なコードを生成することに成功していません。特に、個別にコンパイルする場合は、明らかに非常に困難です。

Felix では、逆のアプローチを取りました。正確さを要求し、最適化がセマンティクスを保持していることを証明することによって徐々に効率を改善する代わりに、最適化がセマンティクスを定義することを義務付けます。これにより、特定のコードがどのように動作するかについての不確実性を犠牲にして、オプティマイザーの正しい動作が保証されます。この考え方は、デフォルトの最適化戦略が積極的すぎる場合に、オプティマイザーを意図したセマンティクスに強制的に準拠させる方法をプログラマーに提供することです。

たとえば、デフォルトのパラメーター受け渡しモードでは、コンパイラーは引数をクロージャーでラップするか、パラメーターを引数で置き換えるか、または引数をパラメーターに割り当てるかを選択できます。プログラマーがクロージャーを強制したい場合は、クロージャーを渡すだけです。プログラマーが熱心な評価を強制したい場合は、パラメーターをマークしますvar。

ここでの複雑さは、関数型プログラミング言語よりもはるかに大きくなります。Felix は、変数とポインターを使用する手続き型言語です。Haskell スタイルの型クラスもあります。これにより、インライン化ルーチンが非常に複雑になります。たとえば、型クラスのインスタンスは、可能な限り抽象関数を置き換えます (ポリモーフィック関数を呼び出すときの型の特殊化により、インライン化中にインスタンスを見つけることができる場合があるため、新しい関数があります。インライン化できます)。

明確にするために、さらにメモを追加する必要があります。

インライン化と、ユーザー定義の用語削減、型クラスのインスタンス化、変数削除のための線形データ フロー チェック、テール レコードの最適化などの他のいくつかの最適化が、指定された関数に対して一度に実行されます。

順序付けの問題は、さまざまな最適化を適用する順序ではなく、関数を順序付けすることです。

脳死アルゴリズムを使用して再帰を検出します。各関数によって直接使用されるすべてのリストを作成し、クロージャーを見つけて、関数が結果に含まれているかどうかを確認します。使用セットは最適化中に何度も構築されることに注意してください。これは深刻なボトルネックです。

関数が再帰的であるかどうかは、残念ながら変わる可能性があります。tail rec の最適化後、再帰関数が非再帰になる可能性があります。しかし、もっと難しいケースがあります: 型クラスの「仮想」関数をインスタンス化すると、再帰的でないように見えたものを再帰的にすることができます。

兄弟呼び出しに関しては、問題は、f が g を呼び出し、g が f を呼び出す f と g を指定すると、実際には f を g に、g を f .. に 1 回インライン化したいことです。私の無限回帰停止規則は、f が g の子である場合に相互に再帰的である場合にのみ、f の g へのインライン展開を許可することです。これにより、兄弟のインライン展開は除外されます。

基本的に、すべてのコードを「可能な限り」「平坦化」したいと考えています。

これは、動的計画法に関連する別のアルゴリズムの問​​題です。

ここに問題があります：

各行と列で1つを選択するように、指定された行列の最小合計を見つけます

例えば ​​：

3 4 2

8 9 1

7 9 5

最小のもの：4 + 1 + 7

解決策はネットワークフロー（最大フロー/最小カット）だと思いますが、それほど難しくはないはずです

私の解決策：nに分離list [column]、column1、column2 ... column n

次に、開始点（S）->列1->列2-> ...->列n->（E）終了点で、最大フロー/最小カットを実装します

ですから、これはCSでMSCを取得している人にとっては古典的な質問だと思います。

N要素があり、距離もあります。次の距離の要素が3つあるとします。対称なので

マトリックスのように見えます：

私の質問は次のようになります：

• これを効率的に保存するにはどうすればよいですか（どのデータ構造）
• 距離の合計が最小であるリンクリストを取得するための最も効率的な方法は何ですか

この場合、最良は

その他の場合：

これにはBFSが適しているのではないかという印象を受けました。アマゾンの本でさえ、英語のドキュメントへのリンクは良いです...

コンテナーを動的に満たすにはどうすればよいですか? 大きな円を小さな円で再帰的に塗りつぶすとしましょう。スペースをうまく埋めるだけです。

データ階層表示に使用したいと思います。

明確にするために：

この問題の適切な解決策を見つけるのを手伝ってください。

3 次元の n 個のボックスがあります。それらを方向付けることができ、最大の高さになるようにそれらを別の上に置きたい. 2 つの寸法 (幅と長さ) が下のボックスの寸法よりも小さい場合、ボックスを別のボックスの上に置くことができます。

たとえば、w*D*h の 3 つの次元があり、(h*d,d*h​​,w*d,d*W,h*w,w*h) で表示できます。グラフ理論。この問題では、(2*3) を (2*4) の上に配置することはできません。これは、幅が同じであるためです。したがって、2 次元はボックスよりも小さくする必要があります。

Twiddle と呼ばれる小さなパズル ゲームの最適な解決策を見つけようとしています (ゲームのアプレットはここにあります)。このゲームには、1 から 9 までの数字の 3x3 マトリックスがあります。目標は、最小限の移動で数字を正しい順序に並べることです。一手ごとに、2x2 の正方形を時計回りまたは反時計回りに回転させることができます。

つまり、この状態がある場合

左上の 2x2 の正方形を時計回りに回転すると、

A* 検索を使用して最適なソリューションを見つけています。私の f() は単に必要な回転数です。私のヒューリスティック関数はすでに最適な解決策につながっています (変更する場合は、最後の通知を参照してください)。私の現在のヒューリスティックは各コーナーを取り、コーナーの数字を見て、この数字が解決された状態で持つ位置までのマンハッタン距離を計算し (これにより、数字をこの位置に移動するために必要な回転数が得られます)、すべてを合計しますこれらの値。つまり、上記の例を取り上げます。

そしてこの最終状態

次に、ヒューリスティックは次のことを行います

さらに、h が 0 であるが、状態が完全に順序付けられていない場合、h = 1 よりも。

しかし、一度に 4 つの要素を回転させるという問題があります。そのため、これらの推定回転を 1 回の移動で 2 つ (またはそれ以上) 実行できるまれなケースがあります。これは、これらのヒューリスティックが解までの距離を過大評価していることを意味します。

私の現在の回避策は、少なくとも私のテストケースでは、この問題を解決する計算からコーナーの 1 つを単純に除外することです。本当に問題が解決するかどうか、またはこのヒューリスティックがいくつかのエッジケースでまだ過大評価されているかどうかは調査していません。

だから私の質問は、あなたが思いつくことができる最高のヒューリスティックは何ですか?

（免責事項：これは大学のプロジェクトのためのものなので、これはちょっとした宿題です。しかし、私は思いついたリソースを自由に使用できるので、皆さんに聞いても大丈夫です。また、私を助けてくれた Stackoverflow の功績を認めます。 ) )

グラフ表現としてnetworkxを使用して、Pythonでホップクロフトカープアルゴリズムを実装しようとしています。

現在、私はこれまでです：

アルゴリズムはhttp://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithmから取得されますが 、機能しません。次のテストコードを使用します

残念ながら、これは機能せず、無限ループに陥ります:(。誰かがエラーを見つけることができますか、私はアイデアがありません、そして私はまだアルゴリズムを完全に理解していないことを認めなければなりません、それでそれはほとんど疑似の実装ですウィキペディアのコード

Web ページにジェノグラムを描画できる Ruby プログラムを開発しています。

したがって、ジェノグラムまたは同様のツリー構造を描画するためのアルゴリズムを探しています。私はRubyのアルゴリズムを好みますが、他の言語もそうするか、そのようなアルゴリズムの背後にある原則を説明するいくつかの参考文献を参照してください

C++ の再帰アルゴリズムはここで公開されていますが、私が使用できるように文書化されていません。

ジェノグラムを実装する方法についてのヘルプは、非常に感謝されます

Android GPS からいくつかのデータを記録しました。これらのグラフのピークを見つけようとしていますが、特定のものを見つけることができませんでした。為に。いくつかの MatLab 関数を見つけましたが、それを実行する実際のアルゴリズムが見つかりません。これは Java で行う必要がありますが、他の言語のコードを翻訳できるはずです。

ご覧のとおり、多くの「ミニ ピーク」がありますが、メインのピークだけが必要です。

I am looking for an example implementation of the Generalized Sequential Pattern algorithm (GSP) http://en.wikipedia.org/wiki/GSP_Algorithm

Whilst the Wikipedia article provides psuedo code, its a bit confusing and I would like to see some proper code (ideally python or java). Does anyone know a good reference?

I want to understand the algorithm first and then potentially make it work in a MapReduce world - which as the wikipedia article shows the use of counters I think could be complex.

I am doing this because I have a graph of events where the edges are constrained by time, a sequence would be where a node is connected to another node where A -> B happens between a start and a finish time and B -> C happens X time after B finishes in the first connection. A -> B -> C would be the sequence, a sequence can't revisit a node more than once.