11

由并集、交集和差组成的集合计算通常可以用许多不同的方式表示。是否有任何理论或具体实现试图最小化达到给定答案所需的计算量？

例如，当我试图在模拟无定形材料中将原子分解为相邻壳时，我第一次遇到了这个的实际应用，其中第一个壳是某个给定原始原子的直接邻居，第二个壳是那些相邻的原子第一个外壳不在第一个外壳或在它之前的外壳中：

nth 0 = singleton i
nth 1 = neighbors i
nth n = reduce union (map neighbors (nth(n-1))) - nth(n-1) - nth(n-2)

有很多不同的方法可以解决这个问题。您可以在组成结果的同时逐步测试每个集合中的成员资格，或者您可以计算三个相邻壳的并集并使用交集删除前两个壳，留下最外层的壳。在实践中，需要构建大型中间集的解决方案速度较慢。

据推测，智能集实现可以组成要评估的表达式，然后在评估它之前对其进行优化（例如，减少中间集的大小）以提高性能。是否存在这样的集合实现？

4

1 回答 1

8

您的问题立即让我想起了本文中描述的 Haskell 的流融合。一般原则可以很容易地总结出来：你不是存储一个列表，而是存储一种构建列表的方法。然后列表转换函数直接在列表生成器上操作，这意味着所有操作都融合到一个数据生成中，而无需任何中间结构。然后，当您完成组合操作时，您将运行生成器并生成数据。

所以我认为你的问题的答案是，如果你想要一些类似的智能机制来融合计算并消除中间数据结构，你需要找到一种方法将集合转换为“共同结构”（这就是论文调用它）生成一个集合并直接对其进行操作，然后在完成后实际生成集合。

我认为这个概念背后有一个非常深刻的理论，论文暗示但从未阐明，如果这里的其他人知道它是什么，请告诉我，因为这与我正在做的其他事情也非常相关！

于 2012-06-10T20:03:38.873 回答