ある属性に紐付いたkeyからある属性に紐付いたvalueを、O(1)で参照するデータ構造

なにこれ

Hash使ってると「valueからkeyを参照したい…」と思うことがあって、

h.find{|k,v| v == hoge }[0]

とか書いたらできるのですが、これは計算量O(N)であるという欠点があって、要素数が多くなってくると性能が落ちていきます。
なので要素数の増加に強く、キー→値の一方通行ではなく双方向、しかも複数の属性を行き来できるようなデータ構造があるといいなと。

Example

f = HashFrame.new

# キーを登録（予め登録されていないキーを参照するとエラーになる
f.regist("fruit", "price")

# 項目の挿入
docs = [
  {"fruit" => "apple" , "price" => 200}, 
  {"fruit" => "orange", "price" => 140},
]
f.set(*docs)

# オレンジ(果物) の 値段 を参照
f.get "price", of: [ "fruit", "orange" ] # => 140

# オレンジ(果物) を含む項目を削除
f.delete "fruit", "orange"

# 既存の項目を更新: りんご(果物) について 1980円(値段) にする
f.attach ["price", 1980], to: ["fruit", "apple"]

コード

属性の値を全部HashのキーとしてやればO(1)できるんじゃないか、という安直な発想で作ってみました。挿入では値を2次元配列上にマッピングして、値を参照する際には、Hashによってその番地を特定します。

ユルい実装でなんとかするため、キーを登録制としています。
インターフェースを磨きあげれば使い物になるかも。

# O(1)で属性間のアクセス
class HashFrame
  def initialize(*reg_keys)
    @reg_keys = reg_keys
    @key_index = reg_keys.map.with_index{|k, i| [k,i] }.to_h
    @table  = []
    @cur_index = reg_keys.map{|k| [k,{}] }.to_h
  end

  # 項目の挿入
  def set(*documents)
    checks = [
      documents.all? {|d| (d.keys & @reg_keys).size == d.keys.size },
      @reg_keys.all? {|key| (documents.map{|d| d[key] } & values(key)).empty? },
    ]
    raise "Invalid document Error" unless checks.all?

    documents.each do |doc|
      a = @reg_keys.map{|k| doc[k] }
      cursor = ( @table << a ).size - 1
      doc.each{|k, v| @cur_index[k][v] = cursor }
    end

    true
  end

  # 項目の更新
  def attach( v = [ 'v-key', 'v-value' ], to: [ 'k-key', 'k-value' ] )
    raise 'Unregistered Key Error' unless ( @reg_keys & [ v[0], to[0] ] ).size == 2

    i = @cur_index[to[0]][to[1]]
    j = @key_index[v[0]]

    @cur_index[v[0]][v[1]] = i
    @table[i][j] = v[1]

    true
  end

  # 値の参照
  def get( target_key, of: [ 'k-key', 'k-value' ] )
    raise 'Unregistered Key Error' unless ( @reg_keys & [ target_key, of[0] ] ).size == 2

    i = @cur_index[of[0]][of[1]]
    j = @key_index[target_key]

    @table[i][j]
  end

  # 該当要素を含む項目を削除
  def delete(kkey, kval)
    raise 'Unregistered Key Error' unless @reg_keys.include?(kkey)

    i = @cur_index[kkey][kval]
    @table[i] = []

    true
  end

  # キーを登録（予め登録されていないキーを参照するとエラーになる
  def regist(*keys)
    raise 'Key Already exist Error' unless (@reg_keys & keys).empty?

    keys.each do |key|
      @reg_keys << key
      @key_index[key] = @key_index.size
      @cur_index[key] = {}
    end

    true
  end

  def table
    [ @reg_keys, *@table.reject(&:empty?) ]
  end

  def size
    @table.count{|a| !a.empty? }
  end

  def keys
    @reg_keys
  end

  def values(key)
    i = @key_index[key]
    @table.reject(&:empty?).map{|a| a[i] }
  end
end