教材：快學(xué)Scala
chapter 13. 集合 Collections
- 集合=Collection 集=Set
- 所有集合都extends Iterable特質(zhì)
- 集合分為三大類
SeqSetMap，幾乎所有集合類都有mutable和immutable兩個(gè)版本 -
List要么為Nil(空表) 要么有head和tail其中tail本身又是一個(gè)List - 關(guān)于元素添加：
+用于添加到無(wú)先后次序的集合中(SetMap)，+::+用于添加到Seq++串接集合---移除元素
13.1 主要的集合traits
- Iterable：能生成用來(lái)訪問(wèn)集合中所有元素的迭代器
val coll = ... // some Iterable
val iter = coll.iterator
while (iter.hasNext)
iter.next() // do something
-
Seq有先后次序的值的序列(數(shù)組/列表)IndexedSeq允許下標(biāo)快速訪問(wèn)元素 如ArrayBuffer -
Set一組沒(méi)有先后次序的值SortedSet以排序后的順序訪問(wèn)元素 -
Map一組kv對(duì)偶SortedMap按照鍵排序訪問(wèn)元素 - 與Java相比的改進(jìn)：
Scala：Map|Seq|Set→Iterable
Java：Set|List|Queue→Collection,Hashtable|Hashmap|SortedMap→Map
Scala：ArrayBuffer→IndexedSeq,List|LinkedList→LinearSeq數(shù)組和列表沒(méi)有直接繼承同一個(gè)trait
Java：ArrayList|LinkedList→List - 統(tǒng)一創(chuàng)建原則(uniform creation principle) 所有Scala集合都有一個(gè)帶apply方法的伴生對(duì)象，用來(lái)構(gòu)建該集合的實(shí)例
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集合從不改變，可以安全地共享其引用 每一步添加|刪除|修改操作都生成一個(gè)新的集合 - 默認(rèn)的是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的不可變版本 下標(biāo)訪問(wèn) 樹形結(jié)構(gòu)實(shí)現(xiàn)(32叉樹)
Range 整數(shù)序列 只存儲(chǔ)起始值、結(jié)束值和增值 用tountil構(gòu)造 - mutable
Array是Java數(shù)組實(shí)現(xiàn)，Array[T]在JVM就是一個(gè)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，要么是一個(gè)head元素加一個(gè)tail，而tail又是一個(gè)List
val digits = List(4, 2) // head = 4, tail = List(2)
9 :: List(4, 2) // List(9, 4, 2) 等價(jià)于 9::4::2::Nil 等價(jià)于 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) // 將列表析構(gòu)成head和tail
}
List(9, 4, 2).sum // 最方便
13.5 mutable.LinkedList|DoubleLinkedList
對(duì)應(yīng)傳統(tǒng)單向鏈表(LinkedList)/雙向鏈表(DoubleLinkedList)的定義，有next和prev指針，節(jié)點(diǎn)元素elem
修改某個(gè)節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)：cur = LinkedList.empty 不能賦值為Nil 更不能賦值為null會(huì)產(chǎn)生空指針錯(cuò)誤
// 將鏈表上所有負(fù)值改成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
}
// 鏈表上每?jī)蓚€(gè)元素去掉一個(gè)
var cur = lst
while (cur != Nil && cur.next != Nil) {
cur.next = cur.next.next
cur = cur.next
}
13.6 集 Set
- 不重復(fù)元素的集合，默認(rèn)是哈希集實(shí)現(xiàn)，在哈希集上查找比在數(shù)組和列表快得多
- 兩種有序的集：可變的鏈?zhǔn)焦＜?、排序?br>
mutable.LinkedHashSet 記住元素被插入的順序，通過(guò)維護(hù)一個(gè)鏈表
SortedSet 排序后的順序，用紅黑樹實(shí)現(xiàn) - 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 添加/刪除元素的操作符
帶:的操作符 :偏向集合操作數(shù)一側(cè)，元素::lst添加元素 lst2:::lst合并列表
Seq:+元素向后追加元素，元素+:Seq向前追加元素
無(wú)序集合+元素 無(wú)序集合+(e1,e2,...) 適用于Map Set
集合-元素 集合-(e1,e2,...) 集合--集合 移除元素
集合++集合 合并集合
對(duì)于列表，優(yōu)先使用:: :::
13.8 常用方法
- trait Iterable
head 第一個(gè)元素 last 最后一個(gè)元素 headOption lastOption 以O(shè)ption返回
tail init 除去第一個(gè)/最后一個(gè)元素剩下部分
count(fun) 計(jì)數(shù)符合條件 forall(fun) 是否全部滿足 exist(fun) 是否存在
length isEmpty
filter filterNot partition(fun) 將filter和filterNot的結(jié)果組成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) 補(bǔ)齊元素fill至長(zhǎng)度n
reverse 序列反向
sorted 使用元素本身大小排序 x < y
sortWith(less) 使用二元函數(shù)less排序 less(x, y) = x < y
sortBy(f) 根據(jù)f(x)排序 f(x) < f(y)
permutations 遍歷全排列的迭代器
combination(n) 遍歷長(zhǎng)度為n的組合的迭代器 - 統(tǒng)一返回類型(uniform return type)原則：這些方法不改變?cè)?，而是返回一個(gè)與原集合類型相同的新集合
13.9 Mapping a Function
map flatMap collect foreach
for (n <- names) yield n.toUpperCase 等價(jià)于 names.map(_.toUpperCase)
collect用于偏函數(shù)(partial function) 即沒(méi)有對(duì)所有可能輸入進(jìn)行定義的函數(shù)
"-3++4".collect { case '+' => 1; case '-' => -1 } // Vector(-1, 1, 1)
13.10 化簡(jiǎn)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 第一個(gè)為柯里化參數(shù)，通過(guò)初始值類型推斷操作符的類型定義
(0 /: List(1, 7, 2, 9))(_ - _) // 等價(jià)于foldLeft, :\ 是foldRight
// foldLeft取代循環(huán) 統(tǒng)計(jì)字母頻率
(Map[Char, Int]() /: "Mississippi") { (m, c) => m + (c -> (m.getOrElse(c, 0) + 1)) }
// scan：就是存儲(chǔ)fold中間的每一步結(jié)果
(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方法獲得集合的迭代器 用于完整構(gòu)造需要巨大開銷的集合，例如Source.fromFile -
grouped(n)(分成n組)sliding(n)(大小為n的滑窗) 返回一個(gè)迭代器
val it1 = (1 to 100).grouped(10)
val it2 = (1 to 100).sliding(10)
- 利用迭代器遍歷
while (iter.hasNext) { iter.next }for (elem <- iter) { elem } -
Iterator類定義了一些與集合方法使用起來(lái)完全相等的方法除head,last,tail,init,takeRight等意外都支持，使用部分方法后迭代器將指向末尾不能再用 - 可以先用toArray toSeq等等把元素拷到新集合再處理
13.13 流Stream
流是迭代器的immutable替代品，是一個(gè)尾部被懶計(jì)算的不可變列表
#:: 構(gòu)造流操作符
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, ?) 流的方法是懶執(zhí)行的
// 強(qiáng)制求所有值，先用take，再用force 【注意 不要直接force】
squares.take(50).force
// 迭代器轉(zhuǎn)換為流 toStream
val words = Source.fromFile("xxx.txt").getLines.toStream
13.14 懶視圖 Lazy Views
集合的view方法：懶操作集合的計(jì)算，且不緩存計(jì)算結(jié)果，每次調(diào)用重新計(jì)算
val powers = (0 until 1000).view.map(pow(10, _)) // 此時(shí)一個(gè)值都沒(méi)有計(jì)算
powers(100) // 計(jì)算pow(10,100) 但不緩存值
(0 to 1000).map(pow(10, _)).map(1 / _) // 有中間計(jì)算結(jié)果的集合
(0 to 1000).view.map(pow(10, _)).map(1 / _) // 對(duì)每個(gè)元素 兩個(gè)map同時(shí)執(zhí)行不需要構(gòu)建中間集合
13.15 與Java集合的互操作
Java的集合和Scala的集合之間互相轉(zhuǎn)換的方法 JavaConversions
13.16 線性安全的集合
用于多線程訪問(wèn)一個(gè)可變集合時(shí)確保線性安全
方法1. 使用Scala的同步集合 Synchronized*
* 可以是 Buffer Map PriorityQueue Queue Set Stack
方法2. 使用java.util.concurrent包中的類，再轉(zhuǎn)換為Scala集合
13.17 并行集合
par方法返回集合的一個(gè)并行實(shí)現(xiàn) 使之盡可能的并行執(zhí)行集合方法
coll.par.sum
如果并行運(yùn)算修改了共享的變量(如計(jì)數(shù)器的實(shí)現(xiàn))，則共享變量的結(jié)果無(wú)法預(yù)知
練習(xí)答案
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
