Scala Data Structure-有解無憂

Arrays

Array 固定長度；ArrayBuffer 可變長度
- arr.toBuffer, buf.toArray
初始化是不要使用 new
使用 () 訪問元素
使用 for (elem <- arr) 遍歷元素；倒序 arr.reverse
使用 for (elem <- arr if ...) ... yield ... 轉換為新的陣列
- 等價于 arr.filter(...).map(...) 或者更簡潔 arr filter { ... } map {...}
與 Java 的陣列通用，如果是 ArrayBuffer，可配合 scala.collection.JavaConversions 使用
在做任何操作前都會轉換為 ArrayOps 物件
構建多維陣列
- val matrix = Array.ofDim[Double](3, 4) // 3 行 4 列

Maps & Tuples

創建、查詢、遍歷 Map 的語法便捷
- val scores = Map("a" -> 100, "b" -> 90, "c" -> 95) 創建的默認為 immutable 的 hash map
- 可變的 Map 需要顯式指定 scala.collection.mutable.Map
- 創建空的 Map 需指定型別 new scala.collection.mutable.HashMap[String, Int]
- Map 是鍵值對的集合，鍵值對型別可不相同
  - "a" -> 100 等價于 ("a", 100)；創建的另一種寫法 Map(("a", 100), ("b", 90), ("c", 95))
- 訪問
  - scores("a") //回傳 Option
  - scores("d").getOrElse(0) // 回傳實際值
- mutable 更新
  - 更新值 scores("a") = 80
  - 增加元素 scores += ("d" -> 70, "e" -> 50)
  - 洗掉元素 scores -= "a"
- immutable 不可更新，修改時會產生新的 Map，但公共部分的元素資料是共享的
  - 添加元素會產生新的 Map，scores + ("d" -> 70, "e" -> 50)
  - 洗掉元素產生新的 Map scores - "a"
- 遍歷 for((k,v) <- map) ...
- 排序 Map
  - 按照 key 排序存放 scala.collection.immutable.SortedMap("d" -> 1, "b" -> 2, "c" -> 3) // Map(b -> 2, c -> 3, d -> 1)
  - 按照插入順序排放 scala.collection.mutable.LinkedHashMap("d" -> 1, "b" -> 2, "c" -> 3) // Map(d -> 1, b -> 2, c -> 3)
區分 mutable 和 immutable
默認 hash map，也可使用 tree map
與 Java 中的 Map 轉換方便 scala.collection.JavaConverters
- 在很多時候需要使用 Java 的介面完成任務，但是處理結果時可轉換為 Scala 的資料介面來處理更方便，如檔案操作等
Tuples 在聚合操作時很有用
- Map 中的鍵值對就是最簡單的元組形式 (k, v)
- 型別不必一致 val a = (1, 3.14, "hello")
- 下標訪問 a._1 // 1
- 模式匹配訪問 val (first, second, _) = a
- 用于回傳多個值
Zipping
- 元組可用于系結多個值同時處理
- zip 方法

Collections

集合性能對比
多少集合通過 scala.collection.JavaConverters 可與 Java 集合互相轉換
集合區分 generic(scala.collection)、mutable(scala.collection.mutable) 和 immutable(scala.collection.immutable)
- 如果未明確匯入包或使用包路徑，默認使用 immutable
集合 trait 或 class 的伴生物件中，都有 apply 方法，可直接構造集合實體，如 Array(1,2,3)
Traversable 集合層級的頂部，只有 foreach 方法是抽象的，其他方法都可直接繼承使用
Iterable ，只有 iterator 方法是抽象的，其他方法都可直接繼承使用
- 與 Traversable 的區別在于，iterator 帶狀態（可選擇獲取下一個元素的時間，在獲取下一個元素之前會一直跟蹤集合中的位置）
- Iterable 中的 foreach 通過 iterator 實作
Seq 有序序列，包含 length，有固定下標
- IndexedSeq 快速隨機訪問，通過 Vector 實作
- LinearSeq 高效的 head/ tail 操作，通過 ListBuffer 實作
Set 無序集合、無重復元素
- 默認實作為 HashSet，即元素其實是按照對應的哈希值排序的
  - 在 HashSet 中查找元素遠快于在 Array 或 List 中查找
Map 鍵值對集合，scala.Predef 提供了隱式轉換，可直接使用 key -> value 表示 (key, value)
- SortedMap 按 key 排序

Immutable

file

Vector 帶下標的集合，支持快速的隨機訪問，相當于不可變的 ArrayBuffer
- 通過高分叉因子的樹實作，每個節點包含 32 個元素或子節點
- 在快速隨機選擇和快速隨機更新之間保持平衡
- 彌補 List 在隨機訪問上的缺陷
Range 有序的整型集合，步長一致
- 1 to 10 by 3 即生成 1 到 10 的序列，步長為 3
- util 不包含上邊界，to 包含上邊界
- 不存盤實際值，只保存 start, end, step 三個值
List 有限的不可變序列
- 為空 Nil，或包含兩部分 head 元素和 tail (子 List)
- :: 根據給定 head 和 tail 構建新的 List
  - 右結合性，即從右側開始呼叫 1 :: 2 :: Nil 等價于 1 :: (2 :: Nil) // 結果 `List(1,2)
- 根據 head, tail 的特性，可很容易進行遞回操作
```
def multi(l: List[Int]): Int = l match {
  case Nil    => 1
  case h :: t => h * multi(t)
}
```
- 復雜度
  - 獲取 head, tail 只需要常數時間 O(1)
  - 在頭部添加元素也只需要常數時間 O(1)；可使用 mutable.ListBuffer 可在頭部或尾部進行增/刪元素操作
  - 其他操作需要線性時間 O(N)
SortedSet 有序集合，按順序訪問元素，默認實作為紅黑樹
immutable.BitSet 非負整數集合，底層使用 Long 陣列存盤
- 用較小的整型表示較大的整型，如 3,2,0 二進制表示為 1101，即十進制的 13
ListMap
- 通過鍵值對的 LinkedList 來表示 Map
- 多數情況下比標準的 Map 要慢，因此使用較少
  - 只有在獲取第一個元素較頻繁時才比較有優勢 (即 List 的 head)
Stream 與 List 類似，但其元素都是延遲計算的
- 長度無限制
- 只有請求的元素會被計算
  - 可通過 force 來強制進行計算所有元素
- 通過 #:: 構造，1 #:: 2 #:: 3 #:: Stream.empty 結果為 Stream(1, ?) 此處只列印了 head 1，而 tail 未列印，因為還未計算 tail
immutable.Stack LIFO 序列
- push 入堆疊 , pop 出堆疊, top 查看堆疊頂元素
- 很少使用，因為其操作都可以被 List 包括(push = ::, pop = tail, top = head)
immutable.Queue FIFO 序列
- enqueue 入列，可使用集合做引數，一次性入列多個元素
- dequeue 出列，結果包含兩部分 (element, rest)

Mutable

ArrayBuffer
- 包含一個 array 和 size (繼承自 ResizableArray)
- 多數操作速度與 Array 相同
- 可向尾部添加元素 (恒定分攤時間，對于更大的集合也可以高效的添加元素)
ListBuffer，類似于 ArrayBuffer 但是基于鏈表實作
LinkedList
- 元素包含指向下一元素的鏈接
- 空鏈表元素自己指向自己
LinkedHashSet 除了 Hash 的特點外，會記錄元素插入的順序
mutable.Queue
- += 添加單個元素；++= 添加多個元素
- dequeue 移除并回傳隊首元素
mutable.Stack 與不可變版本相同，除了會對原資料發生修改
mutable.BitSet 直接修改原資料，更新操作比 immutable.BitSet 更高效

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/50631.html

標籤：大數據

上一篇：淺談HDFS（三）之DataNote

下一篇：idea中flink啟動報錯org.apache.flink.api.common.ExecutionConfig$GlobalJobParameters