お気楽 Scala プログラミング入門

マップ (Map) とセット (Set)

前回は「列 (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 ハッシュ法をお読みくださいませ。

●不変 (immutable) なマップ

最初に不変なマップから説明しましょう。マップの型は 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: scala.collection.immutable.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:298)
  ... 32 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: scala.collection.immutable.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: scala.collection.immutable.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: scala.collection.immutable.Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30)

scala> a ++ Map(4 -> 40, 5 -> 50, 6 -> 60)
val res15: scala.collection.immutable.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: scala.collection.immutable.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: scala.collection.immutable.Map[Int,Int] = 
HashMap(5 -> 50, 1 -> 10, 6 -> 60, 2 -> 20, 3 -> 30, 4 -> 40)

scala> a ++ Map(1 -> 100)
val res18: scala.collection.immutable.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: scala.collection.immutable.Map[String,Int] = Map(foo -> 10, bar -> 20, baz -> 30)

scala> a - "foo"
val res0: scala.collection.immutable.Map[String,Int] = Map(bar -> 20, baz -> 30)

scala>  a - ("foo", "bar")
          ^
       warning: method - in trait MapOps is deprecated (since 2.13.0): Use -- with an explicit collection
val res1: scala.collection.immutable.Map[String,Int] = Map(baz -> 30)

scala> a - "oops"
val res2: scala.collection.immutable.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: scala.collection.immutable.Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40)

scala> a -- (1, 3)
                ^
       error: too many arguments (found 2, expected 1) for method --: 
(keys: scala.collection.IterableOnce[Int]): scala.collection.immutable.Map[Int,Int]

scala> a -- List(1, 3)
val res1: scala.collection.immutable.Map[Int,Int] = Map(2 -> 20, 4 -> 40)

scala> a -- Array(1, 3)
val res2: scala.collection.immutable.Map[Int,Int] = Map(2 -> 20, 4 -> 40)

マップから複数のキーを削除する場合、タプルは使わないほうがよさそうです。ご注意くださいませ。

●キーと値の取得

マップは for 式、メソッド foreach、イテレータを使って、キーと値を順番に取り出すことができます。

scala> val a = Map("foo" -> 10, "bar" -> 20, "baz" -> 30)
val a: scala.collection.immutable.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: scala.collection.immutable.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: scala.collection.immutable.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: scala.collection.immutable.Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30)

scala> Vector((1, 10), (2, 20), (3, 30)).toMap
val res4: scala.collection.immutable.Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30)

scala> Array((1, 10), (2, 20), (3, 30)).toMap
val res5: scala.collection.immutable.Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30)

toList, toVector, toArray などでマップを列に変換することができます。また、列はメソッド toMap でマップに変換することができます。

●可変 (mutable) なマップ

可変 (mutable) なマップは scala.collection.mutable.Map を使います。Map は immutable なマップが使っているので、import で別名を付けるといいでしょう。簡単な例を示します。

scala> import scala.collection.mutable.{Map => MMap}
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: a.type = HashMap(bar -> 2, foo -> 100, oops -> 400, baz -> 300, foo1 -> 500)

scala> a += ("bar1" -> 20)
val res15: a.type = HashMap(bar1 -> 20, bar -> 2, foo -> 100, oops -> 400, baz -> 300, foo1 -> 500)

演算子 + を使うと新しいマップが生成されることに注意してください。

キーの削除は演算子 -= または remove で行います。

scala> a -= "foo1"
val res16: a.type = 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: a.type = 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: a.type = 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 が必要になります。

●不変 (immutable) なセット

最初に不変なセットから説明しましょう。セットの型は Set[A] で、型パラメータ A が要素の型を表します。セットは次の構文で生成します。

Set[A]()
Set[A](item1, item2, ...)

マップと同様にカッコの中に要素を指定します。() だけの場合は空のセットが生成されます。要素を指定する場合は型 [A] を省略することができます。Scala が型推論で型を決めてくれます。

簡単な例を示します。

scala> val a = Set(1, 2, 3, 4)
val a: scala.collection.immutable.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: scala.collection.immutable.Set[Int] = HashSet(10, 1, 2, 3, 4)

scala> a + (10, 20, 30)
         ^
       warning: method + in trait SetOps is deprecated (since 2.13.0): 
Use ++ with an explicit collection argument instead of + with varargs
val res7: scala.collection.immutable.Set[Int] = HashSet(10, 20, 1, 2, 3, 30, 4)

演算子 + は要素を追加した新しいセットを返します。以前のバージョンでは、タプルに格納された要素をまとめて追加することができなのですが、ver 2.13 から非推奨の機能になりました。複数の要素をまとめて追加するには演算子 ++ を使います。

演算子 ++ を使うと、セットや他の列に格納されたデータを追加することができます。

scala> a
val res8: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

scala> a ++ Set(5, 6, 7, 8)
val res9: scala.collection.immutable.Set[Int] = HashSet(5, 1, 6, 2, 7, 3, 8, 4)

scala> a ++ List(5, 6, 7, 8)
val res10: scala.collection.immutable.Set[Int] = HashSet(5, 1, 6, 2, 7, 3, 8, 4)

scala> a ++ Array(5, 6, 7, 8)
val res11: scala.collection.immutable.Set[Int] = HashSet(5, 1, 6, 2, 7, 3, 8, 4)

scala> a ++ (5, 6, 7, 8)
         ^
       error: overloaded method ++ with alternatives:

●データの削除

データの削除は演算子 - を使います。

scala> a
val res13: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

scala> a - 4
val res14: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

scala> a - (1, 2, 3)
         ^
       warning: method - in trait SetOps is deprecated (since 2.13.0): 
Use &- with an explicit collection argument instad of - with varargs
val res15: scala.collection.immutable.Set[Int] = Set(4)

scala> a - 10
val res16: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

演算子 - は要素を削除した新しい集合を返します。削除する要素が無い場合は、セットをそのまま返します。以前のバージョンでは、タプルに格納された要素をまとめて削除することができたのですが、ver 2.13 から非推奨の機能になりました。複数の要素をまとめて削除するには演算子 -- を使います。

演算子 -- を使うと、セットや他の列に格納されたデータを削除することができます。

scala>a
val res18: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

scala> a -- Set(1, 3)
val res19: scala.collection.immutable.Set[Int] = Set(2, 4)

scala> a -- List(1, 3)
val res20: scala.collection.immutable.Set[Int] = Set(2, 4)

scala> a -- Array(1, 3)
val res21: scala.collection.immutable.Set[Int] = Set(2, 4)

scala> a -- (1, 3)
                ^
       error: too many arguments (found 2, expected 1) for method --: 
(that: scala.collection.IterableOnce[Int]): scala.collection.immutable.Set[Int]

●集合演算

セットは集合を扱うメソッドや演算子が用意されています。主なメソッドを下表に示します。

表 : セットの集合演算
メソッド	機能
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: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

scala> val b = Set(3, 4, 5, 6)
val b: scala.collection.immutable.Set[Int] = Set(3, 4, 5, 6)

scala> a union b
val res0: scala.collection.immutable.Set[Int] = HashSet(5, 1, 6, 2, 3, 4)

scala> a | b
val res1: scala.collection.immutable.Set[Int] = HashSet(5, 1, 6, 2, 3, 4)

scala> a intersect b
val res2: scala.collection.immutable.Set[Int] = Set(3, 4)

scala> a & b
val res3: scala.collection.immutable.Set[Int] = Set(3, 4)

scala> a diff b
val res4: scala.collection.immutable.Set[Int] = Set(1, 2)

scala> a &~ b
val res5: scala.collection.immutable.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: scala.collection.immutable.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: scala.collection.immutable.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: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

scala> Vector(1, 2, 3, 1, 1, 2, 3, 4).toSet
val res19: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

scala> Array(1, 2, 3, 1, 1, 2, 3, 4).toSet
val res20: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

toList, toVector, toArray などでセットを列に変換することができます。また、列はメソッド toSet でセットに変換することができます。このとき、重複要素が削除されることに注意してください。

●可変 (mutable) なセット

可変 (mutable) なセットは scala.collection.mutable.Set を使います。Set は immutable なセットが使っているので、import で別名を付けるといいでしょう。簡単な例を示します。

scala> import scala.collection.mutable.{Set=>MSet}
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: a.type = HashSet(1, 2, 3, 4, 5, 10)

scala> a += (20, 30, 40)
         ^
       warning: method += in trait Growable is deprecated (since 2.13.0): Use `++=` aka `addAll` 
instead of varargs `+=`; infix operations with an operand of multiple args will be deprecated
val res5: a.type = 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: a.type = 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)
         ^
       warning: method -= in trait Shrinkable is deprecated (since 2.13.3): Use `--=` aka `subtractAll` 
instead of varargs `-=`; infix operations with an operand of multiple args will be deprecated
val res14: a.type = 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: a.type = HashSet(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> a ++= List(10, 11, 12, 13, 14, 15)
val res18: a.type = 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: a.type = HashSet(1, 2, 3, 4, 5, 11, 12, 13, 14, 15)

scala> a --= Set(1, 2, 3, 4, 5)
val res20: a.type = HashSet(11, 12, 13, 14, 15)

●TreeMap と TreeSet

ハッシュ法はデータを高速に探索できる優れたアルゴリズムですが、データの順序はバラバラになるので、たとえばデータの中から最小値や最大値を探すような処理には不向きです。このような場合、順序木を使ってマップやセットを実装すると、最小値や最大値を簡単に求めることができるようになります。Scala には scala.collection.imutable に TreeMap と TreeSet が用意されています。

Scala の場合、TreeMap と TreeSet の実装には「赤黒木 (Red-Black Tree)」という二分木 (平衡木) が使われています。データ数を N とすると、平衡木はデータの挿入、探索、削除を O(log₂ 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}
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) : 49.0 [s]
tak(24, 12, 0)  :  5.8 [s]

実行環境 : Ubunts 18.04 (Windows Subsystem for Linux), 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.262 [s]
ハッシュ表 : 0.033 [s]

Map (ハッシュ表) の場合、引数の値を増やしても高速に実行することができます。ハッシュ法の効果も大変大きいですね。また、同じ計算を再度実行すると、メモ化の働きにより値をすぐに求めることができます。

●参考 URL

COLLECTIONS - Scala Documentation

●プログラムリスト

//
// tarai.scala : たらいまわし関数
//
//               Copyright (C) 2014-2021 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")
  }
}

初版 2014 年 9 月 28 日
改訂 2021 年 3 月 28 日

Scala Programming