Help us understand the problem. What is going on with this article?

Hash のキーに配列を利用するアプローチ

More than 3 years have passed since last update.

以前『Ruby 基本のき: オブジェクト周りを遊びながら理解する』(5.4節) でこんなことを書きました。

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次元セルデータ
  • プロットデータ(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)
1,000x1,000セルの値格納
                                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)
1,000x1,000セルの値参照
                                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_driveroo での活用例を知るまでこのアプローチは悪手だと思っていましたが、
パフォーマンスや配列キーの破壊的変更などに留意した上で使うのは悪くないかもと思いました。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away