29

我目前在下班后的空闲时间在 Coursera 上学习 Scala 课程，试图最终尝试函数式编程。我目前正在处理一项任务，我们应该“计算”包含某个对象的两个集合的并集。我故意省略了细节，因为这对我在这里要问的内容并不重要。然而，相关的是集合被定义为二叉树，每个节点包含一个元素和两个子树。

既然如此；讲座中的例子union如下：

def union(other:BTSet) :BTSet = ((left union right) union other) incl element

问题1：坦率地说，即使在阅读了相关的FAQ和其他论坛帖子之后，我仍然不明白这个功能是如何以及为什么起作用的。除了在头节点添加（调用）元素之外，在联合实现中这里绝对没有“动作” incl，它只是一遍又一遍地调用自己。我会非常感谢一些解释......

问题2：课程论坛中有很多帖子说这个解决方案根本没有效率，而且还不够好。看到我不明白它是如何工作的，我真的不明白为什么它不够好。

请注意，我不会以任何方式要求对分配解决方案进行剧透。我非常愿意“为成绩做作业”，但我根本不明白我应该在这里做什么。我不相信课程中提供的说明和指导足以让您了解函数式编程的怪癖，因此我欢迎任何关于如何正确思考而不是如何正确编码的评论/答案。

4

6 回答 6

27 
  A
 / \  union  D
B   C

((B union C) union D) incl A
  ^^^^^^^^^......................................assume it works

(  B             )
(    \   union D ) incl A
(     C          )

(((0 union C) union D) incl B) incl A
   ^^^^^^^^^.....................................just C

(((C union D) incl B) incl A
   ^^^^^^^^^.....................................expand

((((0 union 0) union D) incl C) incl B) incl A
    ^^^^^^^^^....................................just 0

(((0 union D) incl C) incl B) incl A
   ^^^^^^^^^.....................................just D

((D incl C) incl B) incl A
^^^^^^^^^^^^^^^^^^^^^^^^^^.......................all incl now

一步一步写出来。现在您看到 union 简化为一组应用于右侧参数的 incl 语句。

于 2013-04-25T15:15:27.107 回答
5

我收集到incl将元素插入现有集合？如果是这样，那就是所有真正的工作正在发生的地方。

并集的定义是包含任一输入集中所有内容的集合。给定两个存储为二叉树的集合，如果将第一个集合的并集与第二个集合的分支相结合，则结果中唯一可能丢失的元素是第二个树的根节点处的元素，所以如果你插入那个元素你有两个输入集的联合。

这只是将两个集合中的每个元素插入到一个开始为空的新集合中的一种非常低效的方法。推测重复项被 丢弃incl，因此结果是两个输入的并集。

也许暂时忽略树结构会有所帮助；它对基本算法并不重要。假设我们有抽象的数学集合。给定一个包含未知元素的输入集，我们可以做两件事：

  • 向其中添加一个元素（如果该元素已经存在，则不执行任何操作）
  • 检查集合是否非空，如果是，则将其分解为单个元素和两个不相交的子集。

为了取两个集合 {1,2} 和 {2,3} 的并集，我们首先将第一个集合分解为元素 1 和子集 {} 和 {2}。我们使用相同的过程递归地取 {}、{2} 和 {2,3} 的并集，然后将 1 插入结果中。

在每一步，问题从一个联合运算减少到两个较小输入的联合运算；一个标准的分治算法。当达到单例集 {x} 和空集 {} 的联合时，联合是平凡的 {x}，然后返回到链上。

树结构仅用于允许案例分析/分解成更小的集合，并使插入更有效。使用其他数据结构也可以做到这一点，例如将列表分成两半以进行分解，并通过详尽的唯一性检查完成插入。要有效地采用联合，需要一种更聪明的算法，并利用用于存储元素的结构。

于 2013-04-25T14:54:44.053 回答
3

因此，基于上述所有响应，我认为真正的主力是incl递归调用方式union只是为了遍历集合中的所有元素。

我想出了以下联合的实现，这更好吗？

def union(other:BTSet) :BTSet = right union (left union (other incl element))
于 2016-06-19T23:03:57.567 回答
2 
  2
 / \  union  4
1   3

((1 union 3) union 4) incl 2
  ^^^^^^^^^......................................assume it works

(((E union E) union 3 incl 1) union 4) incl 2
   ^^^^^^^^^.....................................still E

(E union E) union 3 incl 1 = E union 3 incl 1 = 3 incl 1

The following subtree should be 3 incl 1

(  3             ) 
(    \   union D ) incl 2
(      1         )


(((1 union E) union 4) incl 3) incl 2
   ^^^^^^^^^.......................................expand

(((( (E union E) union E) incl 1) union 4) incl 3) incl 2
      ^^^^^^^^^^^^^^^^^^^^^^^^^^..................still 1

((1 union 4) incl 3) incl 2
   ^^^^^^^^......................................continue

((((E union E) union 4) incl 1) incl 3) incl 2
   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^..........expand 1 union 4

((4 incl 1) incl 3) incl 2
  ^^^^^^^^^^^^^^^^^^^^^^^^^............Final union result

Thanks @Rex Kerr draws out the steps. I substitute the second step with the actual runtime step, which may give a more clear description of the Scala union function.

于 2014-05-12T18:42:11.397 回答
1

除非您查看基本案例，否则您无法理解递归算法。事实上，很多时候，理解的关键在于首先理解基本情况。由于未显示基本情况（可能是因为您一开始没有注意到有一个），因此无法理解。

于 2013-09-30T23:26:35.677 回答
-3

我正在做同样的课程，上面的实现union确实效率极低。

我想出了以下不太实用的解决方案来创建二叉树集合的联合，这更有效：

def union(that: BTSet): BTSet = {
  var result:BTSet = this
  that.foreach(element => result = result.incl(element))
  result
}
于 2014-11-21T20:49:24.510 回答