4.3 BinaryHash(二分探索を利用した連想配列)
はじめに
たぶん、この記事は間違った感じのことを書いてると思います。
というわけで、参考にしないでください。
連想配列
連想配列、あるいはハッシュとは配列の一種である。通常の配列がインデックスナンバーを用いてデータにアクセスするのに対し、連想配列では自ら設定した文字列等（keyと呼ぶ）でデータ（valueと呼ぶ）にアクセスする。
連想配列の非効率的なところ
irb(main):001:0> test = {"a" => 4}
=> {"a"=>4}
irb(main):002:0> test["c"] = 6
=> 6
irb(main):003:0> test["b"] = 1
=> 1
irb(main):004:0> test
=> {"a"=>4, "c"=>6, "b"=>1}連想配列への値の追加は必ず末尾になっている。つまり、アクセス時間は線形オーダーなのである。
これは非効率的ではないか？と思った。通常のデータなら十分な速さだが、今回はコンちゃんに認識させる形態素群を連想配列に突っ込みたいので、アクセス時間を爆速にしたい。
BinaryHash
というわけで、keyで昇順ソートして二分探索によってアクセスを行う連想配列、BinaryHashクラスを作った。
アクセス時間は対数オーダーになる。爆速である。
# -*- coding: utf-8 -*- # アクセスの速い連想配列 class BinaryHash def initialize() @data = [] # [key, value]の昇順で格納されていく @length = 0 # @dataの大きさ。@data.lengthでも良いんだけど処理を爆速にしたい… end # データを初期化する def clear() @data = [] @length = 0 end # データサイズを返す def length() return @length end # keyに値をセットする def set!(key, value) # dataのmin_indexからmax_indexまでを探索(二分探索) def _set!(key, value, min_index, max_index) index = (min_index + max_index).div(2) if @length == 0 push!(key, value, 0) else if @data[index][0] == key @data[index][1] = value elsif min_index == max_index if @data[index][0] < key push!(key, value, index + 1) else push!(key, value, index) end elsif @data[index][0] < key _set!(key, value, index + 1, max_index) else _set!(key, value, min_index, index) end end end _set!(key, value, 0, @length - 1) return @data end # @data[index]にペアを突っ込む def push!(key, value, index) @data.push([nil,nil]) # とりあえず空のペアを突っ込んどく @length += 1 # indexより後ろ(index含む)を1つ後ろにずらし、indexに挿入 i = @length - 1 while i > index @data[i] = @data[i - 1] i -= 1 end @data[index] = [key, value] end # keyに対応するvalueを返す def get(key) # dataのmin_indexからmax_indexまでを探索(二分探索) def _get(key, min_index, max_index) index = (min_index + max_index).div(2) if @length == 0 return nil else if @data[index][0] == key return @data[index][1] elsif min_index == max_index return nil elsif @data[index][0] < key _get(key, index + 1, max_index) else _get(key, min_index, index) end end end return _get(key, 0, @length - 1) end # keyに対応するvalueをadd_valueだけ増やす def add!(key, add_value) # dataのmin_indexからmax_indexまでを探索(二分探索) def _add!(key, add_value, min_index, max_index) index = (min_index + max_index).div(2) if @length == 0 set!(key, add_value) else if @data[index][0] == key @data[index][1] += add_value elsif min_index == max_index set!(key, add_value) elsif @data[index][0] < key _add!(key, add_value, index + 1, max_index) else _add!(key, add_value, min_index, index) end end end _add!(key, add_value, 0, @length - 1) return @data end end =begin #test test = BinaryHash.new puts "set!のテスト" p test.set!("Alice", 5) p test.set!("Chris", 1244) p test.set!("Bob", 531) p test.set!("Chris", 111) p test.set!("Bobby", 135) p test.set!("Debid", 114514) p test.set!("Alan", 4545) puts "\ngetのテスト" p test.get("Alan") p test.get("Alice") p test.get("Bob") p test.get("Bobby") p test.get("Chris") p test.get("Debid") p test.get("Joker") puts "\nadd!のテスト" p test.add!("Alan", 5) p test.add!("Alice", -10) p test.add!("Bob", 469) p test.add!("Bobby", -135) p test.add!("Chris", 111) p test.add!("Debid", 114514) p test.add!("Ack", 1) p test.add!("Joker", 13) p test.add!("Cachy", 999999999999999) =end
テストコードの実行結果は以下の通り。
set!のテスト [["Alice", 5]] [["Alice", 5], ["Chris", 1244]] [["Alice", 5], ["Bob", 531], ["Chris", 1244]] [["Alice", 5], ["Bob", 531], ["Chris", 111]] [["Alice", 5], ["Bob", 531], ["Bobby", 135], ["Chris", 111]] [["Alice", 5], ["Bob", 531], ["Bobby", 135], ["Chris", 111], ["Debid", 114514]] [["Alan", 4545], ["Alice", 5], ["Bob", 531], ["Bobby", 135], ["Chris", 111], ["Debid", 114514]] getのテスト 4545 5 531 135 111 114514 nil add!のテスト [["Alan", 4550], ["Alice", 5], ["Bob", 531], ["Bobby", 135], ["Chris", 111], ["Debid", 114514]] [["Alan", 4550], ["Alice", -5], ["Bob", 531], ["Bobby", 135], ["Chris", 111], ["Debid", 114514]] [["Alan", 4550], ["Alice", -5], ["Bob", 1000], ["Bobby", 135], ["Chris", 111], ["Debid", 114514]] [["Alan", 4550], ["Alice", -5], ["Bob", 1000], ["Bobby", 0], ["Chris", 111], ["Debid", 114514]] [["Alan", 4550], ["Alice", -5], ["Bob", 1000], ["Bobby", 0], ["Chris", 222], ["Debid", 114514]] [["Alan", 4550], ["Alice", -5], ["Bob", 1000], ["Bobby", 0], ["Chris", 222], ["Debid", 229028]] [["Ack", 1], ["Alan", 4550], ["Alice", -5], ["Bob", 1000], ["Bobby", 0], ["Chris", 222], ["Debid", 229028]] [["Ack", 1], ["Alan", 4550], ["Alice", -5], ["Bob", 1000], ["Bobby", 0], ["Chris", 222], ["Debid", 229028], ["Joker", 13]] [["Ack", 1], ["Alan", 4550], ["Alice", -5], ["Bob", 1000], ["Bobby", 0], ["Cachy", 999999999999999], ["Chris", 222], ["Debid", 229028], ["Joker", 13]]
