scala - 为什么 "((left union right) union other)"没有关联行为？

Question

以下要点中的代码几乎是从 Martin Odersky 的 Scala 中的函数式编程原则 类(class)中一字不差地提取出来的 Coursera :

https://gist.github.com/aisrael/7019350

问题出现在第 38 行，在 NonEmpty 类的 union 定义中:

def union(other: IntSet): IntSet =
  // The following expression doesn't behave associatively
  ((left union right) union other) incl elem

对于给定的表达式，((left union right) union other)，largeSet.union(Empty) 需要大量时间才能完成 100 个集合元素或更多。

当该表达式更改为 (left union (right union other)) 时，联合操作相对立即完成。

---

已添加:这是一个更新后的工作表，它显示了即使使用具有随机元素的更大的集合/树，表达式 ((left ∪ right) ∪ other) 也可能需要很长时间，但是 (left ∪ (right ∪ other)) 将立即完成。

https://gist.github.com/aisrael/7020867

Answer 1

您问题的答案与关系数据库及其做出的明智选择密切相关。当数据库“联合”表时 - 智能 Controller 系统将围绕“表 A 有多大？首先加入 A 和 B 或在用户写入时加入 A 和 C 更有意义:

 A Join B Join C

无论如何，当您手动编写代码时，您不能期待相同的行为 - 因为您已经使用括号准确指定了您想要的顺序。这些明智的决定都不会自动发生。 (尽管理论上他们可以，这就是 Oracle、Teradata、mySql 存在的原因)

考虑一个大得离谱的例子:

Set A  - 1 Billion Records
Set B  - 500 Million Records
Set C   -  10 Records

为了论证，假设联合运算符通过连接的 2 个集合中最小的记录获取 O(N) 条记录。这是合理的，每个键都可以作为散列检索在另一个键中查找:

A & B 运行时间 = O(N) 运行时间 = 5 亿(假设该类足够聪明，可以使用两者中较小的一个进行查找)

所以

(A & B) & C 

Results in:

O(N) 500 million +  O(N) 10  = 500,000,010 comparisons

再次指出它被迫首先比较 10 亿条记录和 5 亿条记录的事实，根据内括号，然后 - 再拉入 10 条记录。

但考虑一下:

A & (B & C)

好吧，现在发生了一些惊人的事情:

(B & C) runtime O(N) = 10 record comparisons (each of the 10 C records is checked against B for existence)
then
A & (result) = O(N) = 10

Total = 20 comparisons

请注意，一旦 (B & C) 完成，我们只需将 10 条记录与 10 亿条记录相撞!

两个例子产生完全相同的结果；一个在 O(N) = 20 运行时，另一个在 500,000,010 !

总而言之，这个问题只是以一种很小的方式说明了数据库设计中的一些复杂思维以及该软件中发生的智能优化。这些事情在编程语言中并不总是自动发生，除非您以这种方式编写代码或使用某种库。例如，您可以编写一个函数，它接受多个集合并智能地决定并集顺序。但是，如果必须混入其他集合操作，问题就会变得异常复杂。希望这会有所帮助。