集合库中有一种generic变种,如GenTraversableOnce、GenIterator和GenSeq。该特质不确保线性执行或并行执行,在并行集合的遍历顺序是不确保的。
Traversable特质定义了一个foreach方法。foreach方法是一个内部迭代器,其接受一个函数作为参数,对集合的每个元素应用该函数。
Traversable特质没有提供任何在foreach里停止遍历的方法。为了使某些操作更高效,库使用预初始化的异常来提前跳出迭代。
内部迭代&外部迭代
import java.io.FileReader
import java.io.BufferedReader
import java.io.File
class FileLineTraversable(file: File) extends Traversable[String] {
override def foreach[U](f: String => U): Unit = {
println("Opening file")
val input = new BufferedReader(new FileReader(file))
try {
var line = input.readLine
while (line != null) {
f(line)
line = input.readLine
}
println("Done iterating file")
} finally {
println("Closing file")
input.close()
}
}
}
import java.io.FileReader import java.io.BufferedReader import java.io.File defined class FileLineTraversable
上面定义了一个Traversable,它打开一个文件,遍历文件的每一行。
val x = new FileLineTraversable(new File("test.txt"))
Opening file Done iterating file Closing file Opening file Done iterating file Closing file
x: FileLineTraversable = cmd0( "Line 1", "Line 2", "Line 3", "Line 4", "Line 5", "Line 6" )
// 遍历文件,并且遍历每一行,把行拆分成词,最后构造一个词的列表,结果是一个Traversable[String]
for {
line <- x
word <- line.split("\\s+")
} yield word
Opening file Done iterating file Closing file
res2: Traversable[String] = List( "Line", "1", "Line", "2", "Line", "3", "Line", "4", "Line", "5", "Line", "6" )
for {
line <- x.take(2)
word <- line.split("\\s+")
} yield word
Opening file Closing file
res3: Traversable[String] = List("Line", "1", "Line", "2")
FileLineTraversable调用了take方法抽取集合的前n个元素,这里“Done iterating file”没有打印。
这是因为Traversable类有一个在必要时高效停止foreach的手段,就是抛出scala.util.control.ControlThrowable。这是一种预分配的异常,JVM能够高效地抛出和捕获它。这样做法的缺点是take方法实际上会多取一个元素才抛出异常终止迭代。
由于foreach方法不支持高效的随机访问,所以其对很多算法都是次优的选择,我们可以通过Iterable的外部迭代器来解决。
Iterable特质提供了iterator方法,iterator方法返回一个能用来遍历集合元素的外部迭代器。这个类允许只是用集合部分元素的方法比Traversable更早提前停止迭代,从而在性能上比Traversable稍有提高。Iterable特质应该用在明确需要外部迭代器,但不需要随机访问的应用场景。
迭代器支持hasNext和next方法。
Iterable特质的主要优点之一是有能力高效地合作迭代两个集合。
val names = Iterable("Josh", "Jim")
val address = Iterable("123 Anyroad", "125 Anyroad")
val n = names.iterator
val a = address.iterator
names: Iterable[String] = List("Josh", "Jim") address: Iterable[String] = List("123 Anyroad", "125 Anyroad") n: Iterator[String] = non-empty iterator a: Iterator[String] = non-empty iterator
while(n.hasNext && a.hasNext) {
println(n.next + " lives at " + a.next)
}
Josh lives at 123 Anyroad Jim lives at 125 Anyroad
Scala提供了zip方法,用来把两个集合压缩成一个pair的集合
names.iterator zip address.iterator map {
case (n, a) => n+ " lives at " + a
} foreach println
Josh lives at 123 Anyroad Jim lives at 125 Anyroad
当在可变集合上使用外部迭代器时候,可能迭代器不知道集合发生了变化
val x = collection.mutable.ArrayBuffer(1, 2, 3)
val i = x.iterator
x: collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 2, 3) i: Iterator[Int] = non-empty iterator
x.remove(0, 3)
i.hasNext
res8_1: Boolean = true
i.next
java.lang.IndexOutOfBoundsException: 0 scala.collection.mutable.ResizableArray$class.apply(ResizableArray.scala:43) scala.collection.mutable.ArrayBuffer.apply(ArrayBuffer.scala:48) scala.collection.IndexedSeqLike$Elements.next(IndexedSeqLike.scala:65) cmd9$$user$$anonfun$1.apply$mcI$sp(Main.scala:81)
上面remove移除了集合中的全部元素,由于迭代器是外部的,它不知道背后集合已经变化,hasNext方法返回了true,调用next方法时却抛出了异常。
Seq特质是用过length和apply方法定义的。apply方法用来根据序号进行索引操作,length返回集合的大小。Seq特质不对索引或length的性能做任何保证。
如果元素插入集合的顺序是很重要的,而且允许重复元素,那么应该使用Seq。
Seq经常被用在抽象方法里,因为算法经常以其两个子类之一作为目标数据结果:LinearSeq和IndexedSeq。
// 该示例是通过滑动窗口计算元素和
val x = Seq(2, 1, 30, -2, 20, 1, 2, 0)
x.tails map(_.take(2)) filter(_.length > 1) map (_.sum) toList
x: Seq[Int] = List( 2, 1, 30, -2, 20, 1, 2, 0 ) res10_1: List[Int] = List(3, 31, 28, 18, 21, 3, 2)
滑动窗口是通过使用tails方法创建的,tails方法返回一个集合的tail迭代器。也就是说,tails产生的迭代器组的每个迭代器都比前一个迭代器少一个元素。此外,还可以使用Scala提供的sliding方法来代替tails:
x.sliding(2) map (_.sum) toList
res12: List[Int] = List(3, 31, 28, 18, 21, 3, 2)
LinearSeq特质代表能够分割为头元素+尾集合的集合。该特质是通过三个“假定高效”的抽象方法来定义的,分别是isEmpty、head和tail。
Stack是LinearSeq的典型代表,下面的例子是在一个遍历树算法里如何把LinearSeq用作堆栈。
// define a binary tree structure
sealed trait BinaryTree[+A]
case object NilTree extends BinaryTree[Nothing]
case class Branch[+A](value: A,
lhs: BinaryTree[A],
rhs: BinaryTree[A]) extends BinaryTree[A]
case class Leaf[+A] (value: A) extends BinaryTree[A]
defined trait BinaryTree defined object NilTree defined class Branch defined class Leaf
// define algorithm to traverse the binary tree
import scala.collection.LinearSeq
import scala.annotation.tailrec
def traverse[A, U](t: BinaryTree[A])(f: A => U): Unit = {
@tailrec
def traverseHelper(current: BinaryTree[A],
next: LinearSeq[BinaryTree[A]]): Unit =
current match {
case Branch(value, lhs, rhs) =>
f(value)
traverseHelper(lhs, rhs +: next)
case Leaf(value) if !next.isEmpty =>
f(value)
traverseHelper(next.head, next.tail)
case Leaf(value) => f(value)
case NilTree if !next.isEmpty =>
traverseHelper(next.head, next.tail)
case NilTree => ()
}
traverseHelper(t, LinearSeq())
}
import scala.collection.LinearSeq import scala.annotation.tailrec defined function traverse
traverseHelper实现了遍历树的核心功能,该方法接受当前要遍历的树和下一个LinearSeq,其中包含之后要迭代的二叉树元素。模式匹配的规则是:
val atree = Branch(1, Leaf(2), Branch(3, Leaf(4), NilTree))
traverse(atree)(println)
1 2 3 4
atree: Branch[Int] = Branch(1, Leaf(2), Branch(3,Leaf(4),NilTree))
当需要把一个普通递归的算法转化成尾递归或循环算法时,在堆(heap)上手工创建个栈(stack),然后用这个栈来完成实际功能是一种常见的做法。在使用函数式风格的尾递归算法时,LinearSeq是个恰当的选择。
IndexedSeq在随机访问时更为高效,也就是说,其访问元素的开销应该是常量或接近常量。这种集合类型适用于大多数一般的、不涉及头尾分解的算法。
val x = IndexedSeq(1, 2, 3)
x.updated(1, 5)
x: IndexedSeq[Int] = Vector(1, 2, 3) res4_1: IndexedSeq[Int] = Vector(1, 5, 3)
上面使用IndexedSeq对象定义的工厂方法创建IndexedSeq实例,默认情况下,这会创建一个不可变的Vector。IndexedSeq有个update方法,该方法接受一个下标和新值,返回用新值修改了下标位置上的值的新集合。
IndexedSeq用apply方法来根据下标取值,在Scala里,apply方法调用可以省略。
x.apply(2)
res5: Int = 3
x(2)
res6: Int = 3
Set集合类型代表一种其每个元素都是唯一的结合,至少对==方法来说是唯一。当需要测试一个集合是否包含某个元素或者要确保集合里没有重复元素的时候,Set是很好用的集合类型。
Scala支持三种类型的不可变和可变Set:TreeSet、HashSet和BitSet:
- TreeSet用红黑树实现,具有O(logn)的随机访问复杂度。要创建一个TreeSet,必须提供隐式的Ordering类型类,以便能执行小于和大于比较(因为查找元素时需要比较期望值大小)
val errorcodes = Map(1 -> "O NOES", 2 -> "KTHXBAI", 3 -> "ZOMG")
errorcodes: Map[Int, String] = Map( 1 -> "O NOES", 2 -> "KTHXBAI", 3 -> "ZOMG" )
errorcodes(1)
res8: String = "O NOES"
// Map能用做从键类型到值类型的偏函数
List(1, 3) map errorcodes
res9: List[String] = List("O NOES", "ZOMG")
Scala还提供了当键不存在时返回默认值的能力
val errorcodes = Map(1 -> "O NOES", 2 -> "KTHXBAI", 3 -> "ZOMG").withDefaultValue("Error key")
errorcodes: Map[Int, String] = Map( 1 -> "O NOES", 2 -> "KTHXBAI", 3 -> "ZOMG" )
errorcodes(4)
res11: String = "Error key"