Scala学习系列-集合3：视图和迭代器

Posted on Edited on In Views:

迭代器和视图是Scala集合中处理大规模数据集的两个重要的工具，本篇详细介绍了视图和迭代器的原理以及使用方式。

视图(View)

问题的产生

我们首先来看一下下面这两行代码背后发生了什么：

1
2
val c = Vector(1 to 10: _*)
val y = c.map(_ + 1).map(_ * 2)

immutable.Vector的map()方法继承自特质TraversableLike中的map()，其定义如下：

1
2
3
4
5
6
7
8
9
10
def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  def builder = { // extracted to keep method size under 35 bytes, so that it can be JIT-inlined
    val b = bf(repr)
    b.sizeHint(this)
    b
  }
  val b = builder
  for (x <- this) b += f(x)
  b.result
}

可以看出，对于每次map()调用，都会有一个新的数据结果生成出来。所以代码行c.map(_ + 1).map(_ * 2)会有两个数据结果生成出来，其中：

  • c.map(_ + 1)会生成一份数据x；
  • .map(_ * 2)在结果x基础上做进一步转换，生成最后的数据y；

显然，如果向量c是一份巨量数据，那么对于这条数据链路：c -> x -> y，其性能开销（存储和计算开销）将会是非常可观的。那么有没有途径可以将其简化为：c -> y呢？

一种解决思路是将两次map变换合并为一次map变换，即c.map((_ + 1) * 2)，这对我们的例子程序是完全可行的，因为我们对于代码有完全的掌控能力。但是假如在团队合作或使用了第三方类库时，我们有时是不能完全掌控代码的，这时就该视图上场了！

使用视图

使用视图的一般形式为：1)调用集合的view方法获得集合的视图表示；2)对视图进行一系列转换，视图转换操作是lazy的，并不会实际执行；3)调用视图的force方法，命令视图执行其保存的转换操作，返回操作的结果。

  • 示例1

以下代码是使用视图进行转换的一个例子：

1
2
3
4
5
scala> val c = Vector(1 to 10: _*)
v: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> val y = (c.view.map(_ + 1).map(_ * 2)).force
y: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

我们来分步拆解上面例子的执行过程：

首先，c.view获得到集合的视图表示，此例中集合c的类型为向量，获得的视图类型为SeqView，其中第一个类型参数表示的是底层元素的数据类型，第二个类型参数表示的是当调用force时返回的数据类型，如下，

1
2
scala> val cv = c.view
cv: scala.collection.SeqView[Int,scala.collection.immutable.Vector[Int]] = SeqView(...)

然后，对视图cv进行进行一次map转换，得到值变量cvm的类型为SeqView[Int,Seq[_]]，注意，cv和cvm的类型中第二个类型参数是不同的，并且输出结果等号右边给出了SeqViewM的字样，它表示cvm视图是通过对cv视图进行map操作转换而来，如下，

1
2
scala> val cvm = cv.map(_ + 1)
cvm: scala.collection.SeqView[Int,Seq[_]] = SeqViewM(...)

然后，再对视图cvm进行进行一次map转换，如下，

1
2
scala> val cvmm = cvm.map(_ * 2)
cvmm: scala.collection.SeqView[Int,Seq[_]] = SeqViewMM(...)

最后，对视图cvmm调用force方法，执行保存在视图中的操作，如下，

1
2
scala> val y = cvmm.force
y: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
  • 示例2

示例1是对不可变集合使用视图，示例2中，我们对可变序列进行视图操作。可变序列的视图中的很多转换方法提供了对于原始序列的一个视窗，使用这种视窗可以有选择性地更新底层原始可变序列。

我们使用数组作为可变序列，如下：

1
2
scala> val arr = (0 to 9).toArray
arr: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

调用view获取数组的视图表示，注意该视图所在的包是可变集合包scala.collection.mutable，如下：

1
2
3
4
5
scala> val arrV = arr.view
arrV: scala.collection.mutable.IndexedSeqView[Int,Array[Int]] = SeqView(...)

scala> val subarrV = arrV.slice(3, 6)
subarrV: scala.collection.mutable.IndexedSeqView[Int,Array[Int]] = SeqViewS(...)

定义有一个对可变序列集合中的元素取反的函数negate()，然后以subarrV视图作为入参数进行调用，如下：

1
2
3
4
5
scala> def negate(xs: collection.mutable.Seq[Int]) =
     |   for (i <- 0 until xs.length) xs(i) = -xs(i)
negate: (xs: scala.collection.mutable.Seq[Int])Unit

scala> negate(subarrV)

检查原始可变数组arr，其索引3、4、5处的值被取反，如下：

1
2
scala> arr
res10: Array[Int] = Array(0, 1, 2, -3, -4, -5, 6, 7, 8, 9)

注意，使用视图的一个主要原因是性能，但是不要误以为在任何情况下使用视图就会比直接使用集合要好。对于小型集合而言，组织视图和应用闭包所带来的开销通常要大于省略中间结果的收益。

总的来说，视图是调和性能和模块化的强大工具。但是，为了不陷入延迟计算的细节，应该尽量只在纯函数的场景下使用视图。最好不要将既创建了新集合又有副作用的操作用于视图。

视图原理

集合中有很多方法可以实现集合到集合的转换，如map、filter和++等，我们将这样的集合到集合的转换操作称之为“转换器(transformer)”。实现“转换器”主要有两种方式，严格的和非严格的(惰性的)，其中：

  • 采用严格的方式，新集合的所有元素作为“转换器”的结果被完全构造出来；
  • 采用非严格/惰性的方式，构造的只是作为结果集合的代理，其元素只在需要它们时才会被构造；

Scala中的集合默认都是采用严格方式来定义它们的“转换器”。

TODO

特质SeqLike：

1
2
3
4
5
6
override def view = new SeqView[A, Repr] {
  protected lazy val underlying = self.repr
  override def iterator = self.iterator
  override def length = self.length
  override def apply(idx: Int) = self.apply(idx)
}

迭代器(Iterator)

迭代器并不是集合，它是逐个访问集合元素的一种方式。Iterator特质中有两个基本方法：hasNext和next()，该特质中的其它方法都是依赖这两个方法进行实现，其中：

  • it.hasNext检查迭代器是否还有元素；
  • it.next()返回迭代器的下一个元素，并推进迭代器的状态；如果没有元素可以被返回了，那么将抛出NoSuchElementException异常；

遍历迭代器的一般形式如下：

1
2
while (it.hasNext)
  /* do something with it.next() */

这个一般形式与Iterator.foreach()效果是一样的，以下是foreach()的定义：

1
def foreach[U](f: A => U) { while (hasNext) f(next()) }

迭代器工作原理

Iterator.map()是Iterator中最简单的转换操作之一，通过对该方法的分析，我们初步窥探一下迭代器的工作机制。

首先，先来看一下Iterator.map()的实现，如下：

1
2
3
4
def map[B](f: A => B): Iterator[B] = new AbstractIterator[B] {
  def hasNext = self.hasNext
  def next() = f(self.next())
}

它返回的是一个新的AbstractIterator迭代器对象，该迭代器中：

  • hasNext，直接代理给上游迭代器实例的self.hasNext来执行；
  • next()，由上游迭代器的self.Next()的结果经过f函数转换作为其输出；

可以看出map操作本身并不会产生中间数据结果，它返回的是一个AbstractIterator的具体实现。抽象类AbstractIterator直接继承自Iterator，并且没有添加任何代码，它的目的是方便实例化具体的Iterator实例。

并且Iterator中提供了特质Traversable、Iterable和Seq中的大部分的方法，这些方法的实现与map()类似，不会有中间数据生成。


我们通过一个具体的示例来说明：

首先，定义迭代器ita和itb，itb是通过ita.map()转换而来，如下：

1
2
3
4
5
scala> val ita = Iterator("a", "number", "of", "words")
ita: Iterator[String] = <iterator>

scala> val itb = ita.map(_.length)
itb: Iterator[Int] = <iterator>

然后，打印itb.next()，输出1；接着打印ita.next()，输出number；可以看出，itb.next()的调用推进了上游迭代器ita的状态，所以ita.next()的输出是number；依次，直到ita.next()和itb.next()抛出NoSuchElementException，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
scala> println(itb.next())
1

scala> println(ita.next())
number

scala> println(itb.next())
2

scala> println(ita.next())
words

scala> println(itb.next())
java.util.NoSuchElementException: next on empty iterator

scala> println(ita.next())
java.util.NoSuchElementException: next on empty iterator

带缓冲的迭代器

特质BufferedIterator提供了一个方法head用于返回迭代器的下一个元素，而不推进迭代器的状态，该方法与next()都具有返回下一个元素的功能，只是head不推进迭代器的状态，而next()会推进迭代器的状态。

我们来看一下特质BufferedIterator的唯一的实现：collection.IndexedSeqLike.Elements，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def next(): A = {
  if (index >= end)
    Iterator.empty.next()

  val x = self(index)
  index += 1
  x
}

def head = {
  if (index >= end)
    Iterator.empty.next()

  self(index)
}

两个方法的实现几乎是一样的，只是next()在获得下一个元素（self(index)）后，将索引指示器推进了一步（index += 1）。

那么，如何获得带缓冲的迭代器呢？答案是，调用迭代器的buffered方法，示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
scala> val it = Iterator(1, 2, 3, 4)
it: Iterator[Int] = <iterator>

scala> val bit = it.buffered
bit: scala.collection.BufferedIterator[Int] = <iterator>

scala> bit.head // 返回下一个元素1，不推进状态，下一次调用next()仍返回1
res29: Int = 1

scala> bit.next() // 返回下一个元素1，推进状态，下一次调用next()仍返回2
res30: Int = 1

scala> bit.next()
res31: Int = 2

迭代器框架

此表为Scala中Iterator的层级结构
collection collection.immutable collection.parallel io
<<t>>collection.Iterator
<<c>>collection.AbstractIterator
<<c>>GroupedIterator <<c>>VectorIterator <<c>>LineIterator
private<<c>>SliceIterator <<c>>StreamIterator <<c>>BufferedLineIterator
<<c>>IndexedSeqLike.Elements private<<c>>IntMapIterator
private<<c>>LongMapIterator
private<<c>>TrieIterator
<<t>>collection.BufferedIterator
<<c>>IndexedSeqLike.Elements
<<t>>collection.parallel.Splitter
<<t>>PreciseSplitter
<<t>>IterableSplitter

Notes

本文基于Scala2.12.13

参考

  1. https://docs.scala-lang.org/overviews/collections-2.13/views.html
  2. https://docs.scala-lang.org/overviews/collections-2.13/iterators.html
  3. 《Scala编程 第3版 24章》