问题标签 [graph-algorithm]

有谁知道任何讨论内联算法的论文？和密切相关的是，父子图与调用图的关系。

背景：我编写了一个编译器，Ocaml其中积极地内联函数，主要是由于这个和其他一些优化，它为我的编程语言在许多情况下（包括甚至C）生成比大多数其他语言更快的代码。

问题 #1：该算法在递归方面存在问题。为此，我的规则只是将孩子内联到父母中，以防止无限递归，但这排除了兄弟函数相互内联一次。

问题 #2：我不知道优化内联操作的简单方法。我的算法对于函数体的可变表示是必不可少的，因为似乎根本不可能做出有效的函数内联算法。如果调用图是一棵树，很明显自下而上的内联是最佳的。

技术信息：内联由许多内联步骤组成。问题是步骤的顺序。

每个步骤的工作原理如下：

• 我们通过用实参替换类型参数和值参数来制作要内联和 beta-reduce 的函数的副本。
• 然后，我们将 return 语句替换为对新变量的赋值，然后跳转到函数体的末尾。
• 然后，对该函数的原始调用将被此主体替换。
• 然而我们还没有完成。我们还必须克隆该函数的所有子函数，同时对它们进行 beta 缩减，并将克隆重新作为调用函数的父级。

克隆操作使得内联递归函数变得极其困难。保留已在进行中的内容的列表并仅检查我们是否已经在处理此调用的常用技巧在幼稚的形式中不起作用，因为递归调用现在被移动到被填充到调用中的 beta-reduced 代码函数，并且递归目标可能已更改为克隆的孩子。然而，在调用父级时，子级仍在调用调用其子级的原始父级，现在递归的展开不会停止。如前所述，我打破了这种回归，只允许内联对孩子的递归调用，防止兄弟递归被内联。

由于需要garbage collect未使用的函数，内联的成本变得更加复杂。由于内联可能是指数级的，因此这是必不可少的。如果对一个函数的所有调用都是内联的，如果该函数还没有被内联，我们应该删除它，否则我们将浪费时间内联到一个不再使用的函数。实际上跟踪谁调用了什么是极其困难的，因为当内联时，我们不是在使用实际的函数表示，而是一个“未分解”的表示：例如，指令列表正在按顺序处理并建立一个新列表，并且在任何一个时间点都可能没有一个连贯的指令列表。

在他的 ML 编译器中，Steven Weeks 选择使用一些重复应用的小优化，因为这使得优化易于编写和控制，但不幸的是，与递归算法相比，这错过了很多优化机会。

问题 #3：什么时候内联函数调用是安全的？

笼统地解释这个问题：在惰性函数式语言中，参数被包装在闭包中，然后我们可以内联应用程序；这是 Haskell 的标准模型。然而，它也解释了为什么Haskell这么慢。如果参数已知，则不需要闭包，则可以直接将参数替换为其参数 where is 出现（这是正常顺序beta-reduction）。

但是，如果已知参数评估不是非终止的，则可以使用急切评估：为参数分配一次表达式的值，然后重用。这两种技术的混合是使用闭包，但将结果缓存在闭包对象中。尽管如此，GHC 还没有成功地生成非常高效的代码：这显然非常困难，尤其是在您进行单独编译的情况下。

在菲利克斯，我采取了相反的方法。我不是通过证明优化保留语义来要求正确性并逐渐提高效率，而是要求优化定义语义。这保证了优化器的正确操作，但代价是某些代码将如何表现的不确定性。这个想法是为程序员提供方法来强制优化器在默认优化策略过于激进的情况下符合预期的语义。

例如，默认的参数传递模式允许编译器选择是否将参数包装在闭包中，用参数替换参数，或者将参数分配给参数。如果程序员想要强制闭包，他们可以传入一个闭包。如果程序员想要强制进行急切评估，他们会标记参数var。

这里的复杂性远大于函数式编程语言：Felix 是一种带有变量和指针的过程语言。它也有 Haskell 风格的类型类。这使得内联例程极其复杂，例如，类型类实例尽可能替换抽象函数（由于调用多态函数时的类型特化，可能在内联时找到实例，所以现在我们有了一个新函数可以内联）。

为了清楚起见，我必须添加更多注释。

内联和其他一些优化，例如用户定义的术语减少、类型类实例化、用于变量消除的线性数据流检查、尾部记录优化，都是在给定函数上一次性完成的。

排序问题不是应用不同优化的顺序，问题是对函数进行排序。

我使用一种脑死亡算法来检测递归：我建立一个每个函数直接使用的所有内容的列表，找到闭包，然后检查函数是否在结果中。请注意，在优化过程中会多次建立使用集，这是一个严重的瓶颈。

不幸的是，函数是否递归可能会发生变化。递归函数可能在尾部记录优化后变为非递归函数。但是有一个更难的情况：实例化一个类型类的“虚拟”函数可以使看起来是非递归的递归。

至于兄弟调用，问题是给定 f 和 g 其中 f 调用 g 和 g 调用 f 我实际上想将 f 内联到 g 中，并将 g 内联到 f .. 一次。我的无限回归停止规则是，如果 f 是 g 的孩子，则只允许将 f 内联到 g 中，这不包括内联兄弟。

基本上我想“尽可能地”“扁平化”所有代码。

这是另一个与动态规划相关的算法问题

这是问题所在：

找到给定矩阵的最小和，使得在每一行和每一列中选择一个

例如 ：

3 4 2

8 9 1

7 9 5

最小的一个：4 + 1 + 7

我认为解决方案是网络流量（最大流量/最小切割），但我认为它不应该像现在那么难

我的解决方案：单独到 n list[column], column1, column2 ... column n

然后起点 (S) -> column1 -> column2 -> ... -> column n -> (E) 终点并实施最大流量/最小切割

所以我想这对于在 CS 中拥有 MSC 的人来说是一个经典问题。

我有 N 个元素，我也有距离。假设我有 3 个具有以下距离的元素。它是对称的，所以

它看起来像一个矩阵：

我的问题是：

• 我怎样才能有效地存储它（什么数据结构）
• 获得距离总和最小的链表的最有效方法是什么

在这种情况下，最好的是

其他情况：

我的印象是 BFS 可能适合这个。英文文档的链接很好，即使是亚马逊上的书籍......

如何动态填充容器？假设递归地用小圆圈填充一个大圆圈。把空间填满就好了。

我想用它来显示数据层次结构。

说清楚：

请帮我找到解决这个问题的好方法。

我们有 n 个 3 维的盒子。我们可以定位它们，并且我们希望将它们放在另一个之上以获得最大高度。如果两个尺寸（宽度和长度）小于下面盒子的尺寸，我们可以将一个盒子放在另一个盒子的顶部。

例如，我们有 3 个维度 w*D*h，我们可以将其显示为 (h*d,d*h​​,w*d,d*W,h*w,w*h) 请帮我解决它图论。在这个问题中，我们不能将（2*3）放在（2*4）之上，因为它具有相同的宽度。所以二维应该小于盒子

我正在尝试为一个名为 Twiddle 的小益智游戏找到最佳解决方案（可以在此处找到带有该游戏的小程序）。游戏有一个 3x3 矩阵，数字从 1 到 9。目标是使用最少的移动量以正确的顺序排列数字。在每次移动中，您可以顺时针或逆时针旋转 2x2 正方形。

即如果你有这个状态

然后顺时针旋转左上角 2x2 正方形

我正在使用 A* 搜索来找到最佳解决方案。我的 f() 只是所需的旋转次数。我的启发式函数已经得出了最佳解决方案（如果我修改它，请参阅最后的通知），但我认为它不是你能找到的最好的解决方案。我当前的启发式方法获取每个角落，查看角落的数字并计算到该数字在已解决状态下的位置的曼哈顿距离（这给了我将数字带到这个位置所需的旋转次数）并将所有这些价值观。即你举上面的例子：

和这个最终状态

然后启发式执行以下操作

此外，如果 h 为 0，但状态不是完全有序的，则 h = 1。

但是有一个问题，你一次旋转 4 个元素。因此，在极少数情况下，您可以一次完成两个（或更多）这些估计的旋转。这意味着论文启发式高估了解决方案的距离。

我目前的解决方法是，从至少为我的测试用例解决这个问题的计算中简单地排除一个角。如果真的解决了问题，或者这种启发式方法在某些极端情况下是否仍然高估，我没有进行任何研究。

所以我的问题是：你能想出的最好的启发式方法是什么？

（免责声明：这是一个大学项目，所以这是一个家庭作业。但我可以随意使用任何资源，如果可以的话，所以可以问你们。我也会感谢 Stackoverflow 对我的帮助； ) )

我正在尝试使用 networkx 作为图形表示在 Python 中实现Hopcroft Karp 算法。

目前我是这样的：

该算法取自http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm 但是它不起作用。我使用以下测试代码

不幸的是，这不起作用，我最终陷入了无限循环:(。有人能发现错误吗，我没有想法，我必须承认我还没有完全理解算法，所以它主要是伪的实现维基百科上的代码

我正在开发一个 ruby​​ 程序，它应该能够在网页上绘制基因图。

因此，我正在寻找一种用于绘制基因图或类似树结构的算法。我更喜欢 ruby​​ 中的算法，但其他语言也可以，或者一些参考资料解释了这种算法背后的原理

C++ 中的递归算法已在此处发布，但没有以允许我使用它的方式记录。

关于如何实施基因图的任何帮助都会非常有用

所以我从 Android GPS 记录了一些数据，我试图找到这些图表的峰值，但我找不到任何具体的东西，也许是因为我不太确定我在看什么为了。我找到了一些 MatLab 函数，但找不到执行此操作的实际算法。我需要在 Java 中执行此操作，但我应该能够翻译其他语言的代码。

如您所见，有很多“小山峰”，但我只想要主要的山峰。

我正在寻找广义序列模式算法 (GSP) http://en.wikipedia.org/wiki/GSP_Algorithm的示例实现

虽然 Wikipedia 文章提供了伪代码，但它有点令人困惑，我希望看到一些正确的代码（最好是 python 或 java）。有谁知道一个好的参考？

我想首先了解该算法，然后可能使其在 MapReduce 世界中工作 - 正如维基百科文章显示的那样，我认为计数器的使用可能很复杂。

我这样做是因为我有一个事件图，其中边缘受时间限制，一个序列将是一个节点连接到另一个节点的位置，其中 A -> B 在开始和结束时间之间发生并且 B -> C 发生B 完成第一次连接后 X 次。A -> B -> C 将是序列，序列不能多次重新访问节点。