以前[『Ruby 基本のき: オブジェクト周りを遊びながら理解する』(5.4節)] (http://qiita.com/yut_h1979/items/aafece7404a1002c0105#54-hash-%E3%81%AE%E3%82%AD%E3%83%BC%E3%81%AB-mutable-%E3%81%AA-string-%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E3%82%82%E5%A4%A7%E4%B8%88%E5%A4%AB%E3%81%AA%E3%81%AE) でこんなことを書きました。
Hash のキーに Array オブジェクトなどを使用した場合はこのようなコピー処置は行われません。
（そんなことをする人はあまりいないと思いますが・・・）
が、最近このアプローチの実装例を見つけて興味深かったので、
使いどころやメリデメなどを自分なりにまとめてみました。
実装例
スプレッドシートを扱う下記ライブラリにおいて、2次元セルの内部データとして
「行番号・列番号の配列をキーとした Hash オブジェクト」が使われています。
実装内容のエッセンスは以下になります。
class Cells
def initialize
@cells = {}
end
def [](row_index, col_index)
@cells[[row_index, col_index]]
end
def []=(row_index, col_index, value)
@cells[[row_index, col_index]] = value
end
end
cells = Cells.new
cells[10, 20] = "foo"
cells[10, 20] # => "foo"
メリデメ
メリット：
- 飛び飛びのデータを効率良く扱える
-
cells[10, 1000] = "foo"; cells[100, 10000] = "bar"としても2要素の追加で済む
-
- 小数点や文字列なども扱える
cells[1.53, 2.01]cells["A", "Z"]
デメリット：
- 2次元配列利用のアプローチに比べてパフォーマンスが悪い（特にデータ量が多くなる場合）
- 配列キーが破壊的に変更されないよう留意する必要がある
- 詳細： [『Ruby 基本のき: オブジェクト周りを遊びながら理解する』(5.4節)（別記事）] (http://qiita.com/yut_h1979/items/aafece7404a1002c0105#54-hash-%E3%81%AE%E3%82%AD%E3%83%BC%E3%81%AB-mutable-%E3%81%AA-string-%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E3%82%82%E5%A4%A7%E4%B8%88%E5%A4%AB%E3%81%AA%E3%81%AE)
どんなデータ構造に使えそうか
- 2次元セルデータ
- プロットデータ（n次元拡張も容易にできそう）
- 地図データ（経度・緯度）
他アプローチとのパフォーマンス比較
以下3パターンについて 1,000 x 1,000 セルの値格納・値参照の処理時間を計測しました。
- ① 配列キーのHashを利用するアプローチ
- ② カンマ区切り文字列キーのHashを利用するアプローチ
- ③ 2次元配列を利用するアプローチ
一番速かったのは「③ 2次元配列を利用するアプローチ」でした。
ちなみに標準ライブラリの Matrix, CSV::Table クラスなどはこのアプローチを使っているようです。
実装スクリプト：
module Cells
# ① 配列キーのHashを利用するアプローチ（クラス名変えて再掲）
class ByHashOfArrayKey
def initialize
@cells = {}
end
def [](row_index, col_index)
@cells[[row_index, col_index]]
end
def []=(row_index, col_index, value)
@cells[[row_index, col_index]] = value
end
end
# ② カンマ区切り文字列キーのHashを利用するアプローチ
class ByHashOfStringKey
def initialize
@cells = {}
end
def [](row_index, col_index)
@cells["#{row_index},#{col_index}"]
end
def []=(row_index, col_index, value)
@cells["#{row_index},#{col_index}"] = value
end
end
# ③ 2次元配列を利用するアプローチ
class By2DArray
def initialize
@cells = []
end
def [](row_index, col_index)
(@cells[row_index] ||= [])[col_index]
end
def []=(row_index, col_index, value)
(@cells[row_index] ||= [])[col_index] = value
end
end
end
測定スクリプト：
require 'benchmark'
def fill_up_cells(cells, row_size, col_size, value)
(1..row_size).each do |r|
(1..col_size).each do |c|
cells[r, c] = value
end
end
end
def look_up_cells(cells, row_size, col_size)
(1..row_size).each do |r|
(1..col_size).each do |c|
cells[r, c]
end
end
end
Benchmark.bm(25) do |x|
cells_1 = Cells::ByHashOfArrayKey.new
cells_2 = Cells::ByHashOfStringKey.new
cells_3 = Cells::By2DArray.new
[cells_1, cells_2, cells_3].each do |cells|
x.report(cells.class.name) { fill_up_cells(cells, 1_000, 1_000, true) }
end
[cells_1, cells_2, cells_3].each do |cells|
x.report(cells.class.name) { look_up_cells(cells, 1_000, 1_000) }
end
end
測定結果：
- OS X Yosemite 10.10.3
- 2.6 GHz Intel Core i5
- 8 GB 1600 MHz DDR3
- ruby 2.2.2p95 (2015-04-13 revision 50295)
user system total real
Cells::ByHashOfArrayKey 1.280000 0.030000 1.310000 ( 1.312445)
Cells::ByHashOfStringKey 1.290000 0.050000 1.340000 ( 1.346375)
Cells::By2DArray 0.130000 0.000000 0.130000 ( 0.133934)
user system total real
Cells::ByHashOfArrayKey 1.280000 0.010000 1.290000 ( 1.292671)
Cells::ByHashOfStringKey 0.990000 0.030000 1.020000 ( 1.029152)
Cells::By2DArray 0.110000 0.000000 0.110000 ( 0.103042)
まとめ
「Hash のキーに配列を利用するアプローチ」の使いどころやメリデメなどを書きました。
google_drive や roo での活用例を知るまでこのアプローチは悪手だと思っていましたが、
パフォーマンスや配列キーの破壊的変更などに留意した上で使うのは悪くないかもと思いました。