Scala 2.8 コレクション API -- 集合

集合

集合 (Set) は要素の重複の無い Iterable だ。集合一般に定義される演算は次の表にまとめてあり、可変集合に関してはその次の表も見てほしい。これらの演算は以下のカテゴリーに分類される:

条件演算である contains, apply, subsetOf。contains メソッドは集合が任意の要素を含むかを調べる。集合での apply メソッドは contains と同じであるため、set(elem) は set contains elem と同じだ。これは集合が要素を含んでいれば true を返す関数として使えることを意味する。例えば、

val fruit = Set("apple", "orange", "peach", "banana")

fruit: scala.collection.immutable.Set[java.lang.String]

Set(apple, orange, peach, banana)

scala> fruit("peach")

res0: Boolean = true

scala> fruit("potato")

res1: Boolean = false

加算である + と ++ は、単一もしくは複数の要素を集合に追加し、新たな集合を返す。

減算である - は -- は、単一もしくは複数の要素を集合から削除し、新たな集合を返す。

集合演算である和集合、積集合、および差集合。これらの演算には文字形とシンボル形の二つの形がある。文字バージョンは intersect、union、および diff で、シンボルバージョンは &、|、と &~ だ。Set が Traversable から継承する ++ は union と | の更なる別名だと考えることができるが、++ は Traversable の引数を取るが、union と | は集合を取る。

`Set` トレイトの演算
使用例	振る舞い
条件演算:
`xs` `contains` `x`	`xs` が `x` を含むかを調べる。
`xs(x)`	`xs` `contains` `x` に同じ。
`xs` `subsetOf` `ys`	`xs` が `ys` の部分集合であるかを調べる。
加算:
`xs` `+` `x`	`xs`内の全ての要素および `x` を含んだ集合。
`xs` `+` `(x,` `y,` `z)`	`xs`内の全ての要素および渡された要素を含んだ集合。
`xs ++ ys`	`xs`内の全ての要素と `ys`内の全ての要素を含んだ集合。
減算:
`xs` `-` `x`	`x` を除き、`xs`内の全ての要素を含んだ集合。
`xs` `-` `(x,` `y,` `z)`	渡された要素を除き、`xs`内の全ての要素を含んだ集合。
`xs -- ys`	`ys`内の要素を除き、`xs`内の全ての要素を含んだ集合。
`xs.empty`	`xs` と同じクラスの空集合。
集合演算:
`x` `&` `ys`	`xs` と `ys` の積集合。
`xs` `intersect` `ys`	`xs` `&` `ys` に同じ。
`x` `\|` `ys`	`xs` と `ys` の和集合。
`xs` `union` `ys`	`xs` `\|` `ys` に同じ。
`x` `&~` `ys`	`xs` と `ys` の差集合。
`xs` `diff` `ys`	`xs` `&~` `ys` に同じ。

Set トレイトの演算

使用例

振る舞い

条件演算:

xs contains x

xs が x を含むかを調べる。

xs(x)

xs contains x に同じ。

xs subsetOf ys

xs が ys の部分集合であるかを調べる。

加算:

xs + x

xs内の全ての要素および x を含んだ集合。

xs + (x, y, z)

xs内の全ての要素および渡された要素を含んだ集合。

xs ++ ys

xs内の全ての要素と ys内の全ての要素を含んだ集合。

減算:

xs - x

x を除き、xs内の全ての要素を含んだ集合。

xs - (x, y, z)

渡された要素を除き、xs内の全ての要素を含んだ集合。

xs -- ys

ys内の要素を除き、xs内の全ての要素を含んだ集合。

xs.empty

xs と同じクラスの空集合。

集合演算:

x & ys

xs と ys の積集合。

xs intersect ys

xs & ys に同じ。

x | ys

xs と ys の和集合。

xs union ys

xs | ys に同じ。

x &~ ys

xs と ys の差集合。

xs diff ys

xs &~ ys に同じ。

可変集合は、この表にまとめてあるとおり、加算、減算、更新演算などの新たなメソッドを追加する。

`mutable.Set` トレイトの演算
使用例	振る舞い
加算:
`xs` `+=` `x`	集合 `xs` に副作用として要素 `x` を加え、`xs`自身を返す。
`xs` `+=` `(x,` `y,` `z)`	集合 `xs` に副作用として渡された要素を加え、`xs`自身を返す。
`xs` `++=` `ys`	集合 `xs` に副作用として `ys`内の全ての要素を加え、`xs`自身を返す。
`xs` `add` `x`	集合 `xs` に要素 `x` を加え、以前に集合に含まれていなければ `true` を返し、既に含まれていれば `false` を返す。
減算:
`xs` `-=` `x`	集合 `xs` から副作用として要素 `x` を削除して、`xs`自身を返す。
`xs` `-=` `(x,` `y,` `z)`	集合 `xs` から副作用として渡された要素を削除して、`xs`自身を返す。
`xs` `--=` `ys`	集合 `xs` から副作用として `ys`内の全ての要素を削除して、`xs`自身を返す。
`xs` `remove` `x`	集合 `xs` から要素 `x` を削除、以前に集合に含まれていれば `true` を返し、含まれていなければ `false` を返す。
`xs` `retain` `p`	`xs`内の要素で条件関数 `p` を満たすものだけを残す。
`xs.clear()`	`xs` から全ての要素を削除する。
更新演算:
`xs(x)` `=` `b`	(展開した場合、`xs.update(x,` `b)`)。ブーリアン値の引数 `b` が `true` ならば `xs` に `x` を加え、それ以外なら `xs` から `x` を削除する。
クローン演算:
`xs.clone`	`xs` と同じ要素を持つ新しい可変集合。

mutable.Set トレイトの演算

使用例

振る舞い

加算:

xs += x

集合 xs に副作用として要素 x を加え、xs自身を返す。

xs += (x, y, z)

集合 xs に副作用として渡された要素を加え、xs自身を返す。

xs ++= ys

集合 xs に副作用として ys内の全ての要素を加え、xs自身を返す。

xs add x

集合 xs に要素 x を加え、以前に集合に含まれていなければ true を返し、既に含まれていれば false を返す。

減算:

xs -= x

集合 xs から副作用として要素 x を削除して、xs自身を返す。

xs -= (x, y, z)

集合 xs から副作用として渡された要素を削除して、xs自身を返す。

xs --= ys

集合 xs から副作用として ys内の全ての要素を削除して、xs自身を返す。

xs remove x

集合 xs から要素 x を削除、以前に集合に含まれていれば true を返し、含まれていなければ false を返す。

xs retain p

xs内の要素で条件関数 p を満たすものだけを残す。

xs.clear()

xs から全ての要素を削除する。

更新演算:

xs(x) = b

(展開した場合、xs.update(x, b))。ブーリアン値の引数 b が true ならば xs に x を加え、それ以外なら xs から x を削除する。

クローン演算:

xs.clone

xs と同じ要素を持つ新しい可変集合。

不変集合と同様に、可変集合も要素追加のための + と ++ 演算、および要素削除のための - と -- 演算を提供する。しかし、これらは集合をコピーする必要があるため可変集合ではあまり使われることがない。可変集合はより効率的な += と -= という更新方法を提供する。s += elem という演算は、集合 s に副作用として elem を集合に加え、変化した集合そのものを戻り値として返す。同様に、s -= elem は集合から elem を削除して、変化した集合を戻り値として返す。+= と -= の他にも、traversable やイテレータの全ての要素を追加または削除する一括演算である ++= と --= がある。

メソッド名として += や -= が選ばれていることによって、非常に似たコードが可変集合と不変集合のどちらでも動くことを意味する。不変集合 s を使った次の REPL のやりとりを見てほしい:

scala> var s = Set(1, 2, 3)

s: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

scala> s += 4

scala> s -= 2

scala> s

res2: scala.collection.immutable.Set[Int] = Set(1, 3, 4)

ここでは immutable.Set型の var に対して += と -= を使った。s += 4 のようなステートメントは、s = s + 4 の略だ。つまり、これは集合 s に対して追加メソッドの + を呼び出して、結果を変数 s に代入しなおしてる。次に、可変集合でのやりとりを見てほしい。

scala> val s = collection.mutable.Set(1, 2, 3)

s: scala.collection.mutable.Set[Int] = Set(1, 2, 3)

scala> s += 4

res3: s.type = Set(1, 4, 2, 3)

scala> s -= 2

res4: s.type = Set(1, 4, 3)

結果は前回のやりとりと非常に似通ったものになった: Set(1, 2, 3) から始めて、最後に Set(1, 3, 4) を得た。ステートメントは前回と同じに見えるが、実際には違うことを行っている。 s += 4 は今度は可変集合 s の += メソッドを呼び出し、その場で集合を上書きしているのだ。同様に、s -= 2 は同じ集合の -= メソッドを呼び出している。

この二つのやりとりの比較から重要な原則を導き出せる。val に格納された可変コレクションと、var に格納された不変コレクションは、大抵の場合にお互いを置換できるということだ。これはコレクションに対して上書きで更新されたのか新たなコレクションが作成されたのかを第三者が観測できるような別名の参照がない限り成り立つ原則だ。

可変集合は += と -= の別形として add と remove を提供する。違いは add と remove は集合に対して演算の効果があったかどうかを示す Boolean の戻り値を返すことだ。

現在。可変集合のデフォルトの実装では要素を格納するのにハッシュテーブルを使っている。不変集合のデフォルトの実装は集合の要素数に応じて方法を変えている。空集合はシングルトンで表される。サイズが 4つまでの集合は全要素をフィールドとして持つオブジェクトとして表される。それを超えたサイズの不変集合はハッシュトライとして表される。

このような設計方針のため、(例えば 4以下の) 小さいサイズの集合を使う場合は、通常の場合、可変集合に比べて不変集合の方が、よりコンパクトで効率的だ。集合のサイズが小さいと思われる場合は、不変集合を試してみてはいかがだろうか。

集合のサブトレイトとして SortedSet と BitSet の二つがある。これは別のページで解説されている。

続いては、