Scalaのコレクションたち〜imutable.Map編〜

# はじめに
Scalaのコレクションには色々な実装が存在します。
ここでは『イミュータブル』な`Map`にフォーカスをあてて、各マップの特徴をまとめていきたいと思います。以降、ミュータブル/イミュータブルの明記がない場合はイミュータブルコレクションのことを指します。
（ミュータブル編は必要性に駆られたら調べますが、多分やらない・・・）

- ここで書くこと
  - 各コレクション実装の特徴

- ここで書かないこと
  - 『Mapとは？』のようなコレクション概念
  - ミュータブルコレクションに関すること

内容は[公式ドキュメント](https://docs.scala-lang.org/ja/overviews/collections/introduction.html)に沿ってまとめています。図も公式ドキュメントから拝借したものです。

## 動作環境
- OS
    - MacOS Catalina
- CPU
    - Corei9(2.4GHz 8コア)
- メモリー
    - 64GB 
- Scalaバージョン
    - 2.13.2

# Scalaのマップ
以下の図は公式ドキュメントに使用されているものです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/64360/2f401218-67ee-8360-ac82-8b8521b2a556.png)
資料：https://docs.scala-lang.org/ja/overviews/collections/overview.html
上記図の`Map`配下が今回の対象です。ただ、上記の図は少し古いようでScala2.13で追加されたコレクションが反映されていません。それらについても拾える範囲で拾っていきます。

# Mapの特徴
Mapには５種類の実装が用意されているのですが、違いについてはコレクションの説明ドキュメントには記載されていません。

## HashMap
`HashMap`はキーのハッシュ値を求めてそれを内部的なキーとしてデータを管理するデータ構造です。`Map`を使うとなると、基本的にはこれを使うことになると思います。
これ以外の`Map`の実装は何らかの「順番」をキープしながらデータを管理する構造となっています。

```scala:HashMapの動作確認
// Mapにデータを格納していく
scala> res7.updated("qwer", 1)
res13: scala.collection.immutable.HashMap[String,Int] = HashMap(qwer -> 1)

// このデータはたまたま登録順に格納された
scala> res13.updated("asdf", 100)
res14: scala.collection.immutable.HashMap[String,Int] = HashMap(qwer -> 1, asdf -> 100)

// このデータは２番目に格納されているように見える
scala> res14.updated("uiop", 10)
res15: scala.collection.immutable.HashMap[String,Int] = HashMap(qwer -> 1, uiop -> 10, asdf -> 100)

// 同上
scala> res15.updated("fghj", 10)
res16: scala.collection.immutable.HashMap[String,Int] = HashMap(qwer -> 1, fghj -> 10, uiop -> 10, asdf -> 100)

// 出力しても登録順にはデータは読み取られない
scala> res16.foreach(println(_))
(qwer,1)
(fghj,10)
(uiop,10)
(asdf,100)

// 別の取得方法を試してみてもやはり登録順ではない
scala> res16.tail.head
res20: (String, Int) = (fghj,10)
```

## ListMap
内部的にデータの登録順を保持していてくれるデータ構造です。
指定されたキーに一致する値を取得するためにデータ内部を線形に走査してデータアクセスすることとなります。最後に登録したデータが最初にヒットするように格納されているので、最初に格納したキーにヒットするのは一番最後です。
データを`Map`で管理しつつ、アクセス回数に偏りがある(かつどのキーへのアクセスが多いかを把握できている)場合で使用すると有効です。

`ListMap`のScaladocには以下のようにあります。
> this collection suitable only for a small number of elements.
(このコレクションは少数の要素にしか適していません。)

後半で性能比較を行っていますが、`ListMap`で大量データを扱おうとするとめちゃくちゃ遅いです。

```scala:ListMapの動作確認
// HashMapの時と同じ順番で同じ内容を登録していく
scala> res26.updated("qwer", 1)
res27: scala.collection.immutable.ListMap[String,Int] = ListMap(qwer -> 1)

scala> res27.updated("asdf", 100)
res28: scala.collection.immutable.ListMap[String,Int] = ListMap(qwer -> 1, asdf -> 100)

scala> res28.updated("uiop", 10)
res29: scala.collection.immutable.ListMap[String,Int] = ListMap(qwer -> 1, asdf -> 100, uiop -> 10)

scala> res29.updated("fghj", 10)
res30: scala.collection.immutable.ListMap[String,Int] = ListMap(qwer -> 1, asdf -> 100, uiop -> 10, fghj -> 10)

// 登録した順番がキープされている
scala> res30.foreach(println(_))
(qwer,1)
(asdf,100)
(uiop,10)
(fghj,10)

// データを更新
scala> res30.updated("asdf", 500)
res32: scala.collection.immutable.ListMap[String,Int] = ListMap(qwer -> 1, asdf -> 500, uiop -> 10, fghj -> 10)

// キーが同一であれば値が書き換わっても順番はキープされる
scala> res32.foreach(println(_))
(qwer,1)
(asdf,500)
(uiop,10)
(fghj,10)
```

## SortedMap
格納されているデータが自動的にソートされるデータ構造です。

### TreeMap
赤黒木というデータ構造で`Map`を実装したものになります。赤黒木を[Wikipedia](https://ja.wikipedia.org/wiki/%E8%B5%A4%E9%BB%92%E6%9C%A8#:~:text=%E8%B5%A4%E9%BB%92%E6%9C%A8%EF%BC%88%E3%81%82%E3%81%8B%E3%81%8F%E3%82%8D%E3%81%8E,%E3%83%BB%E3%83%96%E3%83%A9%E3%83%83%E3%82%AF%E3%83%BB%E3%83%84%E3%83%AA%E3%83%BC%E3%81%A8%E3%82%82%E3%81%84%E3%81%86%E3%80%82)で調べてみると以下のように説明されています。

> 赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log n)（nはツリーの要素数）と短く、複雑ではあるが実用的なデータ構造として知られている。

なるほど？？？
よくわからんのでScaladocを見てみます。

> This class is optimal when range queries will be performed, or when traversal in order of an ordering is desired.
If you only need key lookups, and don't care in which order key-values are traversed in, consider using * [[scala.collection.immutable.HashMap]], which will generally have better performance. If you need insertion order, consider a * [[scala.collection.immutable.SeqMap]], which does not need to have an ordering supplied.
(このクラスは、範囲の問い合わせが実行される場合や、順序を指定してトラバーサルしたい場合に最適です。
キー検索だけが必要で、キー値がどの順番で走査されるかを気にしない場合は、[[scala.collection.immutable.HashMap]]の使用を検討してください。挿入順が必要な場合は、[[scala.collection.immutable.SeqMap]]を検討してください。)

`SeqMap`はScala2.13で追加されたコレクションのようです。[Scala2.13のRelease Note](https://github.com/scala/scala/releases/tag/v2.13.0)に「New abstract collection type SeqMap」とあります。`SeqMap`は後で触れるとして、`TreeMap`の特徴を`HashMap`や`ListMap`の時と同じ様に確認したところ、キーが自動的にソートされていることがわかります。

```scala
scala> res4.updated("qwer", 1)
res5: scala.collection.immutable.TreeMap[String,Int] = TreeMap(qwer -> 1)

scala> res5.updated("asdf", 100)
res6: scala.collection.immutable.TreeMap[String,Int] = TreeMap(asdf -> 100, qwer -> 1)

scala> res6.updated("uiop", 10)
res7: scala.collection.immutable.TreeMap[String,Int] = TreeMap(asdf -> 100, qwer -> 1, uiop -> 10)

scala> res7.updated("fghj", 10)
res8: scala.collection.immutable.TreeMap[String,Int] = TreeMap(asdf -> 100, fghj -> 10, qwer -> 1, uiop -> 10)

// 自動的にキーがソートされている
scala> res8.foreach(println(_))
(asdf,100)
(fghj,10)
(qwer,1)
(uiop,10)
```

## SeqMap
`SeqMap`は`ListMap`等の順序を持つ`Map`のための汎用トレイトです。`ListMap`の実装を見てみると、以下のように`SeqMap`を実装していることがわかります。

```scala:ListMap
sealed class ListMap[K, +V]
  extends AbstractMap[K, V]
    with SeqMap[K, V]
    with ...
```
具象クラスではないので使い方等は省略します。
ところで、先ほどの[Release Note](https://github.com/scala/scala/releases/tag/v2.13.0)の「New abstract collection type SeqMap」の項目を見てみると以下の１文があります。

> Implementations: VectorMap (#6854) and TreeSeqMap (#7146) (in addition to the already existing ListMap).

どうやら`VectorMap`と`TreeSeqMap`という`Map`がScala2.13で追加されているようです。

## VectorMap
基本的な動作は`ListMap`と同じのようですが、内部的な挙動が異なるようです。Scaladocを見てみます。

> Unlike `ListMap`, `VectorMap` has amortized effectively constant lookup at the expense of using extra memory and generally lower performance for other operations

`ListMap`は検索対象のキーが挿入された順番によってパフォーマンスが変動するデータ構造でしたが、`VectorMap`ではデータの並び順をキープしつつもキー検索のパフォーマンスを一定に保つようになっているようです。ただし、実現のためにキー検索以外の操作とメモリー効率を犠牲にしているようです。

## TreeSeqMap
こちらも順序を意識した`Map`を扱うための実装です。Scaladocから見て取れる特徴は以下のとおりです。

- ソート順に「挿入順」「変更順」を指定することができる
- 指定した順序で`Map`をソートする

実際に動かしてみます。
ソート順も指定できるようですが、デフォルトのまま試してみます。

```scala:
scala> res4.updated("qwer", 1)
res5: scala.collection.immutable.TreeSeqMap[String,Int] = TreeSeqMap(qwer -> 1)

scala> res5.updated("asdf", 100)
res6: scala.collection.immutable.TreeSeqMap[String,Int] = TreeSeqMap(qwer -> 1, asdf -> 100)

scala> res6.updated("uiop", 10)
res7: scala.collection.immutable.TreeSeqMap[String,Int] = TreeSeqMap(qwer -> 1, asdf -> 100, uiop -> 10)

scala> res7.updated("fghj", 10)
res8: scala.collection.immutable.TreeSeqMap[String,Int] = TreeSeqMap(qwer -> 1, asdf -> 100, uiop -> 10, fghj -> 10)

scala> res8.foreach(println(_))
(qwer,1)
(asdf,100)
(uiop,10)
(fghj,10)
```

`ListMap`と同様の並び順で格納されているようです。

# Mapの計測
ここまで`Map`の特徴を見てきましたが、一般的な用途では`HashMap`を使うこととなると思います。
その他のコレクションは特化した機能があると同時におそらく性能を犠牲にしているのでしょう。確認してみます。
性能比較をするにあたって同一処理を100回実施した平均時間を比較します。確認に使用したコードは[GitHub](https://github.com/louvre2489/CollectionPerformance)にアップしています。

## HashMap、ListMap、TreeMap
### データ追加
```scala:データ追加用処理
// 以下の処理をHashMap、ListMap、TreeMapに対して実施する
// sizeで指定したデータ数のMapを作成する
def addHashProc(map: Map[Int, Int])(size: Int): Map[Int, Int] = {
  var m = map
  for (i <- 1 to size) {
    m = m.updated(i, randomInt(1000))
  }
  m
}
```

計測結果は以下のとおりです。

- 10,000件は試行回数100回の平均時間
- 100,000件は試行回数10回の平均時間

| 件数 | HashMap | ListMap | TreeMap|
|----:|----:|----:|----:|
| 10,000件|2 ミリ秒/件 |143 ミリ秒/件 | 2 ミリ秒/件|
|100,000件|19 ミリ秒/件|15,498 ミリ秒/件|23 ミリ秒/件|

`ListMap`が圧倒的に遅いです。今回の計測を行うにあたって、`ListMap`の性能が悪すぎて待ってられないので、100,000件の計測については10回の計測の平均時間を測っています。
データを作るだけであれば、`HashMap`と`TreeMap`はそれほど性能優位はなさそうです。

### キーアクセス
最初に格納したキー、最後に格納したキー、ちょうど中間のタイミングで格納したキーを指定してデータを取る際のスピードを確認します。

```scala:キーアクセス用処理
// 以下の処理をHashMap、ListMap、TreeMapに対して実施する
// keyで指定したデータにアクセスする
def keyAccess(map: Map[Int, Int])(key: Int): Int = {
  var sum = 0
  for (i <- 1 until map.size) {
    sum = sum + map(key)
  }
  sum
}
```

計測結果は以下のとおりです。

- いずれも試行回数100回の平均時間
- 最初に登録した要素のキーを指定してアクセス

| 件数 | HashMap | ListMap | TreeMap|
|----------------------:|------------:|----:|----:|
| 10,000件 |0 ミリ秒/件 |270 ミリ秒/件 | 0 ミリ秒/件|
| 100,000件 |2 ミリ秒/件 | - | 2 ミリ秒/件|
| 1,000,000件 |17 ミリ秒/件 | - | 34 ミリ秒/件|

- 中間に登録した要素のキーを指定してアクセス

| 件数 | HashMap | ListMap | TreeMap|
|----------------------:|------------:|----:|----:|
| 10,000件 |0 ミリ秒/件 |114 ミリ秒/件 | 0 ミリ秒/件|
| 100,000件 |2 ミリ秒/件 | - | 3 ミリ秒/件|
| 1,000,000件 |21 ミリ秒/件 | - | 30 ミリ秒/件|

- 最後に登録した要素のキーを指定してアクセス

| 件数 | HashMap | ListMap | TreeMap|
|----------------------:|------------:|----:|----:|
| 10,000件 |0 ミリ秒/件 |0 ミリ秒/件 | 0 ミリ秒/件|
| 100,000件 |2 ミリ秒/件 | - | 5 ミリ秒/件|
| 1,000,000件 |18 ミリ秒/件 | - | 66 ミリ秒/件|

`ListMap`は『どのタイミングで追加したキーにアクセスするか』によって顕著な性能差が見られます。その他のMapは件数が少ないうちは差が見られません。
上述のデータ追加時にも明らかになっていたとおり、`ListMap`用の大量データを作成するのにめちゃくちゃ時間を要するので途中で退場してもらっています。
件数が多くなるにつれて`HashMap`の方が性能的に優位であることがわかりました。しかし、`TreeMap`も十分に速いですね。

### 全走査
`foreach`でブン回します。

```scala:シーケンシャルアクセス用処理
// 以下の処理をHashMap、ListMap、TreeMapに対して実施する
def sequentialAccess(map: Map[Int, Int]): Int = {
  var sum = 0
  map.foreach{
    elm =>
      sum = sum + elm._2
  }
  sum
}
```

計測結果は以下のとおりです。

- 試行回数100回の平均時間
  
| 件数 | HashMap | ListMap | TreeMap|
|----------------------:|------------:|----:|----:|
| 100,000件 |1 ミリ秒/件 | 2 ミリ秒/件 | 0 ミリ秒/件|
| 500,000件 |4 ミリ秒/件 | 10 ミリ秒/件 | 3 ミリ秒/件|
| 1,000,000件 |13 ミリ秒/件 | - | 7 ミリ秒/件|
| 10,000,000件 |103 ミリ秒/件 | - | 148 ミリ秒/件|


やはり`ListMap`が目立って遅いです。ここでも`ListMap`は途中で退場してもらっています。
1,000,000件では`TreeMap`、10,000,000件では`TreeMap`の方が速いという結果になりました。100,000件、500,000件の時も`TreeMap`の方が速かったので、『一定件数までは`TreeMap`の方が速いけど、それ以上は`HashMap`の方が速い』と言えそうです。
（100,000,000件も試そうとしましたが、OutOfMemorryErrorが発生したので断念しました。刻むのも面倒だったので...）

## ListMap、VectorMap、TreeSeqMap
`VectorMap`は`ListMap`を性能向上版とのことなので性能差を比較してみます。
また、ソート順を指定しない`TreeSeqMap`は`ListMap`と同じ順番でデータが格納されていました。合わせて性能比較してみます。

### データ追加・キーアクセス・全走査

- 試行回数100回の平均時間
- データ追加
  
| 件数  | ListMap | VectorMap| TreeSeqMap |
|----------:|------------:|----:|----:|
| 100,000件|18,910 ミリ秒/件 | 40 ミリ秒/件 | 41 ミリ秒/件 |
| 1,000,000件| - | 546 ミリ秒/件 | 570 ミリ秒/件 |

- いずれも試行回数100回の平均時間
- 最初に登録した要素のキーを指定してアクセス

| 件数 | ListMap | VectorMap| TreeSeqMap |
|----------:|------------:|----:|----:|
| 100,000件 |30,827 ミリ秒/件 | 2 ミリ秒/件| 1 ミリ秒/件 |
| 1,000,000件| - | 19 ミリ秒/件 | 19 ミリ秒/件 |

- 中間に登録した要素のキーを指定してアクセス

| 件数 | ListMap | VectorMap| TreeSeqMap |
|----------:|------------:|----:|----:|
| 100,000件 |13,591 ミリ秒/件  | 2 ミリ秒/件| 2 ミリ秒/件 |
| 1,000,000件| - | 20 ミリ秒/件 | 19 ミリ秒/件 |

- 最後に登録した要素のキーを指定してアクセス

| 件数 | ListMap | VectorMap| TreeSeqMap |
|----------:|------------:|----:|----:|
| 100,000件 |1 ミリ秒/件 | 2 ミリ秒/件|  2 ミリ秒/件|
| 1,000,000件| - | 19 ミリ秒/件 | 19 ミリ秒/件 |

- シーケンシャルアクセス

| 件数 | ListMap | VectorMap| TreeSeqMap |
|----------:|------------:|----:|----:|
| 100,000件 |1 ミリ秒/件 | 6 ミリ秒/件|6 ミリ秒/件 |
| 1,000,000件| - | 143 ミリ秒/件 | 144 ミリ秒/件 |

`VectorMap`も`TreeSeqMap`も、`ListMap`とは比にならないくらい速いです。この節のテーマは`ListMap`との比較なのですが、例によって`ListMap`は遅いので、`VectorMap`も`TreeSeqMap`について1,000,000件の性能計測も行っています。
シーケンシャルアクセスに関しては`ListMap`の方が速いという結果が出ましたが、その他のアクセスについては`VectorMap`、`TreeSeqMap`が優位という結果になりました(ただし、最後に登録した要素へのキーアクセスは`ListMap`優位です)。`VectorMap`と`TreeSeqMap`については性能差が無いように見えます。


# 結論
ここまでの確認結果に則って「どのような時にどのようなコレクションを使用すべきか」を以下に記しています。

## 迷ったら
`HashMap`を使えば良いです。データ追加もデータ取得も爆速で実行してくれます。

## キーの登録順をキープさせたい！
`VectorMap`か`ListMap`を使用することとなります。
特に`ListMap`は件数が多くなってくると登録すら非常に遅くなってくるので、件数が少ない場合にのみ有効な選択です。`VectorMap`は`ListMap`の性能問題を解決してくれますが、消費メモリーを犠牲にしているとのことなので『件数が多い場合は`VectorMap`、件数が少ない場合は`ListMap`』という判断が有効かもしれません。
あとは、`TreeSeqMap`も登録順をキープすることができるようなので、こちらも選択肢になるかもしれません。

## キーの並び順をソートさせたい！
`TreeMap`か`TreeSeqMap`を使用することとなります。
`TreeSeqMap`の方が少し複雑なことができますが、そもそも`Map`のキーをソートさせたい時ってどういう時なんでしょうね？そういうシチュエーションに出会ったことがありません...