理解两个 Scala 函数效率差异的问题 - 递归并集

Question

我正在学习 Scala 课程，我无法理解两个函数之间的效率差异。本课程是关于二叉搜索树的，其中包含被描述为 TweetSets 的推文，并且特别是令我困惑的联合函数。

我知道第一个分解树并通过 incl 函数将元素添加到树中，但我不明白为什么第二个更好。这两种情况下树都没有完全折断吗？

一棵树可以描述为：

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet:

这是两个联合函数：

def union(that: TweetSet): TweetSet = left.union(right).union(that).incl(elem)

def union(that: TweetSet): TweetSet = left.union(right.union(that).incl(elem))

由于空集中的函数并集，它们都终止了：

def union(that: TweetSet): TweetSet = that

我知道第二个函数更有效，因为它通过了测试，而第一个函数没有通过。

Answer 1

如果没有看到完整的代码，很难完全理解。然而，我认为你基本上是正确的，在这两种情况下树都被完全破坏了。

我将使用一个简单的示例并写出递归来解决这个问题。尝试 TweetSet A，其中 A.left = B 和 A.right = C，然后是一个空的 TweetSet S。（我会让 A.elem = 'a'、B.elem = 'b' 等）

然后我们评估第一个和第二个算法的 A.union(S)。

A.union(S)
= B.union(C).union(S).incl('a')
= 0.union(0).union(C).incl('b').union(S).incl('a')
= C.incl('b').union(S).incl('a')

我承认，我不是 100% 确定如何评估这一点，因为我们没有 TweetSet incl 函数的代码。但我们可以看到，我们现在必须在包含和联合之间交替。对于较大的树，这会变得夸张。

现在是第二个算法。

A.union(S) 
= B.union(C.union(S).incl('a'))
= 0.union(0.union(C.union(S).incl('a')).incl('b'))
= C.union(S).incl('a').incl('b')
= 0.union(0.union(S).incl('a').incl('b').incl('c'))
= S.incl('a').incl('b').incl('c')

仅从算法语句中很难看出，但这种递归将所有并集放在前面，可以对它们进行求值，同时将包含物堆叠在最后。

通常写出一个（或多个）小示例将有助于理解为什么代码给出不同的性能甚至不同的答案。