轉載：不允許轉載請告知，在第一時間刪除觉至。
scala 集合類庫使用率非常頻繁璧尸，也是其它語言開發(fā)者羨慕不已功能咒林。本篇講說明類庫中相同的API的執(zhí)行效率對比，作為使用時的參考依據(jù)爷光。只是理論上的特點垫竞，沒有具體指標量化。
原文傳送門 Author: heathermiller
為閱讀方便蛀序，對內(nèi)容稍作調整欢瞪。
不同的容器類型具有不同的性能特點。這通常是選擇容器類型的首要依據(jù)哼拔。以下的兩張表格引有，總結了一些關于容器類型常用操作的性能特點瓣颅。
標志位解釋
為便于理解倦逐，先對各標志位做說明：
| 術語 | 操作功能描述 |
|---|---|
| C | 指操作的時間復雜度為常數(shù) |
| eC | 指操作的時間復雜度實際上為常數(shù)，但可能依賴于諸如一個向量最大長度或是哈希鍵的分布情況等一些假設宫补。 |
| aC | 該操作的均攤運行時間為常數(shù)檬姥。某些調用的可能耗時較長，但多次調用之下粉怕，每次調用的平均耗時是常數(shù)健民。 |
| Log | 操作的耗時與容器大小的對數(shù)成正比。 |
| L | 操作是線性的贫贝，耗時與容器的大小成正比秉犹。 |
| - | 操作不被支持蛉谜。 |
序列類型的性能特點
根據(jù)需求選擇序列，會大幅提升性能崇堵。具體的性能評估如下：
不可變序列性能特點
| 不可變序列 | head | tail | apply | update | prepend | append | insert |
|---|---|---|---|---|---|---|---|
| List | C | C | L | L | C | L | - |
| Stream | C | C | L | L | C | L | - |
| Vector | eC | eC | eC | eC | eC | eC | - |
| Stack | C | C | L | L | C | L | L |
| Queue | aC | aC | L | L | C | C | - |
| Range | C | C | C | - | - | - | - |
| String | C | L | C | L | L | L | - |
可變序列性能特點
| 可變序列 | head | tail | apply | update | prepend | append | insert |
|---|---|---|---|---|---|---|---|
| ArrayBuffer | C | L | C | C | L | aC | L |
| ListBuffer | C | L | L | L | C | C | L |
| StringBuilder | C | L | C | C | L | aC | L |
| MutableList | C | L | L | L | C | C | L |
| Queue | C | L | L | L | C | C | L |
| ArraySeq | C | L | C | C | - | - | - |
| Stack | C | L | L | L | C | L | L |
| ArrayStack | C | L | C | C | aC | L | L |
| Array | C | L | C | C | - | - | - |
序列中操作的功能描述
- head: 選擇序列的第一個元素
- tail : 生成一個包含除第一個元素以外所有其他元素的新的列表型诚。
- apply : 索引
- update: 功能性更新不可變序列，同步更新可變序列鸳劳。
- prepend: 添加一個元素到序列頭狰贯。對于不可變序列，操作會生成個新的序列赏廓。對于可變序列涵紊，操作會修改原有的序列。
- append: 在序列尾部插入一個元素幔摸。對于不可變序列摸柄，這將產(chǎn)生一個新的序列。對于可變序列抚太，這將修改原有的序列塘幅。
- insert : 在序列的任意位置上插入一個元素。只有可變序列支持該操作尿贫。
集合和映射類型的性能特點
不可變序列性能
| 不可變序列 | lookup | add | remove | min |
|---|---|---|---|---|
| HashSet/HashMap | eC | eC | eC | L |
| TreeSet/TreeMap | Log | Log | Log | Log |
| BitSet | C | L | L | eC1 |
| ListMap | L | L | L | L |
可變序列性能
| 可變序列 | lookup | add | remove | min |
|---|---|---|---|---|
| HashSet/HashMap | eC | eC | eC | L |
| WeakHashMap | eC | eC | eC | L |
| BitSet | C | aC | C | eC1 |
| TreeSet | Log | Log | Log | Log |
可變和不可變集與映射功能描述
- lookup 測試一個元素是否被包含在集合中电媳，或者找出一個鍵對應的值
- add 添加一個新的元素到一個集合中或者添加一個鍵值對到一個映射中
- remove 移除一個集合中的一個元素或者移除一個映射中一個鍵。
- min 集合中的最小元素庆亡，或者映射中的最小鍵匾乓。
