Scala 集合庫(一)
Scala是數據挖掘演算法領域最有力的編程語言之一,語言本身是面向函數,這符合了數據挖掘演算法的常用場景:在原始數據集上應用一系列的變換,Scala本身對集合操作提供了眾多強大的函數,能輕鬆的完成這些變換,這也正是Scala適合大數據領域的理由之一。
- 易用性:由20-50個方法選擇需要的,足以在幾個操作內解決大部分的集合問題。沒有必要被複雜的循環或遞歸所困擾。
- 簡潔:你可以通過單獨的一個詞來執行一個或多個循環。你也可以用輕量級的語法和組合輕鬆地快速表達功能性的操作,以致結果看起來像一個自定義的代數。
- 安全:Scala集合的靜態類型和函數性質意味著你在編譯的時候就可以捕獲絕大多數錯誤。
- 快速:集合操作已經在類庫里是調整和優化過。因此,使用集合通常是比較高效的。你也許能夠通過手動調整數據結構和操作來做的好一點,但是你也可能會由於一些次優的實現而做的更糟。不僅如此,集合類支持在多核處理器上並行運算。並行集合類支持有序集合的相同操作,你可以簡單地通過調用標準方法來把有序集合優化為一個並行集合。
- 通用:集合類提供了相同的操作在一些類型上。所以,你可以用相當少的辭彙完成大量的工作。例如,一個字元串從概念上講就是一個字元序列。因此,在Scala集合類中,字元串支持所有的序列操作。同樣的,數組也是支持的。
Scala 集合類分為immutable和mutable集合。mutable集合可以在適當的地方被更新或擴展。這意味著你可以修改,添加,移除一個集合的元素。而不可變集合類,與之相反,永遠不會改變。不過,你仍然可以模擬添加,移除或更新操作。但是這些操作將在每一種情況下都返回一個新的集合,同時使原來的集合不發生改變。
下圖顯示了scala.collection包中所有的集合類。這些都是高級抽象類或特性,它們通常具備和不可變實現一樣的可變實現。
下圖顯示scala.collection.immutable中的所有集合類。下圖顯示scala.collection.mutable中的所有集合類。集合類都被展示在了上面的圖中,這些類有很多的共性。e.g.,每一種集合都能用相同的語法創建,寫法是集合類名緊跟著元素。
Traversable(1, 2, 3)nIterable("x", "y", "z")nMap("x" -> 24, "y" -> 25, "z" -> 26)nSet(Color.red, Color.green, Color.blue)nSortedSet("hello", "world")nmutable.Buffer(x, y, z)nIndexedSeq(1.0, 2.0)nLinearSeq(a, b, c)nList(1, 2, 3)nHashMap("x" -> 24, "y" -> 25, "z" -> 26)n
Trait Traversable
Traversable是容器類的最高級別特徵,它唯一的抽象方法是foreach
def foreach[U](f: Elem => U)n
Traversable同時定義的很多具體方法
++ 兩個traversable對象連接在一起。
val T1 = Traversable(1, 2)nval T2 = Traversable(3, 4)nprintln(T1 ++ T2)n//output: List(1, 2, 3, 4)n
map 依次把集合的所有元素都調用函數f: A => B來生成一個新容器
val T1 = Traversable(1, 2, 3, 4)nval T2 = T1.map(x => x * x)n//output: List(1, 4, 9, 16)n
flatMap 從名字上可以看出來,先執行map,然後一個大巴掌將其拍扁。
val T1 = Traversable(Array(1, 2), Array(3, 4))nval T2 = T1.flatMap(x => x.map(y => y * y))n//output: List(1, 4, 9, 16)n
collect 通過對每個符合定義的元素調用偏函數f(偏函數是指僅定義了輸入參數的子集的函數),並把結果收集起來生成一個集合。
List(1, 3, 5, "Stanley") collect { case i: Int => i + 1 }n//output: List(2, 4, 6)n
集合類型轉換
val T1 = Traversable(1, 2, 3, 4)nT1.toArraynT1.toListnT1.toIterablenT1.toSeqnT1.toIndexedSeqnT1.toStreamnT1.toSetnTraversable((1,2),(3,4)).toMapn
Copy
import scala.collection.mutable.ArrayBuffernval T1 = Traversable(1, 2, 3, 4)nval B = ArrayBuffer[Int]()nT1.copyToBuffer(B)nnval T1 = Traversable(1, 2, 3, 4)nval A = Array[Int]()nT1.copyToArray(A)n
判斷
val T1 = Traversable(1, 2, 3, 4)nT1.isEmpty //whether T1 is EmptynT1.nonEmptynT1.sizenT1.hasDefiniteSize n
元素檢索
val T1 = Traversable(1, 2, 3, 4)nT1.head //output: 1nT1.headOption //Option[Int] = Some(1)nT1.last //output: 4nT1.lastOption //output: Option[Int] = Some(4)nT1.find(x => x > 2) //output: Option[Int] = Some(3)n
子集合
val T1 = Traversable(1, 2, 3, 4)nT1.tail //output: List(2, 3, 4)nT1.init //output: List(1, 2, 3)nT1 slice(0, 2) //output: List(1, 2)nT1 take 2 //output: List(1, 2)nT1 drop 3 //output: List(4)nT1.takeWhile(_ < 2) //output: List(1)nT1 dropWhile (_ < 2) //output: List(2, 3, 4)nT1 filter (_ % 2 == 0) //output: List(2, 4)nT1 filterNot (_ % 2 == 0) //output: List(1, 3)n
拆分
val T1 = Traversable(1, 2, 3, 4)nT1 splitAt 2 //output: (List(1, 2),List(3, 4))nT1 span (_ < 2) //output: (List(1),List(2, 3, 4))nT1 partition (_ % 2 == 0) //output: (List(2, 4),List(1, 3))nT1 groupBy (_ % 2 == 0) //output: Map(false -> List(1, 3), true -> List(2, 4))n
斷言
val T1 = Traversable(1, 2, 3, 4)nT1 forall (_>0) //output: true ,all elements > 0nT1 exists (_>2) //output:true , two elements > 2nT1 count (_>2) //output: 2 , two elements > 2n
摺疊
val T1 = Traversable(1, 2, 3, 4)nT1.foldLeft(3)((sum, i) => sum + i) // output: 13, from left to right , 3 + SumsnT1.foldRight(2)((sum, i) => sum + i) //output: 12, from right to left , 2 + SumsnT1 reduceLeft ((sum, i) => sum + i) // output:10, from left to right , SumsnT1 reduceRight ((sum, i) => sum + i) // output:10, from right to left , SumsnT1.sum //output:10 , SumsnT1.product //output: 24 , QuadraturenT1.min //output: 1nT1.max //output: 4n
字元串和視圖
val T1 = Traversable(1, 2, 3, 4)nval b = new StringBuilder()nT1 addString(b, "Begin[", "-", "]End") //output: "Begin[1-2-3-4]End"nT1 mkString("B[", "-", "]E") //output: "B[1-2-3-4]E"nT1.stringPrefix //output: "List"n//ViewnT1.viewnT1.view(1,3)n
Trait Iterable
自下而上的容器(collection)層次結構具有可迭代的Trait。Trait的所有方法可定義為一個抽象方法,逐個生成容器(collection)元素迭代器。Traversable Trait的foreach方法實現了迭代器的Iterable。
def foreach[U](f: Elem => U): Unit = {nval it = iteratornwhile (it.hasNext) f(it.next())n} n
Iterable有兩個方法返回迭代器:grouped和sliding。而這些迭代器返回的不是單個元素,而是原容器(collection)元素的全部子序列。這些最大的子序列作為參數傳給這些方法。grouped方法返回元素的增量分塊,sliding方法生成一個滑動元素的窗口。
val L1 = List(1, 2, 3, 4, 5, 6, 7)nval git = L1 grouped 3 //output: non-empty iteratorngit.next() //output: List(1, 2, 3)ngit.next() //output: List(4, 5, 6)ngit.next() //output: List(7)nval sit = L1 sliding (3)nsit.next() //output: List(1, 2, 3)nsit.next() //output: List(2, 3, 4)nsit.next() //output: List(3, 4, 5)n
Iterable的一些方法
//Subcollectionnval T1 = List(1, 2, 3, 4, 5)nT1 takeRight 2 //output: List(4, 5)nT1 dropRight 2 //output: List(1, 2, 3)nn//Zippers ,An iterable of pairs of corresponding elements from T1 and T2.nval T1 = List(1, 2, 3, 4, 5)nval T2 = List("one", "two", "three", "four")nT1 zip T2 //output: List((1,one), (2,two), (3,three), (4,four))nT1 zipAll (T2,0,"zero") //output: List((1,one), (2,two), (3,three), (4,four), (5,zero))nn//Comparison,A test whether T1 and T2 contain the same elements in the same ordernval T1 = List(1, 2, 3, 4, 5)nval T2 = List(1, 2, 3, 4, 5)nT1 sameElements T2 //output: truenval T3 = List(1, 2, 3, 4, 5)nval T4 = List(3, 4, 5, 1, 2)nT3 sameElements T4 //output: falsen
序列
所謂序列,指的是一類具有一定長度的可迭代訪問的對象,其中每個元素均帶有一個從0開始計數的固定索引位置。
序列的一些方法
//Indexing and Lengthnval S1 = Seq(1, 2, 3, 4, 5, 6)nval S2 = Seq(1, 2, 3, 4, 5, 6)nS1(2) //output: 3nS1 isDefinedAt 2 //output: truenS1 isDefinedAt 9 //output: falsenS1.length //output: 6nS1.lengthCompare(2) //output: 0nS1.lengthCompare(6) //output: 0nS1.lengthCompare(9) //output: -1nS1.indices //output: Range 0 until 6nn//Index Searchnval S3 = Seq("one", "two", "three", "four", "five", "six")nS3 indexOf "three" //output: 2nS3 lastIndexOf "three" //output: 2nS3 indexOfSlice Seq("two", "three") //output: 1nS3 lastIndexOfSlice Seq("two", "three") //output: 1nS3 indexWhere (_ == "two") //output: 1n//he length of the longest uninterrupted segment of elements in S3, starting with S3(i), that all satisfy the predicate (_ == "two").nS3 segmentLength(_.contains(t), 1) //output: 2 n//The length of the longest prefix of elements in S3 that all satisfy the predicate _.contains(n).nS3 prefixLength (_.contains(n)) //output: 1nn//Additionsnval T1 = Seq(2, 3, 4)n1 +: T1 //output: List(1, 2, 3, 4)nT1 :+ 1 //output: List(2, 3, 4, 1)nT1 padTo(6, 1) //output: List(2, 3, 4, 1, 1, 1)nn//Updatesnval S1 = Seq(2, 3, 4)nS1 patch(0, Seq(4, 5, 6), 3) //output: List(4, 5, 6, 4)nS1 updated(2, 6) //output: List(2, 3, 6)nval S2 = mutable.Seq(2, 3, 4)nS2(2) = 8t //output: ArrayBuffer(2, 3, 8)nn//Sortingnval S1 = Seq(2, 5, 3, 4, 9, 0, 8)nS1.sorted //output: List(0, 2, 3, 4, 5, 8, 9)nS1 sortWith ((s, t) => s.compareTo(t) > 0) //output: List(9, 8, 5, 4, 3, 2, 0)nS1 sortBy (x => x % 3) //output: List(3, 9, 0, 4, 2, 5, 8)nn//Reversalsnval S1 = Seq(1, 2, 3, 4, 5, 6)nS1.reverse //output: List(6, 5, 4, 3, 2, 1)nval iter = S1.reverseIteratorniter.next() //output: 6niter.next() //output: 5nS1 reverseMap { x => x * x } //output: List(36, 25, 16, 9, 4, 1)nn//Comparisonsnval S1 = Seq(1, 2, 3, 4, 5, 6)nS1 startsWith Seq(1, 2) //output: truenS1 endsWith Seq(5, 6) //output: truenS1 contains 3 //output: truenS1 containsSlice Seq(3, 4, 5) //output: truen//Tests whether corresponding elements of S1 and ys satisfy the binary predicate p.n(S1 corresponds Seq(2, 3, 4, 5, 6, 7)) (_ < _) //output: truenn//Multiset Operationsnval S1 = Seq(1, 2, 3, 4, 5, 6)nS1 intersect Seq(1, 2, 3, 7, 8, 9) //output: List(1, 2, 3)nS1 diff Seq(1, 2, 3, 7, 8, 9) //output: List(4, 5, 6)nS1 union Seq(1, 2, 3, 7, 8, 9) //output: List(1, 2, 3, 4, 5, 6, 1, 2, 3, 7, 8, 9)nS1 ++ Seq(1, 2, 3, 7, 8, 9) //output: List(1, 2, 3, 4, 5, 6, 1, 2, 3, 7, 8, 9)nSeq(1, 1, 1, 3, 3, 3, 2, 2, 2).distinct //List(1, 3, 2)n
Buffer是可變序列一個重要的種類。它們不僅允許更新現有的元素,而且允許元素的插入、移除和在buffer尾部高效地添加新元素。
val S1 = mutable.Buffer(1, 2, 3, 4, 5, 6)n//AdditionsnS1 += 9 //output: ArrayBuffer(1, 2, 3, 4, 5, 6, 9)nS1 +=(7, 8, 9) //output: ArrayBuffer(1, 2, 3, 4, 5, 6, 9, 7, 8, 9)nS1 ++= mutable.Buffer(10, 11) //output: fer[Int] = ArrayBuffer(1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 7, 8, 9)n0 +=: S1 //output: (0, 1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 10, 11)nmutable.Buffer(7, 8, 9) ++=: S1 //output: (7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 10, 11)nS1 insert(3, 8) //ArrayBuffer(7, 8, 9, 8, 0, 1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 10, 11)nS1 insertAll(3, mutable.Buffer(7, 8, 9)) //ArrayBuffer(7, 8, 9, 7, 8, 9, 8, 0, 1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 10, 11)nn//RemovalsnS1 -= 7 //output: ArrayBuffer(8, 9, 7, 8, 9, 8, 0, 1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 10, 11)nS1 remove 0 //output: 8nS1 remove(0, 3) //ArrayBuffer(9, 8, 0, 1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 10, 11)nS1 trimStart 1 // ArrayBuffer(8, 0, 1, 2, 3, 4, 5, 6, 9, 7, 8, 9, 10, 11)nS1 trimEnd 6 // ArrayBuffer(8, 0, 1, 2, 3, 4, 5, 6)nS1.clear() // ArrayBuffer()n//CloningnS1.clone //output: ArrayBuffer()n
Sets
Sets是不包含重複元素的可迭代對象。
不可變Set類的一些方法
val S1 = Set(1, 2, 3)nS1 contains 3 //output: truenS1(3) //output: truenS1 subsetOf Set(1, 2, 3) //output: truen//AdditionsnS1 + 4 //output: Set(1, 2, 3, 4)nS1 +(5, 6, 7) //output: Set(5, 1, 6, 2, 7, 3)nS1 ++ Set(7, 8, 9) //output: Set(1, 9, 2, 7, 3, 8)n//RemovalsnS1 - 3 //output: Set(1, 2, 3)nSet(1, 2, 3, 5, 6, 7) -(3, 5, 6, 7) //output: Set(1, 2)nSet(1, 2, 7, 3, 8, 9) -- Set(7, 8, 9) //output: Set(1, 2, 3)nS1.empty //output: Set()n//Binary Operationsnval S2 = Set(1, 2, 3, 7, 8, 9)nS2 & Set(7, 8, 9, 10) //output: Set(9, 7, 8)nS2 intersect Set(7, 8, 9, 10) //output: Set(9, 7, 8)nS2 | Set(7, 8, 9, 10) //output: Set(10, 1, 9, 2, 7, 3, 8)nS2 union Set(7, 8, 9) //output: Set(1, 9, 2, 7, 3, 8)nS2 &~ Set(7, 8, 9) //output: Set(1, 2, 3)nS2 diff Set(7, 8, 9) //output: Set(1, 2, 3)n
可變Set類更多的一些方法
val S1 = mutable.Set(1, 2, 3)n//AdditionsnS1 += 4 //output: Set(1, 2, 3, 4)nS1 +=(5, 6) //output: Set(1, 5, 2, 6, 3, 4)nS1 ++= Set(7, 8) //output: Set(1, 5, 2, 6, 3, 7, 4, 8)n//Adds element x to xs and returns true if x was not previously contained in the set, false if it was.nS1 add 10 //output: truen//RemovalsnS1 -= 1 //output: Set(5, 2, 6, 3, 10, 7, 4, 8)nS1 -=(7, 8) //output: Set(5, 2, 6, 3, 10, 4)nS1 --= Set(5, 6) //output: Set(2, 3, 10, 4)nS1 remove 4 //output: true nS1 retain (_ % 2 == 0) //Set(2, 10)nS1.clear() //Set()n//Updatenval S2 = mutable.Set(1, 2, 3)nS2(19) = (4 > 2) //Set(1, 19, 2, 3)n//CloningnS2.clone //output: Set(1, 19, 2, 3)n
映射(Map)
映射(Map)是一種可迭代的鍵值對結構(也稱映射或關聯)。
不可變Map的一些方法
val M1 = Map("one" -> 1, "two" -> 2, "three" -> 3, "four" -> 4)n//LookupsnM1 get "one" //output: Some(1)nM1("one") //output: 1nM1 getOrElse("five", 5) //output: 5nM1 contains "two" //output: truenM1 isDefinedAt "two" //output: truenn//Additions and UpdatesnM1 + ("five" -> 5) //output: Map(four -> 4, three -> 3, two -> 2, five -> 5, one -> 1)nM1 +("five" -> 5, "six" -> 6) //output: Map(four -> 4, three -> 3, two -> 2, six -> 6, five -> 5, one -> 1)nM1 ++ Map("five" -> 5, "six" -> 6) //output: Map(four -> 4, three -> 3, two -> 2, six -> 6, five -> 5, one -> 1)nM1 updated("seven", 7) //output: Map(four -> 4, three -> 3, two -> 2, seven -> 7, one -> 1)nn//RemovalsnM1 - "one" //output: Map(two -> 2, three -> 3, four -> 4)nM1 -("one", "two") //output: Map(three -> 3, four -> 4)nM1 -- Seq("one", "two") //output: Map(three -> 3, four -> 4)nn//SubcollectionnM1.keys //output: Set(one, two, three, four)nM1.keySet //output: Set(one, two, three, four)nM1.keysIterator.next() //output: onenM1.values //output: MapLike(1, 2, 3, 4)nM1.valuesIterator.next() //output: 1nn//TransformationnM1 filterKeys (_ == "one") //output: Map(one -> 1)nM1 mapValues (x => x * x) //output: Map(one -> 1, two -> 4, three -> 9, four -> 16)n
可變Map的一些方法
import scala.collection.mutablennval M1 = mutable.Map("one" -> 1, "two" -> 2, "three" -> 3)n//Additions and UpdatesnM1 += ("four" -> 4) //output: Map(one -> 1, three -> 3, four -> 4, two -> 2)nM1 +=("four" -> 4, "five" -> 5) //output: Map(one -> 1, three -> 3, four -> 4, five -> 5, two -> 2)nM1 ++= Map("six" -> 6) //output: Map(one -> 1, three -> 3, six -> 6, four -> 4, five -> 5, two -> 2)nM1 put("seven", 7) //output: NonenM1 getOrElseUpdate("eight", 8) //output: 8n//RemovalsnM1 -= "three" //output: Map(seven -> 7, one -> 1, eight -> 8, six -> 6, four -> 4, five -> 5, two -> 2)nM1 -=("six", "seven") //output: Map(one -> 1, eight -> 8, four -> 4, five -> 5, two -> 2)nM1 --= Seq("four") //output: Map(one -> 1, eight -> 8, five -> 5, two -> 2)nM1 remove "one" //output: Some(1)nM1 retain ((k, v) => k == "two" & v == 2) //output: Map(two -> 2)nM1.clear() //output: Map()n//TransformationnM1 +=("one" -> 1, "two" -> 2, "three" -> 3)nM1 transform { (k, v) => v * 2 } //output: Map(one -> 2, three -> 6, two -> 4)n//Cloning:nM1.clonen
List
列表List是一種有限的不可變序列式。提供了常數時間的訪問列表頭元素和列表尾的操作,並且提供了常數時間的構造新鏈表的操作,該操作將一個新的元素插入到列表的頭部。其他許多操作則和列表的長度成線性關係。
val L1 = List(1, 2, 3)nval L2 = 1 :: 2 :: 3 :: Niln//Same Resultn
Stream
Stream與List很相似,只不過其中的每一個元素都經過了一些簡單的計算處理。因此,stream結構可以無限長。
val str = 1 #:: 2 #:: 3 #:: Stream.emptyn//output: Stream(1, ?)n
這個stream的頭結點是1,尾是2和3。尾部並沒有列印出來,因為還沒有進行計算。stream被特別定義為惰性求值。
Vector
Vector是用來解決list不能高效的隨機訪問的一種結構。Vector結構能夠在「更高效」的固定時間內訪問到列表中的任意元素。雖然這個時間會比訪問頭結點或者訪問某數組元素所需的時間長一些,但至少這個時間也是個常量。因此,使用Vector的演算法不必僅是小心的處理數據結構的頭結點。由於可以快速修改和訪問任意位置的元素,所以對Vector結構做寫操作很方便。
val vec = Vector.empty :+ 1 :+ 2nval vec2 = Vector(1, 2, 3)n
Immutable stacks
如果您想要實現一個後入先出的序列,那您可以使用Stack。
import scala.collection.immutable.Stacknnval stack = Stack.emptynval stack2 = stack.push(1, 3, 5).push(7)nstack2.popn
Immutable Queues
Queue是一種與stack很相似的數據結構,除了與stack的後入先出不同,Queue結構的是先入先出的。
val queue = scala.collection.immutable.Queue[Int]()nval queue2 = queue.enqueue(1)nval one = queue2.dequeuen
Ranges
Range表示的是一個有序的等差整數數列。比如說,「1,2,3,」就是一個Range,「5,8,11,14,」也是。在Scala中創建一個Range類,需要用到兩個預定義的方法to和by。
val R3 = 1 to 3nval R2 = 5 to 14 by 3nfor (i <- 1 to 10) {nprint(i)n}n1 until 3 //not contains 3n
Red-Black Trees
val T1 = scala.collection.immutable.TreeSet.empty[Int]nT1 + 1 + 3 + 3n
Immutable BitSets
BitSets是由小整數構成的容器,這些小整數的值表示了一個大整數被置1的各個位。比如說,一個包含3、2和0的bit集合可以用來表示二進位數1101和十進位數13.
val bits = scala.collection.immutable.BitSet.emptynval moreBits = bits + 3 + 4 + 4n
List Maps
一個保存鍵-值映射的鏈表。
val map = scala.collection.immutable.ListMap(1->"one", 2->"two")n
未完待續
推薦閱讀:
※在 Scala 中實現泛型函數
※Data class 是好東西,Kotlin 就差一個 pattern matching 了