SetのようなもののRubyでの表現

Ruby

準備その2です．
クラスタ作成時には，クラスタ対象同士の相関値を延々と計算します．
特に階層型クラスタの場合は全ての組み合わせの距離を調べるので，当たり前なのですが，相関値の計算は重いのです．
何とか計算する回数を減らしたい．

やりたいこと

A，Bのピアソン相関値をPearson(A, B)とした場合，Pearson(B, A)も同じ値になります．
ということは，ピアソン相関値をハッシュに格納した場合，(A, B)と(B, A)のキー値を同一にできれば計算は1回で済むことになります．


では，(A, B)と(B, A)のキー値を一致させるにはどうしたらよいのでしょうか．

Setで試してみた

まず思いついたのは，集合を扱うSetライブラリです．
Setでは各要素に順序というものがなく，イケそうな感じがします．

require 'set'

hash = {}
set1 = Set.new ['a', 'b']
set2 = Set.new ['b', 'a']

hash[set1] = 'value'
puts hash[set1]
puts hash[set2]

結果は，

value
nil # キーが異なると見なされ，'value'を参照できない


ダメでした...

Hashのキーとして同一にさせるための条件

そもそも，キー値は何を使って決められているのでしょう．Rubyリファレンスマニュアルによると

キーには任意の種類のオブジェクトを用いることができますが、以下の２つのメソッドが適切に定義してある必要があります。


* Object#hash ハッシュの格納に用いられるハッシュ値の計算
* Object#eql? キーの同一性判定

とあります．


では，このhashとeql?の値を確認してみましょう．

p set1.hash == set2.hash
p set1.eql?(set2)

結果は，

false
false

やはり，このままでは無理そうです．

Arrayを元に実装してみる

先ほど述べたように，hashとeql?の値を同じにできればよいので，自分で実装してみます．
ここではsortしてから元のメソッドに渡すようにしてみました．
今回の条件ではSetを使わずともArrayを元にすればよさそうです．

module My
  class Pair < Array
    def initialize(*args)
      super
      # 引数が何個あっても，最初の2個だけ使ってペアにする
      slice!(2, (size - 2))
    end

    alias_method :original_eql?, :eql?
    alias_method :original_hash, :hash

    def eql?(other)
      sort.original_eql?(other.sort)
    end

    def hash
      sort.original_hash
    end

    alias == eql?
    alias left first
    alias right last
  end
end

動作確認

include My

pair1 = Pair.new ['a', 'b']
pair2 = Pair.new ['b', 'a']

hash[pair1] = 'value'

puts hash[pair1]
puts hash[pair2]
p pair1.hash == pair2.hash
p pair1.eql?(pair2)

実行すると↓のようになります．

value
value
true
true

いい感じですね．

後日談

MacPortsを使うようになってから分かったのですが，ruby 1.8.7以上であればSetでもhashやeql?が一致し，そのまま使えるようです．
気づいた時は結構ショックでした...