以下要点中的代码几乎逐字逐句地从Martin Odersky的Scala课程中的功能编程原则的课程中逐字逐句解读:
https://gist.github.com/aisrael/7019350
问题发生在第38行,union在类的定义中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)),联合操作将相对立即完成.
增加:这是一个更新的工作表,显示即使对于具有随机元素的较大集合/树,表达式((左∪右)∪其他)可以永远占用但(左∪(右∪其他))将立即完成.
您的问题的答案与关系数据库非常相关 - 以及他们做出的明智选择.当一个数据库"联合"表 - 一个智能控制器系统会做出一些决定,比如"表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
为了论证,假设union运算符通过连接的2个集合的SMALLEST获取O(N)个记录.这是合理的,每个键可以作为散列检索在另一个中查找:
A&B运行时= O(N)运行时= 500万 (假设该类足够智能,可以使用两者中较小的一个进行查找)
所以
(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!
总而言之,这个问题只是一小部分说明了数据库设计中的一些复杂思维以及该软件中发生的智能优化.这些东西并不总是在编程语言中自动发生,除非你用这种方式编码,或者使用某种类型的库.例如,您可以编写一个需要多个集合的函数,并智能地决定联合顺序.但是,如果必须混入其他一系列操作,这个问题就变得难以置信了.希望这会有所帮助.