2

以下要点中的代码几乎是从 Martin Odersky在Coursera上的 Scala 函数式编程原理课程的讲座中逐字提取的：

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

问题发生在第 38 行，在unionin class的定义中NonEmpty：

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

4

2 回答 2

5

您的问题的答案与关系数据库非常相关 - 以及它们做出的明智选择。当数据库“联合”表时 - 智能控制器系统将围绕诸如“表 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 ！

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

于 2013-10-17T06:30:05.143 回答
2

关联性与性能无关。两个表达式可能通过关联性等价，但一个可能比另一个更难实际计算：

(23  * (14/2))  * (1/7)

是相同的

23  * ((14/2)  * (1/7))

但如果是我评估这两者，我会用第二个很快得出答案（23），但如果我强迫自己只用第一个，则需要更长的时间。

于 2013-10-17T05:50:07.393 回答