はじめに
Scalaのお話です。
Mapで情報を管理しつつ、要素の挿入順序も保持したいという欲求にかられました。
２年ほど前に一度使ったな、確か要素の挿入順序を保持してくれたっけな、という曖昧な記憶のもとに可変ListMap（mutable.ListMap）を使いました。
A simple mutable map backed by a list.
としか書かれてませんが、「ああ、内部実装はListなのね。じゃあ入れた順に並ぶんだね」と安直に考えてしまいました。
それが間違いの始まりでした。
可変ListMapに要素を入れてみる
現時点の最新のScala 2.11.6でやってみます。
まず、バージョン確認から。
|
1 2 |
scala> scala.util.Properties.versionString res0: String = version 2.11.6 |
最新になっています。
インスタンスを用意して、要素を２つほど入れます。要素の追加には「+=」を使います。
|
1 2 3 4 5 6 7 8 |
scala> val listMap = scala.collection.mutable.ListMap[String, String]() listMap: scala.collection.mutable.ListMap[String,String] = Map() scala> listMap += ("First" -> "") res1: listMap.type = Map(First -> "") scala> listMap += ("Second" -> "") res2: listMap.type = Map(Second -> "", First -> "") |
挿入順序の逆順になっています。さらに要素を入れていきます。
|
1 2 |
scala> listMap += ("Third" -> "") res3: listMap.type = Map(Third -> "", First -> "", Second -> "") |
あれ？順序が乱れていますね。もうひとつ要素を入れてみます。
|
1 2 |
scala> listMap += ("Fourth" -> "") res4: listMap.type = Map(Fourth -> "", Second -> "", First -> "", Third -> "") |
？？？
どういうことでしょう。
ソースを見てみよう
mutable.ListMapのソースを読んでみます。必要な箇所のみ抜粋します。
|
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
private var elems: List[(A, B)] = List() private var siz: Int = 0 def get(key: A): Option[B] = elems find (_._1 == key) map (_._2) def iterator: Iterator[(A, B)] = elems.iterator @deprecatedOverriding("No sensible way to override += as private remove is used in multiple places internally.", "2.11.0") def += (kv: (A, B)) = { elems = remove(kv._1, elems, List()); elems = kv :: elems; siz += 1; this } @deprecatedOverriding("No sensible way to override -= as private remove is used in multiple places internally.", "2.11.0") def -= (key: A) = { elems = remove(key, elems, List()); this } @tailrec private def remove(key: A, elems: List[(A, B)], acc: List[(A, B)]): List[(A, B)] = { if (elems.isEmpty) acc else if (elems.head._1 == key) { siz -= 1; acc ::: elems.tail } else remove(key, elems.tail, elems.head :: acc) } |
+= 関数は54行目です。
まず、要素を保持するmutable.Listであるelems（47行目）からキー（kv._1）に該当する要素を削除（remove）します。
次に、elemsの先頭にキーと値（kv）を追加します。
ここは問題なさそうです。最後に追加した要素が先頭にくるんですね。
では、次に remove 関数（60行目）を見てみます。
accumulator を使って処理結果を引き継いでいくというよくある実装です。
61行目：elemsが空の場合（つまり最後まで処理した場合）は、accumulator（それまでの処理結果）を返す。
62行目：elemsの先頭がキーに一致する場合、accumulator（それまでの処理結果）の後ろに、elemsの先頭を除いたものを追加して返す。
63行目：それ以外（elemsの先頭がキーに一致しない）場合、elemsの先頭を除いたものからキーを remove する。それまでの処理結果の前にelemsの先頭を追加したものを、ここまでの処理結果とする。
あ、63行目ですね。ここで順序が逆になっています。
「それまでの処理結果の前にelemsの先頭を追加したものを、ここまでの処理結果とする」ではなく、
「それまでの処理結果の後にelemsの先頭を追加したものを、ここまでの処理結果とする」であれば、挿入順序は保持されます。
つまり、
|
59 60 61 62 63 64 |
@tailrec private def remove(key: A, elems: List[(A, B)], acc: List[(A, B)]): List[(A, B)] = { if (elems.isEmpty) acc else if (elems.head._1 == key) { siz -= 1; acc ::: elems.tail } else remove(key, elems.tail, acc :+ elems.head) } |
とすれば挿入順序は保持されるのですが、Listの最後尾に要素を追加するのはコストが高いので、このような実装になっているのでしょう。
「挿入順序は保持される」と仕様に書かれているわけではないですし．．．。
古いバージョンのScalaで試してみる
でもやっぱり気になります。昔は確か挿入順序が保持されていたような．．．。
どこかで実装が変更になったんでしょうか。githubの履歴を辿ってみると、ありました。
SI-6853 changed private method remove to be tail recursive.
Operations += and -= on mutable.ListMap rely on the private method remove to perform. This methods was implemented using recursion, but it was not tail recursive. When the ListMap got too big the += caused a StackOverflowError.
「removeは再帰関数だけど末尾再帰ではないので、大きなものを処理するとStackOverflowErrorになる」ので修正したとのことです。
Scala 2.10.1 以降で変更になっているようですので、その一つ前のバージョンのScala 2.9.3で試してみます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
scala> scala.util.Properties.versionString res0: java.lang.String = version 2.9.3 scala> val listMap = scala.collection.mutable.ListMap[String, String]() listMap: scala.collection.mutable.ListMap[String,String] = Map() scala> listMap += ("First" -> "") res1: listMap.type = Map(First -> "") scala> listMap += ("Second" -> "") res2: listMap.type = Map(Second -> "", First -> "") scala> listMap += ("Third" -> "") res3: listMap.type = Map(Third -> "", Second -> "", First -> "") scala> listMap += ("Fourth" -> "") res4: listMap.type = Map(Fourth -> "", Third -> "", Second -> "", First -> "") |
こちらだと、逆順ですが挿入順序は保持されます。
ソースはここにあります。
|
42 43 44 45 46 47 48 49 50 51 52 53 |
private var elems: List[(A, B)] = List() private var siz: Int = 0 def get(key: A): Option[B] = elems find (_._1 == key) map (_._2) def iterator: Iterator[(A, B)] = elems.iterator def += (kv: (A, B)) = { elems = remove(kv._1, elems); elems = kv :: elems; siz += 1; this } def -= (key: A) = { elems = remove(key, elems); this } private def remove(key: A, elems: List[(A, B)]): List[(A, B)] = if (elems.isEmpty) elems else if (elems.head._1 == key) { siz -= 1; elems.tail } else elems.head :: remove(key, elems.tail) |
+= 関数（47行目）は変わってないですが、remove 関数（50行目）の実装が変わっています。
確かにこの実装だと挿入順序が保持されますね。
おわりに
ライブラリの仕様を確認せずに思い込みで使っていたら、ライブラリのバージョンが上がったら挙動が変わっていて慌てました、というありがちなお話です。
mutable.ListMapは実装がシンプルだし、動作確認しても以前は大丈夫だったので、順序保証されると思い込んでしまいましたが、仕様にはそんなこと一言も書いてありません。
書いてあるのは、ただ「実装がListである」だけ。
仕様を読むときに「こうだったらいいな」という希望が「こうに違いない」という予断に変わり、誤った理解をしてしまったんだと反省します。
ライブラリの仕様を読むときは「ほんとにそう？」と疑ってかかりましょう。
おまけ
挿入順序を保持したい場合はmutable.LinkedHashMapを使うのがいいですね。
APIリファレンスには、
This class implements mutable maps using a hashtable. The iterator and all traversal methods of this class visit elements in the order they were inserted.
「挿入順序を保持する」とちゃんと書かれています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
scala> scala.util.Properties.versionString res0: String = version 2.11.6 scala> val linkedHashMap = scala.collection.mutable.LinkedHashMap[String, String]() linkedHashMap: scala.collection.mutable.LinkedHashMap[String,String] = Map() scala> linkedHashMap += ("First" -> "") res1: linkedHashMap.type = Map(First -> "") scala> linkedHashMap += ("Second" -> "") res2: linkedHashMap.type = Map(First -> "", Second -> "") scala> linkedHashMap += ("Third" -> "") res3: linkedHashMap.type = Map(First -> "", Second -> "", Third -> "") scala> linkedHashMap += ("Fourth" -> "") res4: linkedHashMap.type = Map(First -> "", Second -> "", Third -> "", Fourth -> "") |
