Scala学习笔记 A2/L1篇 - 集合 Collections

教材：快学Scala

chapter 13. 集合 Collections

集合=Collection 集=Set
所有集合都extends Iterable特质
集合分为三大类 Seq Set Map，几乎所有集合类都有mutable和immutable两个版本
List 要么为Nil(空表) 要么有head和tail 其中tail本身又是一个List
关于元素添加：+用于添加到无先后次序的集合中(Set Map)，+: :+用于添加到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 Map Predef.Map scala.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 整数序列只存储起始值、结束值和增值用 to until 构造
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

Scala学习笔记 A2/L1篇 - 集合 Collections