教材：快学Scala
chapter 13. 集合 Collections
- 集合=Collection 集=Set
- 所有集合都extends Iterable特质
- 集合分为三大类
SeqSetMap，几乎所有集合类都有mutable和immutable两个版本 -
List要么为Nil(空表) 要么有head和tail其中tail本身又是一个List - 关于元素添加：
+用于添加到无先后次序的集合中(SetMap)，+::+用于添加到Seq++串接集合---移除元素
13.1 主要的集合traits
- Iterable：能生成用来访问集合中所有元素的迭代器
val coll = ... // some Iterable
val iter = coll.iterator
while (iter.hasNext)
iter.next() // do something
-
Seq有先后次序的值的序列(数组/列表)IndexedSeq允许下标快速访问元素 如ArrayBuffer -
Set一组没有先后次序的值SortedSet以排序后的顺序访问元素 -
Map一组kv对偶SortedMap按照键排序访问元素 - 与Java相比的改进：
Scala：Map|Seq|Set→Iterable
Java：Set|List|Queue→Collection,Hashtable|Hashmap|SortedMap→Map
Scala：ArrayBuffer→IndexedSeq,List|LinkedList→LinearSeq数组和列表没有直接继承同一个trait
Java：ArrayList|LinkedList→List - 统一创建原则(uniform creation principle) 所有Scala集合都有一个带apply方法的伴生对象，用来构建该集合的实例
Iterable(0xFF, 0xFF00, 0xFF0000)
Set(Color.RED, Color.GREEN, Color.BLUE)
Map(Color.RED -> 0xFF, Color.GREEN -> 0xFF00, Color.BLUE -> 0xFF0000)
SortedSet("hello", "world")
13.2 mutable immutable
-
immutable集合从不改变，可以安全地共享其引用 每一步添加|删除|修改操作都生成一个新的集合 - 默认的是immutable
MapPredef.Mapscala.collection.Map都是指scala.collection.immutable.Map
13.3 序列 Seq
- immutable
Vector|Range→<t>IndexedSeq→<t>Seq
List|Stream|Stack|Queue→<t>LinearSeq→<t>Seq
Vector ArrayBuffer的不可变版本 下标访问 树形结构实现(32叉树)
Range 整数序列 只存储起始值、结束值和增值 用tountil构造 - mutable
Array是Java数组实现，Array[T]在JVM就是一个T[]
ArrayBuffer→<t>IndexedSeq→<t>Seq
(Queue→MutableList)|LinkedList|DoubleLinkedList→<t>LinerSeq→<t>Seq
Stack→<t>Seq
PriorityQueue→<t>Iterable
13.4 immutable.List
List(不可变) LinkedList|DoubleLinkedList(可变)
递归定义列表：List要么是Nil，要么是一个head元素加一个tail，而tail又是一个List
val digits = List(4, 2) // head = 4, tail = List(2)
9 :: List(4, 2) // List(9, 4, 2) 等价于 9::4::2::Nil 等价于 9::(4::(2::Nil))
def sum(lst: List[Int]): Int = if (lst == Nil) 0 else lst.head + sum(lst.tail) // 递归
def sum2(lst: List[Int]): Int = lst match { // 递归 模式匹配
case Nil => 0
case h :: t => h + sum2(t) // 将列表析构成head和tail
}
List(9, 4, 2).sum // 最方便
13.5 mutable.LinkedList|DoubleLinkedList
对应传统单向链表(LinkedList)/双向链表(DoubleLinkedList)的定义，有next和prev指针，节点元素elem
修改某个节点为最后一个节点：cur = LinkedList.empty 不能赋值为Nil 更不能赋值为null会产生空指针错误
// 将链表上所有负值改成0
val lst = scala.collection.mutable.LinkedList(1, -2, 7, -9)
val cur = lst
while (cur != Nil) {
if (cur.elem < 0) cur.elem = 0
cur = cur.next
}
// 链表上每两个元素去掉一个
var cur = lst
while (cur != Nil && cur.next != Nil) {
cur.next = cur.next.next
cur = cur.next
}
13.6 集 Set
- 不重复元素的集合，默认是哈希集实现，在哈希集上查找比在数组和列表快得多
- 两种有序的集：可变的链式哈希集、排序集
mutable.LinkedHashSet 记住元素被插入的顺序，通过维护一个链表
SortedSet 排序后的顺序，用红黑树实现 - BitSet 位集
-
contains检查包含元素subsetOf检查包含子集
val digits = Set(1, 7, 2, 9)
digits contains 0 // false
Set(1, 2) subsetOf digits // true
- 并集/交集/差集
并集操作union或|或++
交集操作intersect或&
差集操作diff或&~或--
13.7 添加/删除元素的操作符
带:的操作符 :偏向集合操作数一侧，元素::lst添加元素 lst2:::lst合并列表
Seq:+元素向后追加元素，元素+:Seq向前追加元素
无序集合+元素 无序集合+(e1,e2,...) 适用于Map Set
集合-元素 集合-(e1,e2,...) 集合--集合 移除元素
集合++集合 合并集合
对于列表，优先使用:: :::
13.8 常用方法
- trait Iterable
head 第一个元素 last 最后一个元素 headOption lastOption 以Option返回
tail init 除去第一个/最后一个元素剩下部分
count(fun) 计数符合条件 forall(fun) 是否全部满足 exist(fun) 是否存在
length isEmpty
filter filterNot partition(fun) 将filter和filterNot的结果组成pair
takeWhile dropWhile span(fun) 组成pair
take drop splitAt(n) 组成pair takeRight dropRight slice(from, to)
mkString - trait Seq
contains(elem) containsSlice(Seq) startsWith(Seq) endsWith(Seq)
indexOf(elem) lastIndexOf(elem) indexOfSlice(Seq) indexWhere(fun)
padTo(n, fill) 补齐元素fill至长度n
reverse 序列反向
sorted 使用元素本身大小排序 x < y
sortWith(less) 使用二元函数less排序 less(x, y) = x < y
sortBy(f) 根据f(x)排序 f(x) < f(y)
permutations 遍历全排列的迭代器
combination(n) 遍历长度为n的组合的迭代器 - 统一返回类型(uniform return type)原则：这些方法不改变原集合，而是返回一个与原集合类型相同的新集合
13.9 Mapping a Function
map flatMap collect foreach
for (n <- names) yield n.toUpperCase 等价于 names.map(_.toUpperCase)
collect用于偏函数(partial function) 即没有对所有可能输入进行定义的函数
"-3++4".collect { case '+' => 1; case '-' => -1 } // Vector(-1, 1, 1)
13.10 化简reduce 折叠fold 扫描scan
List(1, 7, 2, 9).reduceLeft(_ - _) // ((1-7)-2)-9
List(1, 7, 2, 9).reduceRight(_ - _) // 1-(7-(2-9))
List(1, 7, 2, 9).foldLeft(0)(_ - _)) // 0-1-7-2-9 第一个为柯里化参数，通过初始值类型推断操作符的类型定义
(0 /: List(1, 7, 2, 9))(_ - _) // 等价于foldLeft, :\ 是foldRight
// foldLeft取代循环 统计字母频率
(Map[Char, Int]() /: "Mississippi") { (m, c) => m + (c -> (m.getOrElse(c, 0) + 1)) }
// scan：就是存储fold中间的每一步结果
(1 to 10).scanLeft(0)(_ + _) // Vector(0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55)
13.11 拉链zip
((price zip quantities) map { p => p._1 * p._2 }) sum
// zipAll 指定较短列表的缺省值
List(5.0, 20.0, 9.95).zipAll(List(10, 2), 0.0, 1) // List(5.0, 20.0, 9.95).zipAll(List(10, 2), 0.0, 1)
"Scala".zipWithIndex // Vector((S,0), (c,1), (a,2), (l,3), (a,4))
13.12 迭代器iterator
-
iterator方法获得集合的迭代器 用于完整构造需要巨大开销的集合，例如Source.fromFile -
grouped(n)(分成n组)sliding(n)(大小为n的滑窗) 返回一个迭代器
val it1 = (1 to 100).grouped(10)
val it2 = (1 to 100).sliding(10)
- 利用迭代器遍历
while (iter.hasNext) { iter.next }for (elem <- iter) { elem } -
Iterator类定义了一些与集合方法使用起来完全相等的方法除head,last,tail,init,takeRight等意外都支持，使用部分方法后迭代器将指向末尾不能再用 - 可以先用toArray toSeq等等把元素拷到新集合再处理
13.13 流Stream
流是迭代器的immutable替代品，是一个尾部被懒计算的不可变列表
#:: 构造流操作符
def numsFrom(n: BigInt): Stream[BigInt] = n #:: numsFrom(n + 1)
val tenOrMore = numsFrom(10) // Stream(10, ?) 懒求值
tenOrMore.tail.tail.tail // Stream(13, ?)
val squares = numsFrom(1).map(x => x * x) // Stream(1, ?) 流的方法是懒执行的
// 强制求所有值，先用take，再用force 【注意 不要直接force】
squares.take(50).force
// 迭代器转换为流 toStream
val words = Source.fromFile("xxx.txt").getLines.toStream
13.14 懒视图 Lazy Views
集合的view方法：懒操作集合的计算，且不缓存计算结果，每次调用重新计算
val powers = (0 until 1000).view.map(pow(10, _)) // 此时一个值都没有计算
powers(100) // 计算pow(10,100) 但不缓存值
(0 to 1000).map(pow(10, _)).map(1 / _) // 有中间计算结果的集合
(0 to 1000).view.map(pow(10, _)).map(1 / _) // 对每个元素 两个map同时执行不需要构建中间集合
13.15 与Java集合的互操作
Java的集合和Scala的集合之间互相转换的方法 JavaConversions
13.16 线性安全的集合
用于多线程访问一个可变集合时确保线性安全
方法1. 使用Scala的同步集合 Synchronized*
* 可以是 Buffer Map PriorityQueue Queue Set Stack
方法2. 使用java.util.concurrent包中的类，再转换为Scala集合
13.17 并行集合
par方法返回集合的一个并行实现 使之尽可能的并行执行集合方法
coll.par.sum
如果并行运算修改了共享的变量(如计数器的实现)，则共享变量的结果无法预知
练习答案
def indexes(str: String) =
str.zipWithIndex.foldLeft(Map[Char, scala.collection.SortedSet[Int]]()){
(m, p) => m + (p._1 -> (m.getOrElse(p._1, scala.collection.SortedSet[Int]()) + p._2))
}
def indexes(str: String) =
str.zipWithIndex.foldLeft(Map[Char, List[Int]]()){
(m, p) => m + (p._1 -> (m.getOrElse(p._1, List[Int]()) :+ p._2))
}
def dropZeros(lst: List[Int]): List[Int] = lst match {
case Nil => Nil
case h :: t => if (h == 0) dropZeros(t) else h :: dropZeros(t)
}
def names2nums(s: Seq[String], m: Map[String, Int]) = s.flatMap(m.get(_))
// 看了github别人的答案，这里res必须为Any类型才可以，"since its the closest common parent type for String and T"
def myMkString[T](coll: Iterable[T], before: String, between: String, after: String) =
if (coll.isEmpty) before + after else before + coll.reduceLeft((res: Any, elem: T) => res + between + elem) + after
// reduceLeft sucks
def myMkString[T](coll: Iterable[T], before: String, between: String, after: String) =
if (coll.isEmpty) before + after else coll.foldLeft(before)((res, elem) => res + elem + between).init + after
myMkString[Int](List(1, 2, 3, 4, 5), "<", "-", ">")
myMkString[Int](List(), "<", "-", ">")
def reverse1(lst: List[Int]) = (lst :\ List[Int]())((e, l) => l :+ e)
def reverse2(lst: List[Int]) = (List[Int]() /: lst)((l, e) => e +: l)
def twoDimensionize(a: Seq[Int], n: Int) = a.grouped(n).toArray
