2

假设给定N个符号表达式，例如：

f(g(a1, a2), b1)
f(a3, b2)
f(g(a4, a2), b1)
f(a3, b4)
f(a3, b1)

为简单起见，假设所有同名函数具有相同的数量（如，没有重载）。

我的目标是使用内存中最少数量的join、union和list表达式来表示这组N项：

  • 列表表达式只是一个有限集。我们在问题中的输入集是一个列表表达式。例如：

    [a1, a2, a3]

  • 联合表达式是多个集合的联合：

    U{[a1, a2, a3], U{[b1], [c2, c3]}} == [a1, a2, a3, b1, c2, c3]

  • 函数的连接表达式f表示一个集合，该集合是其参数集与f应用于每个参数组合的函数的笛卡尔积。例如：

    f{[a1, a2, a3], [b1, b2]} == 
     [ f(a1, b1), f(a2, b1), f(a3, b1), 
       f(a1, b2), f(a2, b2), f(a3, b2) ]

给定输入集，有许多可能的方法来用这些运算符表示它。简单地将所有N个表达式合并到一个列表中是一种方法。其他两种可能如下所示：

U{ f{ [g(a1, a2), g(a4, a2)], 
      [b1] },
   f{ [a3], 
      [b1, b2, b4] }}

U{ f{ U{ [a3], 
         g{ [a1, a4], 
            [a2] } },
      [b1] },
   f{ [a3], [b2, b4] }}

直观地说，这些表示中的每一个都将给定表达式的一些公共部分统一为一个共享组件。显然，对于足够大的N而言，存在比仅包含N个表达式的显式列表占用更少内存的表示。我这里将“占用内存”定义为集合中所有项的总数（包括中间项，例如函数应用程序）加上集合表达式（连接和联合）的总数。直观地说，它只是表示中运算符和操作数的总数。例如：

  • f我们的输入集用 19 个术语表示，这是所有 5 个表达式（5秒、2g秒、...）中的术语总数。
  • 上面的第一个替代表示有 14 个术语：1 个union，2 f- joins，以及所有列表元素的 11 个术语。
  • 上面的第二种替代表示具有 13 个术语：2 个unions、 2 f- joins、 1 g- join和所有列表元素的 8 个术语。

在这些选项中，最后一个是最优化的。可能还有更好的，我不知道。最终，选择最佳表示是要弄清楚哪些部分应该共享，哪些应该明确列出。有没有办法通过算法解决这个问题？对我来说，它看起来像是对所有表达式形状的某种自上而下的动态编程，但我还没有找到确切的解决方案。

谢谢！

4

0 回答 0