prima materia - diary : Set が Ruby にはないという話, 3月のライオン

過去の日記

<< 2008/03/ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 >>

2008-03-16

■Set が Ruby にはないという話 [java][Ruby]

Rails' Wiki - Rails勉強会＠東北第9回

に参加してでてきた話。

Ruby使いの人
「Java の Set って何?」
「Java の Set にあたるものって Ruby では何? と聞かれて分からなかった*1」

Java使いの人
「あぁ、Set って確かにあまり使わないなぁ」
「っていうか Map つまり連想配列のキーの部分と変わらないし」

私
「Set には実装として HashSet と TreeSet があるから、Set は抽象レベルの話で、Java では実装が選べるから……」

Java使いの人
「やっぱり結局ハッシュのキーの部分ってことでいいんじゃ?」

私
「いや、連想配列のことを俗にハッシュって言っているけど、それはイコールじゃないし。あぁ、説明できない〜。っていうか忘れてる〜」

となったのでその話。

import java.util.*;

public class Test {

    public static void main(String[] args) {
        Set s = new HashSet();
        s.add("a");
        s.add("b");
        s.add("c");
        s.add("b");
        s.add("c");
        s.add("d");

        System.out.println(s.size());

        Iterator iter = s.iterator();

        while (iter.hasNext()) {
            System.out.println(iter.next());
        }

    }
}

実行すると、

4
d
b
c
a

こんな感じ。
s の中身は4つ。"b"を2回、"c"を2回 add しているけど、Set の性質である"重複を許さない"ためにそうなる。

重複要素のないコレクションです。すなわち、セットは、e1.equals(e2) である e1 と e2 の要素ペアは持たず、null 要素を最大 1 つしか持ちません。その名前が示すように、このインタフェースは、数学で言う集合の抽象化をモデル化します。
Java 2 Platform SE 1.3: インタフェース Set

ということ。

さて、上のソースでは interface Set の具象クラスとして HashSet を利用したのだけど、これを TreeSet にしてみる。

        Set s = new TreeSet();

に変更するだけ。
実行結果はこう。

4
a
b
c
d

つまりソートされた状態を保持するわけだ。
iterator で中身を全部吐き出す時や、first, last メソッドがその様に振る舞う。

Set を実装するにあたって"重複を許さない"という性質をどのようにするか? 逆に言うと"重複があるかどうかを調べる"にはどうするか? ということ。
単純に頭から重複があるか探していったら O(n) のオーダになってしまいます*2。

で、Java で最初から用意されている方法がハッシュを使う方法と、ツリーを使う方法。ってそのままカタカナに直しただけに見えますな。
後者は、赤黒木を使って、ソートされた状態を保った平衡二分木でデータを保持します。

前者は……全くややこしいことですが、ハッシュ=連想配列と考えている人が多いので困ります。

初期のJavaの実装では、まず11個の配列を用意しています。
add するオブジェクトの hashCode() メソッドを呼び、その11の剰余でそれぞれの配列に分配していきます。
なぜ11かというと、

あまり配列が小さくて大きくても効率が悪い
Object#hashCode はメモリアドレスを返す仕様になっているので、4や8の倍数になると予想される。その倍数や約数の配列を用意すると、全部の配列にうまくまんべんなく入ってくれない*3ので都合が悪い。

という感じで、適当に小さくも大きくもない素数として選ばれたんではなかろうか、と私は思う(きっと情報工学の初期にこういうことを研究した人がいて、ちゃんと論文もあるんだろうなぁ、とは思う。いや数論の分野かな?)

Javaでもあとのバージョンになると単純な剰余ではなくなり(計算時間を気にした? とも思えないけど、効率がよくなかったんだろうなぁ)、上の様な簡単な話にはならない。
でも、ある数の配列を用意して、それにうまく分散して格納していくことで、重複のチェックにかかる時間を 1/(配列の数) あたりまで減らすことができる、という考えは一緒。

本題はここから。 < おい

Ruby になんで Set にあたるものが無いかというと、連想配列(Ruby でいうと Hash クラス)のキーの部分だけ見ると同じ機構を持っているからなんだろう。

s = {}

s['a']=nil
s['b']=nil
s['c']=nil
s['b']=nil
s['c']=nil
s['d']=nil

p s.size #=>4
p s.has_key?('a') #=>true
s.each_key {|key|
  p key
}

でいいわけで。

で、オチなんだけど、実はJavaも、古いバージョンの TreeSet の実装って中に TreeMap を持っているだけだったと記憶しているんだよね(今確かめる気はないけど)。
なんだよ、じゃ Set なんて要らないじゃん? とか思わなくもない。
けど、きっと Collection という一連のユーティリティとして、あった方が"完璧"つまり"キズが無い"ってことを重視したのではないかと。

そしてもちろん、抽象概念としての Set とその実装を分離することで、アルゴリズムやデータ構造に対して意識を向けさせられる。
私としてはそっちの方に大きな意味を感じるのだけど、開発の現場では結局あまり意識されない、というのもきっと事実。

(で、連想配列=ハッシュという勘違いが広がるんだよ)
(最近でこそハッシュに、"大きなデータストリームの同一性のチェック"という利用価値が出て来たけどな。それを除けば、ハッシュといえば連想配列に使われる、ってことでいいんじゃね?)