前回は「列 (Seq)」について説明しました。今回は Scala の基本的なコレクションである「マップ (Map)」と「セット (Set)」について説明します。
マップは「連想配列」のことで、Perl や Ruby では「ハッシュ (Hash)」と呼ばれています。配列が整数値を使って要素を指定するのに対し、マップはキー (key) というデータを使って要素を指定します。一般に、連想配列のキーには文字列が用いられますが、Scala では「ハッシュ値」の計算と等値の判定ができれば、マップのキーとして使用することができます。
等値の判定はメソッド equals で、ハッシュ値の計算はメソッド hashCode で行います。文字列や数値など基本的な型には equals と hashCode が定義されています。また、case class はどちらのメソッドも自動的に作成されるので、case class のインスタンスはマップのキーとして使用することができます。なお、サブクラスをキーにする場合は、メソッド CanEqual が必要になりますが、case class はこのメソッドも自動的に作成されます。
Perl や Ruby で連想配列をハッシュと呼ぶのは、連想配列を実現するアルゴリズムに「ハッシュ法 (hashing)」が用いられているからです。Scala の場合、不変 (immutable) なマップはハッシュトライ (Hash Trie) といって木構造を使ったハッシュ法が用いられています。可変 (mutable) なマップはハッシュ表 と(Hash Table) いって配列を使ったハッシュ法になります。
ハッシュ法はデータを高速に探索できるアルゴリズムです。線形探索では時間がとてもかかる処理でも、マップを遣うと高速にデータを探索することができます。ハッシュ法 (ハッシュ表) のアルゴリズムに興味のある方は、拙作のページ拙作のページ Algorithms with Python 「ハッシュ法」をお読みくださいませ。
最初に不変なマップから説明しましょう。マップの型は Map[K,V] で、型パラメータ K がキーを、V が値を表します。マップを生成する構文を示します。
Map[K, V]() Map[K, V](Key1 -> Value1, Key2 -> Value2, ...)
Map[K, V] の後ろのカッコでキーと値を指定します。() だけだと空のマップを生成します。-> はタプルを生成する構文です。Scala の場合、Map は -> を使ってキーと値を指定します。キーと値を指定する場合、型 [K, V] を指定しなくても Scala が型推論で型を決めてくれます。
簡単な例を示しましょう。
scala> val a = Map("foo" -> 10, "bar" -> 20)
val a: Map[String,Int] = Map(foo -> 10, bar -> 20)
scala> a("foo")
val res0: Int = 10
scala> a("bar")
val res1: Int = 20
scala> a("baz")
java.util.NoSuchElementException: key not found: baz
at scala.collection.immutable.Map$Map2.apply(Map.scala:316)
... 33 elided
scala> a contains "foo"
val res3: Boolean = true
scala> a contains "baz"
val res4: Boolean = false
scala> a.get("foo")
val res5: Option[Int] = Some(10)
scala> a.get("baz")
val res6: Option[Int] = None
scala> a.getOrElse("foo", 0)
val res7: Int = 10
scala> a.getOrElse("baz", 0)
val res8: Int = 0
scala> a.size
val res9: Int = 2
scala> a.isEmpty
val res10: Boolean = false
マップのアクセスは列と同様にカッコ ( ) を使います。マップを生成して変数 a にセットします。a("foo") でキー "foo" のデータを参照することができます。immutable なマップなので、値を書き換えることはできません。キーが見つからない場合はエラーが送出されます。
キーの有無はメソッド contains でチェックすることができます。メソッド get は Option 型を返すので、キーがあれば値を Some に包んで返します。見つからない場合は None を返します。getOrElse(k, d) はキー k が見つからない場合はデフォルト値 d を返します。マップの大きさはメソッド size で取得することができます。メソッド isEmpty はマップが空であれば true を、そうでなければ false を返します。
データの追加は演算子 + を使います。次の例を見てください。
scala> val b = a + ("baz" -> 30)
val b: Map[String,Int] = Map(foo -> 10, bar -> 20, baz -> 30)
scala> b.get("foo")
val res12: Option[Int] = Some(10)
scala> b.get("baz")
val res13: Option[Int] = Some(30)
scala> val c = b.updated("oops", 40)
val c: Map[String,Int] = Map(foo -> 10, bar -> 20, baz -> 30, oops -> 40)
scala> c.get("oops")
val res14: Option[Int] = Some(40)
a + ("baz" -> 30) は、マップ a に "baz" -> 30 を追加した新しいマップを生成します。演算子 + のほかに、メソッド updated を使って新しいキーと値を追加することもできます。
演算子 ++ を使うと、他のマップやタプル (key, value) を格納した列のデータをマップに追加することができます。
scala> val a = Map(1 -> 10, 2 -> 20, 3 -> 30) val a: Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30) scala> a ++ Map(4 -> 40, 5 -> 50, 6 -> 60) val res15: Map[Int,Int] = HashMap(5 -> 50, 1 -> 10, 6 -> 60, 2 -> 20, 3 -> 30, 4 -> 40) scala> a ++ List((4, 40), (5, 50), (6, 60)) val res16: Map[Int,Int] = HashMap(5 -> 50, 1 -> 10, 6 -> 60, 2 -> 20, 3 -> 30, 4 -> 40) scala> a ++ Array((4, 40), (5, 50), (6, 60)) val res17: Map[Int,Int] = HashMap(5 -> 50, 1 -> 10, 6 -> 60, 2 -> 20, 3 -> 30, 4 -> 40) scala> a ++ Map(1 -> 100) val res18: Map[Int,Int] = Map(1 -> 100, 2 -> 20, 3 -> 30)
HashMap はハッシュトライを表すクラスです。Scala のマップは、要素数が 5 個以上になると HashMap が使用され、要素数が 5 個未満の場合はもっと単純なデータ構造が使用されます。左辺と右辺で同じキーがある場合、左辺の値は右辺の値に置き換えられます。
データの削除は演算子 - を使います。次の例を見てください。
scala> val a = Map("foo" -> 10, "bar" -> 20, "baz" -> 30)
val a: Map[String,Int] = Map(foo -> 10, bar -> 20, baz -> 30)
scala> a - "foo"
val res0: Map[String,Int] = Map(bar -> 20, baz -> 30)
scala> a - ("foo", "bar")
there was 1 deprecation warning; re-run with -deprecation for details
1 warning found
val res1: Map[String,Int] = Map(baz -> 30)
scala> a - "oops"
val res2: Map[String,Int] = Map(foo -> 10, bar -> 20, baz -> 30)
演算子 - はマップからキーとその値を削除した新しいマップを返します。以前のバージョンでは、タプルに格納したキーをまとめて削除することができたのですが、ver 2.13 から非推奨の機能になったようです。複数のキーをまとめて削除するには、次に説明する演算子 -- を使います。
演算子 -- を使うと、キーを格納した列のデータをマップから削除することができます。
scala> val a = Map(1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40) val a: Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40) scala> a -- (1, 3) -- [E007] Type Mismatch Error: --------------------------------- 1 |a -- (1, 3) | ^^^^^^ | Found: (Int, Int) | Required: IterableOnce[Int] | | longer explanation available when compiling with `-explain` 1 error found scala> a -- List(1, 3) val res1: Map[Int,Int] = Map(2 -> 20, 4 -> 40) scala> a -- Array(1, 3) val res2: Map[Int,Int] = Map(2 -> 20, 4 -> 40)
マップから複数のキーを削除する場合、タプルは使わないほうがよさそうです。ご注意くださいませ。
マップは for 式、メソッド foreach、イテレータを使って、キーと値を順番に取り出すことができます。
scala> val a = Map("foo" -> 10, "bar" -> 20, "baz" -> 30)
val a: Map[String,Int] = Map(foo -> 10, bar -> 20, baz -> 30)
scala> for (x <- a) println(x)
(foo,10)
(bar,20)
(baz,30)
scala> a foreach println
(foo,10)
(bar,20)
(baz,30)
scala> val it = a.iterator
val it: Iterator[(String, Int)] = <iterator>
scala> while (it.hasNext) println(it.next())
(foo,10)
(bar,20)
(baz,30)
キーと値はタプルに格納されて渡されます。for 式の場合はパターンマッチングが使えるので、キーと値を別々の変数に取り出すのは簡単です。
scala> for ((k, v) <- a) { println(k); println(v) }
foo
10
bar
20
baz
30
マップ Map[K, V] は列 Seq[(K, V)] に変換することができます。逆に、列 Seq[(K, V)] はマップ Map[K, V] に変換することができます。
簡単な例を示しましょう。
scala> val a = Map("foo" -> 10, "bar" -> 20, "baz" -> 30)
val a: Map[String,Int] = Map(foo -> 10, bar -> 20, baz -> 30)
scala> a.toList
val res0: List[(String, Int)] = List((foo,10), (bar,20), (baz,30))
scala> a.toVector
val res1: Vector[(String, Int)] = Vector((foo,10), (bar,20), (baz,30))
scala> a.toArray
val res2: Array[(String, Int)] = Array((foo,10), (bar,20), (baz,30))
scala> List((1, 10), (2, 20), (3, 30)).toMap
val res3: Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30)
scala> Vector((1, 10), (2, 20), (3, 30)).toMap
val res4: Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30)
scala> Array((1, 10), (2, 20), (3, 30)).toMap
val res5: Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30)
toList, toVector, toArray などでマップを列に変換することができます。また、列はメソッド toMap でマップに変換することができます。
可変 (mutable) なマップは scala.collection.mutable.Map を使います。Map は immutable なマップが使っているので、import で別名を付けるといいでしょう。簡単な例を示します。
scala> import scala.collection.mutable.{Map => MMap}
scala> val a = MMap("foo" -> 10, "bar" -> 20)
val a: scala.collection.mutable.Map[String,Int] = HashMap(bar -> 20, foo -> 10)
scala> a("foo")
val res0: Int = 10
scala> a contains "foo"
val res1: Boolean = true
scala> a get "baz"
val res2: Option[Int] = None
基本的には immutable なマップと同じメソッドが使えますが、演算子 +, ++, -, -- は mutable なマップでも新しいマップを生成することに注意してください。
mutable なマップは値を書き換えることができます。
m(key) = value m.update(key, value)
マップを m とすると、列と同様に m(key) = value, または m.update(key, value) で key の値を value に更新します。
簡単な例を示しましょう。
scala> a("foo") = 100
scala> a
val res4: scala.collection.mutable.Map[String,Int] = HashMap(bar -> 20, foo -> 100)
scala> a.update("bar", 200)
scala> a
val res6: scala.collection.mutable.Map[String,Int] = HashMap(bar -> 200, foo -> 100)
マップにキーが含まれていない場合は、そのマップに新しいキーと値を追加します。
scala> a("baz") = 300
scala> a
val res8: scala.collection.mutable.Map[String,Int] = HashMap(bar -> 200, baz -> 300, foo -> 100)
scala> a.getOrElseUpdate("foo", 500)
val res9: Int = 100
scala> a.update("oops", 400)
scala> a
val res11: scala.collection.mutable.Map[String,Int] = HashMap(bar -> 200, baz -> 300, foo -> 100, oops -> 400)
scala> a.getOrElseUpdate("foo1", 500)
val res12: Int = 500
scala> a
val res13: scala.collection.mutable.Map[String,Int] =
HashMap(bar -> 200, baz -> 300, foo1 -> 500, foo -> 100, oops -> 400)
メソッド getOrElseUpdate は、キーが見つかればその値を返します。キーが見つからない場合は、キーと値をマップに追加して値を返します。キー "foo" はマップ a にあるので、その値 100 を返します。キー "foo1" はマップ a にないので "foo1" -> 500 を追加して、値 500 を返します。
更新処理は演算子 += でも行うことができます。
scala> a += ("bar" -> 2)
val res14: scala.collection.mutable.Map[String,Int] =
HashMap(bar -> 2, foo -> 100, oops -> 400, baz -> 300, foo1 -> 500)
scala> a += ("bar1" -> 20)
val res15: scala.collection.mutable.Map[String,Int] =
HashMap(bar1 -> 20, bar -> 2, foo -> 100, oops -> 400, baz -> 300, foo1 -> 500)
演算子 + を使うと新しいマップが生成されることに注意してください。
キーの削除は演算子 -= または remove で行います。
scala> a -= "foo1" val res16: scala.collection.mutable.Map[String,Int] = HashMap(bar1 -> 20, bar -> 2, foo -> 100, oops -> 400, baz -> 300) scala> a remove "bar1" val res17: Option[Int] = Some(20) scala> a remove "foo1" val res18: Option[Int] = None scala> a val res19: scala.collection.mutable.Map[String,Int] = HashMap(bar -> 2, foo -> 100, oops -> 400, baz -> 300) scala> a.clear() scala> a val res21: scala.collection.mutable.Map[String,Int] = HashMap()
演算子 -= の返り値はマップになりますが、remove は削除したキーの値を Option 型で返します。メソッド clear はマップの全データを削除します。マップは空になります。
また、他のコレクションに格納されているデータでマップを更新する場合は演算子 ++=, --= を使います。
scala> val a = MMap(1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40, 5 -> 50) val a: scala.collection.mutable.Map[Int,Int] = HashMap(1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40, 5 -> 50) scala> a ++= List((6, 60), (7, 70), (8, 80)) val res23: scala.collection.mutable.Map[Int,Int] = HashMap(1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40, 5 -> 50, 6 -> 60, 7 -> 70, 8 -> 80) scala> a --= List(6, 7, 8) val res24: scala.collection.mutable.Map[Int,Int] = HashMap(1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40, 5 -> 50)
「セット (Set)」はリストやマップのように要素を格納するコレクションですが、リストと違って要素に順番はなく、重複した要素を含まないところが特徴です。セットはデータの集合を表すのに便利なデータ型です。集合は要素の順番に意味はありません。たとえば集合 {1, 3, 5, 7} は {7, 5, 3, 1} や {5, 3, 1, 7} と表すこともできます。このように、要素は適当に並べてもかまわないのですが、ある規則で要素を整列させておく場合もあります。
Scala のセットはマップと同様に、不変 (immutable) なセットはハッシュトライ (Hash Trie) という木構造を使ったハッシュ法が用いられています。可変 (mutable) なセットは配列を使ったハッシュ法になります。当然ですが、セットを使う場合はメソッド equals と hashCode が必要になります。
最初に不変なセットから説明しましょう。セットの型は Set[A] で、型パラメータ A が要素の型を表します。セットは次の構文で生成します。
Set[A]() Set[A](item1, item2, ...)
マップと同様にカッコの中に要素を指定します。() だけの場合は空のセットが生成されます。要素を指定する場合は型 [A] を省略することができます。Scala が型推論で型を決めてくれます。
簡単な例を示します。
scala> val a = Set(1, 2, 3, 4) val a: Set[Int] = Set(1, 2, 3, 4) scala> a contains 3 val res0: Boolean = true scala> a(3) val res1: Boolean = true scala> a(0) val res2: Boolean = false scala> a contains 0 val res3: Boolean = false scala> a.size val res4: Int = 4 scala> a.isEmpty val res5: Boolean = false
要素の有無はメソッド contains でチェックすることができます。カッコ ( ) によるアクセスも contains と同じ意味になります。つまり、a(3) は a contains 3 と同じで、セット a に要素 3 があれば true を返し、無ければ false を返します。セットの大きさはメソッド size で求めることができます。メソッド isEmpty はセットが空であれば true を、そうでなければ false を返します。
データの追加は演算子 + を使います。
scala> a + 10 val res6: Set[Int] = HashSet(10, 1, 2, 3, 4) scala> a + (10, 20, 30) there was 1 deprecation warning; re-run with -deprecation for details 1 warning found val res7: Set[Int] = HashSet(10, 20, 1, 2, 3, 30, 4)
演算子 + は要素を追加した新しいセットを返します。以前のバージョンでは、タプルに格納された要素をまとめて追加することができなのですが、ver 2.13 から非推奨の機能になりました。複数の要素をまとめて追加するには演算子 ++ を使います。
演算子 ++ を使うと、セットや他の列に格納されたデータを追加することができます。
scala> a val res8: Set[Int] = Set(1, 2, 3, 4) scala> a ++ Set(5, 6, 7, 8) val res9: Set[Int] = HashSet(5, 1, 6, 2, 7, 3, 8, 4) scala> a ++ List(5, 6, 7, 8) val res10: Set[Int] = HashSet(5, 1, 6, 2, 7, 3, 8, 4) scala> a ++ Array(5, 6, 7, 8) val res11: Set[Int] = HashSet(5, 1, 6, 2, 7, 3, 8, 4) scala> a ++ (5, 6, 7, 8) -- [E134] Type Error: ------------------------------------------------------------- 1 |a ++ (5, 6, 7, 8) |^^^^ |None of the overloaded alternatives of method ++ in trait IterableOps with types | [B >: Int](suffix: IterableOnce[B]): Set[B] | (that: IterableOnce[Int]): Set[Int] |match arguments ((Int, Int, Int, Int)) 1 error found
データの削除は演算子 - を使います。
scala> a val res13: Set[Int] = Set(1, 2, 3, 4) scala> a - 4 val res14: Set[Int] = Set(1, 2, 3) scala> a - (1, 2, 3) there was 1 deprecation warning; re-run with -deprecation for details 1 warning found val res15: Set[Int] = Set(4) scala> a - 10 val res16: Set[Int] = Set(1, 2, 3, 4)
演算子 - は要素を削除した新しい集合を返します。削除する要素が無い場合は、セットをそのまま返します。以前のバージョンでは、タプルに格納された要素をまとめて削除することができたのですが、ver 2.13 から非推奨の機能になりました。複数の要素をまとめて削除するには演算子 -- を使います。
演算子 -- を使うと、セットや他の列に格納されたデータを削除することができます。
scala>a val res18: Set[Int] = Set(1, 2, 3, 4) scala> a -- Set(1, 3) val res19: Set[Int] = Set(2, 4) scala> a -- List(1, 3) val res20: Set[Int] = Set(2, 4) scala> a -- Array(1, 3) val res21: Set[Int] = Set(2, 4) scala> a -- (1, 3) -- [E007] Type Mismatch Error: -------------------------------- 1 |a -- (1, 3) | ^^^^^^ | Found: (Int, Int) | Required: IterableOnce[Int] | | longer explanation available when compiling with `-explain` 1 error found
セットは集合を扱うメソッドや演算子が用意されています。主なメソッドを下表に示します。
| メソッド | 機能 |
|---|---|
| s1 subsetOf s2 | s1 が s2 の部分集合であれば真を返す |
| s1 intersect s2 | s1 と s2 の積を求める (s1 & s2) |
| s1 union s2 | s1 と s2 の和を求める (s1 | s2) |
| s1 diff s2 | s1 と s2 の差を求める (s1 &~ s2) |
簡単な例を示しましょう。なお、セットの等値は演算子 ==, != で判定することができます。
scala> val a = Set(1, 2, 3, 4) val a: Set[Int] = Set(1, 2, 3, 4) scala> val b = Set(3, 4, 5, 6) val b: Set[Int] = Set(3, 4, 5, 6) scala> a union b val res0: Set[Int] = HashSet(5, 1, 6, 2, 3, 4) scala> a | b val res1: Set[Int] = HashSet(5, 1, 6, 2, 3, 4) scala> a intersect b val res2: Set[Int] = Set(3, 4) scala> a & b val res3: Set[Int] = Set(3, 4) scala> a diff b val res4: Set[Int] = Set(1, 2) scala> a &~ b val res5: Set[Int] = Set(1, 2) scala> Set(1, 2) subsetOf a val res6: Boolean = true scala> Set(1, 2) subsetOf b val res7: Boolean = false scala> Set(4,3,2,1) == a val res8: Boolean = true scala> Set(1, 2, 3) + 4 == a val res9: Boolean = true scala> a == b val res10: Boolean = false
セットは for 式、メソッド foreach、イテレータを使って、要素を順番に取り出すことができます。
scala> val a = Set(1, 2, 3, 4, 5) val a: Set[Int] = HashSet(5, 1, 2, 3, 4) scala> for (x <- a) println(x) 5 1 2 3 4 scala> a foreach println 5 1 2 3 4 scala> val it = a.iterator val it: Iterator[Int] = <iterator> scala> while (it.hasNext) println(it.next()) 5 1 2 3 4
セット Set[A] は列 Seq[A] に変換することができます。逆に、列 Seq[A] はセット Set[A] に変換することができます。
簡単な例を示しましょう。
scala> a val res14: Set[Int] = HashSet(5, 1, 2, 3, 4) scala> a.toList val res15: List[Int] = List(5, 1, 2, 3, 4) scala> a.toVector val res16: scala.collection.immutable.Vector[Int] = Vector(5, 1, 2, 3, 4) scala> a.toArray val res17: Array[Int] = Array(5, 1, 2, 3, 4) scala> List(1, 2, 3, 1, 1, 2, 3, 4).toSet val res18: Set[Int] = Set(1, 2, 3, 4) scala> Vector(1, 2, 3, 1, 1, 2, 3, 4).toSet val res19: Set[Int] = Set(1, 2, 3, 4) scala> Array(1, 2, 3, 1, 1, 2, 3, 4).toSet val res20: Set[Int] = Set(1, 2, 3, 4)
toList, toVector, toArray などでセットを列に変換することができます。また、列はメソッド toSet でセットに変換することができます。このとき、重複要素が削除されることに注意してください。
可変 (mutable) なセットは scala.collection.mutable.Set を使います。Set は immutable なセットが使っているので、import で別名を付けるといいでしょう。簡単な例を示します。
scala> import scala.collection.mutable.{Set=>MSet}
scala> val a = MSet(1, 2, 3, 4, 5)
val a: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 5)
scala> a(3)
val res0: Boolean = true
scala> a contains 3
val res1: Boolean = true
scala> a(0)
val res2: Boolean = false
scala> a contains 10
val res3: Boolean = false
mutable なセットは要素の追加や削除を破壊的に行うことができます。自分自身を書き換えるので、元の値は残りません。
要素の追加は演算子 += もしくはメソッド add を使います。簡単な例を示しましょう。
scala> a += 10 val res4: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 5, 10) scala> a += (20, 30, 40) there was 1 deprecation warning; re-run with -deprecation for details 1 warning found val res5: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 20, 5, 40, 10, 30) scala> a add 100 val res6: Boolean = true scala> a val res7: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 20, 100, 5, 40, 10, 30) scala> a add 100 val res8: Boolean = false scala> a val res9: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 20, 100, 5, 40, 10, 30)
演算子 += はセットを返しますが、メソッド add は要素を追加した場合は true を、同じ要素があって追加できなかった場合は false を返します。以前のバージョンでは、タプルに格納された要素をまとめて追加することができたのですが、ver 2.13 から非推奨の機能になりました。
要素の削除は演算子 -= もしくは remove を使います。
scala> a -= 100 val res10: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 20, 5, 40, 10, 30) scala> a remove 40 val res11: Boolean = true scala> a remove 50 val res12: Boolean = false scala> a val res13: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 20, 5, 10, 30) scala> a -= (10, 20, 30) there was 1 deprecation warning; re-run with -deprecation for details 1 warning found val res14: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 5) scala> a.clear() scala> a val res16: scala.collection.mutable.Set[Int] = HashSet()
演算子 -= はセットを返しますが、メソッド remove は要素を削除できた場合は true を、要素が無くて削除できなかった場合は false を返します。以前のバージョンでは、タプルに格納された要素をまとめて削除することができたのですが、ver 2.13 から非推奨の機能になりました。メソッド clear は全要素を削除します。つまり、セットを空にします。
なお、mutable なセットの更新は演算子 ++= や --= を使っても行うことができます。
scala> val a = MSet(1, 2, 3, 4, 5)
val a: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 5)
scala> a ++= Set(6,7,8,9)
val res17: scala.collection.mutable.Set[Int] = HashSet(1, 2, 3, 4, 5, 6, 7, 8, 9)
scala> a ++= List(10, 11, 12, 13, 14, 15)
val res18: scala.collection.mutable.Set[Int] =
HashSet(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
scala> a --= List(6, 7, 8, 9, 10)
val res19: scala.collection.mutable.Set{int] =
HashSet(1, 2, 3, 4, 5, 11, 12, 13, 14, 15)
scala> a --= Set(1, 2, 3, 4, 5)
val res20: scala.collection.mutable.Set[Int] = HashSet(11, 12, 13, 14, 15)
ハッシュ法はデータを高速に探索できる優れたアルゴリズムですが、データの順序はバラバラになるので、たとえばデータの中から最小値や最大値を探すような処理には不向きです。このような場合、順序木を使ってマップやセットを実装すると、最小値や最大値を簡単に求めることができるようになります。Scala には scala.collection.imutable に TreeMap と TreeSet が用意されています。
Scala の場合、TreeMap と TreeSet の実装には「赤黒木 (Red-Black Tree)」という二分木 (平衡木) が使われています。データ数を N とすると、平衡木はデータの挿入、探索、削除を O(log2 N) で行うことができます。平衡木のアルゴリズムに興味のある方は、拙作のページ Algorithms with Python をお読みください。AVL 木、2-3 木、赤黒木、AA 木について詳しく説明しています。
TreeMap の型は TreeMap[K, V] で、TreeSet の型は TreeSet[A] です。TreeMap と TreeSet は次の構文で生成します。
TreeMap[K, V]()(implicit ordering: Ordering[K]) TreeMap[K, V](k1 -> v1, k2 -> v2, ...)(implicit ordering: Ordering[K])
TreeSet[A]()(implicit ordering: Ordering[A]) TreeSet[A](item1, item2, ...)(implicit ordering: Ordering[A])
データの比較には Ordering を使います。これは暗黙の引数として定義されているので省略することができます。
簡単な例を示しましょう。
scala> import scala.collection.immutable.{TreeMap, TreeSet}
scala> val a = TreeMap("foo" -> 10, "bar" -> 20, "baz" -> 30)
val a: scala.collection.immutable.TreeMap[String,Int] = TreeMap(bar -> 20, baz -> 30, foo -> 10)
scala> a("foo")
val res0: Int = 10
scala> a.get("oops")
val res1: Option[Int] = None
scala> val b = TreeSet(5, 4, 3, 2, 1)
val b: scala.collection.immutable.TreeSet[Int] = TreeSet(1, 2, 3, 4, 5)
scala> b(1)
val res2: Boolean = true
scala> b(10)
val res3: Boolean = false
データの挿入は Map や Set と同じメソッドで行うことができます。最小値と最大値は fisrtKey, lastKey, min, max で求めることができます。
scala> a.firstKey val res9: String = bar scala> a.lastKey val res10: String = foo scala> a.min val res11: (String, Int) = (bar,20) scala> a.max val res12: (String, Int) = (foo,10) scala> b.firstKey val res13: Int = 1 scala> b.lastKey val res14: Int = 5 scala> b.min val res15: Int = 1 scala> b.max val res16: Int = 5
TreeMap の場合、max と min は該当するキーとその値をタプルに格納して返します。
for 式、メソッド foreach、イテレータで要素を取り出すと、それは昇順にソートした結果と同じになります。
scala> for (x <- a) println(x) (bar,20) (baz,30) (foo,10) scala> a.foreach(println) (bar,20) (baz,30) (foo,10) scala> val it1 = a.iterator val it1: Iterator[(String, Int)] = <iterator> scala> while (it1.hasNext) println(it1.next()) (bar,20) (baz,30) (foo,10) scala> for (x <- b) println(x) 1 2 3 4 5 scala> b.foreach(println) 1 2 3 4 5 scala> val it2 = b.iterator val it2: Iterator[Int] = <iterator> scala> while (it2.hasNext) println(it2.next()) 1 2 3 4 5
このほかにも、便利なメソッドが多数用意されています。詳細は Scala のドキュメントをお読みください。
最後に「たらいまわし関数」を使ってハッシュ法の効果を確かめてみましょう。次のリストを見てください。
リスト : たらいまわし関数
def tarai(x:Int, y:Int, z:Int): Int =
if (x <= y) y
else tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
def tak(x:Int, y:Int, z:Int): Int =
if (x <= y) z
else tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
関数 tarai や tak は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、John Macarthy 先生によって作成されたそうです。
それでは、さっそく実行してみましょう。
tarai(16, 8, 0) : 53.7 [s] tak(24, 12, 0) : 6.4 [s] 実行環境 : Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数が遅いのは、同じ値を何度も計算しているためです。この場合、表 (table) を使って処理を高速化することができます。同じ値を何度も計算することがないように、計算した値は表に格納しておいて、2 回目以降は表から計算結果を求めるようにします。このような手法を「表計算法」とか「メモ化 (memoization または memoisation)」といいます。
関数 tarai の場合は「遅延評価」を行う処理系、たとえば関数型言語の Haskell では高速に実行することができます。プログラムを見てください。x <= y のとき、tarai は y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。Scala にも遅延評価があるので、tarai の高速化は遅延評価を取り上げるところで行ってみましょう。なお、tak は x <= y のときに z を返しているため、遅延評価で高速化することはできません。ご注意ください。
それでは、関数 tak をメモ化してみましょう。Scala の場合、メモ化は mutable なマップを使うと簡単です。次のリストを見てください。
リスト : たらいまわし関数のメモ化
// ハッシュ表
val takTbl = MMap[(Int,Int,Int),Int]()
def takMemo(x: Int, y: Int, z: Int): Int =
takTbl.get((x, y, z)) match {
case Some(n) => n
case None => {
val n = if (x <= y) z
else takMemo(takMemo(x - 1, y, z),
takMemo(y - 1, z, x),
takMemo(z - 1, x, y))
takTbl((x, y, z)) = n
n
}
}
// 連想リスト
val takLst = ListMap[(Int,Int,Int),Int]()
def takMemoL(x: Int, y: Int, z: Int): Int =
takLst.get((x, y, z)) match {
case Some(n) => n
case None => {
val n = if (x <= y) z
else takMemoL(takMemoL(x - 1, y, z),
takMemoL(y - 1, z, x),
takMemoL(z - 1, x, y))
takLst((x, y, z)) = n
n
}
}
関数 takMemo の値を格納するマップ (ハッシュ表) を変数 takTbl に用意します。関数 tak では、引数 x, y, z を要素とするタプルを作り、それをキーとして takTbl を検索します。takTbl にキーがあれば、その値を返します。そうでなければ、値を計算して takTbl にセットして、その値を返します。
実行速度を比較するため、連想リストを使ったマップ ListMap でメモ化した関数 takMemoL を作ります。LispMap は scala.collection.mutable に用意されています。ListMap はキーを線形探索するので、実行時間は Map (ハッシュ表) よりも遅くなるはずです。なお、mutable な ListMap は ver 2.13 から非推奨になりましたが、本稿ではそのまま使用することにします。
実際に tak(24, 12, 0) を試してみたところ、メモ化の効果はとても大きくて、連想リスト (ListMap) でも実行時間は 1 秒かかりません。そこで、引数の値をもっと増やして実行してみました。
tak (80, 40, 0) 連想リスト : 4.853 [s] ハッシュ表 : 0.037 [s]
Map (ハッシュ表) の場合、引数の値を増やしても高速に実行することができます。ハッシュ法の効果も大変大きいですね。また、同じ計算を再度実行すると、メモ化の働きにより値をすぐに求めることができます。
//
// tarai.scala : たらいまわし関数
//
// Copyright (C) 2014-2024 Makoto Hiroi
//
import scala.collection.mutable.{Map => MMap, ListMap}
object Tarai {
// たらいまわし関数
def tarai(x:Int, y:Int, z:Int): Int =
if (x <= y) y
else tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
def tak(x:Int, y:Int, z:Int): Int =
if (x <= y) z
else tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
// ハッシュ表
val takTbl = MMap[(Int,Int,Int),Int]()
def takMemo(x: Int, y: Int, z: Int): Int =
takTbl.get((x, y, z)) match {
case Some(n) => n
case None => {
val n = if (x <= y) z
else takMemo(takMemo(x - 1, y, z),
takMemo(y - 1, z, x),
takMemo(z - 1, x, y))
takTbl((x, y, z)) = n
n
}
}
// 連想リスト
val takLst = ListMap[(Int,Int,Int),Int]()
def takMemoL(x: Int, y: Int, z: Int): Int =
takLst.get((x, y, z)) match {
case Some(n) => n
case None => {
val n = if (x <= y) z
else takMemoL(takMemoL(x - 1, y, z),
takMemoL(y - 1, z, x),
takMemoL(z - 1, x, y))
takLst((x, y, z)) = n
n
}
}
def main(args: Array[String]): Unit = {
val s0 = System.currentTimeMillis
println(tarai(16, 8, 0))
println(s"${System.currentTimeMillis - s0} msec")
val s1 = System.currentTimeMillis
println(tak(24, 12, 0))
println(s"${System.currentTimeMillis - s1} msec")
val s2 = System.currentTimeMillis
println(takMemoL(80, 40, 0))
println(s"${System.currentTimeMillis - s2} msec")
val s3 = System.currentTimeMillis
println(takMemo(80, 40, 0))
println(s"${System.currentTimeMillis - s3} msec")
}
}