集合有许多用于构造新集合的方法。例如 map
、filter
或 ++
。我们称此类方法为转换器,因为它们至少将一个集合作为其接收器对象,并生成另一个集合作为其结果。
有两种主要方法来实现转换器。一种是严格的,即转换器会生成一个包含所有元素的新集合。另一种是非严格的或惰性的,即只为结果集合构造一个代理,并且只在需要时才构造其元素。
以下惰性映射操作实现是一个非严格转换器的示例
def lazyMap[T, U](iter: Iterable[T], f: T => U) = new Iterable[U] {
def iterator = iter.iterator.map(f)
}
def lazyMap[T, U](iter: Iterable[T], f: T => U) = new Iterable[U]:
def iterator = iter.iterator.map(f)
请注意,lazyMap
构造了一个新的 Iterable
,而不会遍历给定集合 coll
的所有元素。相反,给定的函数 f
会应用于新集合的 iterator
的元素(在需要时)。
Scala 集合在所有转换器中默认是严格的,除了 LazyList
,它以惰性方式实现所有转换器方法。但是,有一种系统的方式可以将每个集合转换为惰性集合,反之亦然,该方式基于集合视图。视图是一种特殊类型的集合,它表示某个基础集合,但以惰性方式实现所有转换器。
要从集合转到其视图,可以在集合上使用 view
方法。如果 xs
是某个集合,则 xs.view
是相同的集合,但所有转换器都以惰性方式实现。要从视图返回到严格集合,可以使用 to
转换操作,并使用严格集合工厂作为参数(例如 xs.view.to(List)
)。
我们来看一个示例。假设你有一个 Int 向量,你希望连续对其映射两个函数
scala> val v = Vector(1 to 10: _*)
val v: scala.collection.immutable.Vector[Int] =
Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
scala> v.map(_ + 1).map(_ * 2)
val res5: scala.collection.immutable.Vector[Int] =
Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
scala> val v = Vector((1 to 10)*)
val v: scala.collection.immutable.Vector[Int] =
Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
scala> v.map(_ + 1).map(_ * 2)
val res5: scala.collection.immutable.Vector[Int] =
Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
在最后一条语句中,表达式 v map (_ + 1)
构造了一个新向量,然后通过第二次调用 map (_ * 2)
将其转换为第三个向量。在许多情况下,从第一次调用 map 构造中间结果有点浪费。在上面的示例中,使用两个函数 (_ + 1)
和 (_ * 2)
的组合进行一次映射会更快。如果你在同一位置可以使用这两个函数,则可以手动执行此操作。但通常,数据结构的连续转换是在不同的程序模块中完成的。然后,融合这些转换会破坏模块化。避免中间结果的更通用方法是先将向量转换为视图,然后将所有转换应用于视图,最后强制视图转换为向量
scala> val w = v.view.map(_ + 1).map(_ * 2).to(Vector)
val w: scala.collection.immutable.Vector[Int] =
Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
让我们再次逐个执行此操作序列
scala> val vv = v.view
val vv: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)
应用程序 v.view
为你提供一个 IndexedSeqView[Int]
,即一个惰性求值的 IndexedSeq[Int]
。与 LazyList
一样,视图的 toString
操作不会强制视图元素,这就是 vv
的内容显示为 IndexedSeqView(<not computed>)
的原因。
将第一个 map
应用于视图会得到
scala> vv.map(_ + 1)
val res13: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)
map
的结果是另一个 IndexedSeqView[Int]
值。这本质上是一个包装器,用于记录需要对向量 v
应用带有函数 (_ + 1)
的 map
的事实。但是,它不会在视图被强制之前应用该映射。现在,让我们将第二个 map
应用于最后一个结果。
scala> res13.map(_ * 2)
val res14: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)
最后,强制最后一个结果会得到
scala> res14.to(Vector)
val res15: scala.collection.immutable.Vector[Int] =
Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
两个存储的函数在 to
操作执行期间被应用,并构造了一个新向量。这样,不需要中间数据结构。
一般来说,应用于视图的转换操作绝不会构建新的数据结构,而访问视图的元素有效地遍历了底层数据结构尽可能少的元素。因此,视图具有以下属性:(1) 转换器的复杂度为 O(1)
,(2) 元素访问操作与底层数据结构的复杂度相同(例如,对 IndexedSeqView
的索引访问是常量,否则是线性的)。
不过,这些规则有一些例外。例如,sorted
操作无法满足这两个属性。事实上,必须遍历整个底层集合才能找到其最小元素。一方面,如果在调用 sorted
时发生了该遍历,那么第一个属性将被违反(sorted
在视图上不会是惰性的),另一方面,如果在访问结果视图元素时发生了该遍历,那么第二个属性将被违反。对于此类操作,我们决定违反第一个属性。这些操作被记录为“始终强制集合元素”。
使用视图的主要原因是性能。您已经看到,通过将集合切换到视图可以避免构建中间结果。这些节省可能非常重要。作为另一个示例,考虑在单词列表中查找第一个回文的问题。回文是一个从后往前读和从前往后读都相同的单词。以下是必要的定义
def isPalindrome(x: String) = x == x.reverse
def findPalindrome(s: Seq[String]) = s.find(isPalindrome)
现在,假设你有一段很长的单词序列,并且你想要在该序列的前一百万个单词中找到一个回文。你能重新使用 findPalindrome
的定义吗?当然,你可以编写
val palindromes = findPalindrome(words.take(1000000))
这很好地将获取序列的前一百万个单词和在其中查找回文这两个方面分开了。但是缺点是,它总是构建一个由一百万个单词组成的中间序列,即使该序列的第一个单词已经是回文。因此,可能有 999’999 个单词被复制到中间结果中,而之后根本不会检查它们。许多程序员会在这里放弃,编写自己的专门版本,在参数序列的某个给定前缀中查找回文。但是,使用视图,你无需这样做。只需编写
val palindromes = findPalindrome(words.view.take(1000000))
这同样很好地分隔了关注点,但它只会构建一个轻量级视图对象,而不是一个包含一百万个元素的序列。这样,你就不需要在性能和模块性之间进行选择。
在了解了视图的所有这些巧妙用法后,你可能会想知道为什么还要有严格集合?一个原因是,性能比较并不总是偏向于惰性集合而不是严格集合。对于较小的集合大小,在视图中形成和应用闭包的额外开销通常大于避免中间数据结构的收益。一个可能更重要的原因是,如果延迟操作有副作用,那么在视图中进行求值可能会非常混乱。
这里有一个示例,它困扰了几个 2.8 之前的 Scala 版本的用户。在这些版本中,Range
类型是惰性的,因此它实际上表现得像一个视图。人们尝试像这样创建许多 actor
val actors = for (i <- 1 to 10) yield actor { ... }
val actors = for i <- 1 to 10 yield actor { ... }
他们惊讶地发现,之后没有一个 actor 在执行,即使 actor 方法应该创建并启动一个 actor,该 actor 来自跟在它后面的大括号中包含的代码。要解释为什么什么都没有发生,请记住上面的 for 表达式等效于应用 map
val actors = (1 to 10).map(i => actor { ... })
由于之前 (1 to 10)
生成的范围表现得像一个视图,因此 map 的结果又是一个视图。也就是说,没有计算任何元素,因此,没有创建任何 actor!本来可以通过强制整个表达式的范围来创建 actor,但显然这不是让 actor 执行其工作的必要条件。
为了避免出现此类意外,当前的 Scala 集合库具有更规则的规则。除了惰性列表和视图之外的所有集合都是严格的。从严格集合到惰性集合的唯一方法是通过 view
方法。返回的唯一方法是通过 to
。因此,上面的 actors
定义现在将按预期的那样运行,它将创建并启动 10 个 actor。要恢复意外的先前行为,您必须添加一个显式的 view
方法调用
val actors = for (i <- (1 to 10).view) yield actor { ... }
val actors = for i <- (1 to 10).view yield actor { ... }
总之,视图是一种强大的工具,可以协调效率问题与模块化问题。但为了不纠缠于延迟求值方面,您应该将视图限制在纯函数代码中,其中集合转换没有副作用。最好避免的是视图和创建新集合且同时具有副作用的操作的混合。