RubyのSet#include? で効率化

項目18 要素が含まれているかどうかの処理を効率よく行うために集合を使うことを検討しよう

先ずはArray

Array#include? は計算量がO(n) 。

class Role
  def initialize(name, permissions)
    @name, @permissions = name, permissions
  end

  def can?(permission)
    @permissions.include?(permission)
  end
end

Hashを使うと高速化できる

メモリを消費するが、要素へのアクセスはO(log n)。
ハッシュの値はtrueを使うとイミュータブルなグローバル変数となり効率的。

class Role
  def initialize(name, permissions)
    @name = name
    @permissions = Hash[permissions.map { |p| [p, true] } ]
  end

  def can?(permission)
    @permissions.include?(permission)
  end
end

ただし、注意点としては、重複が失われることと、配列をHash化するためにさらに大きな配列を作成していること。#can? の効率化を図ったが、結果 #initialize のコストが増加しているので #can? の呼び出し回数が少なければ効果は少ない。

そこでSetですよ

Hashの例はかっこが多くて見にくい。そしてHashの特別な機能を使っているわけではない。
SetクラスはHashに要素を格納するので、Hashと同等のパフォーマンスが出る。

require "set"

class Role
  def initialize(name, permissions)
    @name, @permissions = name, Set.new(permissions)
  end

  def can?(permission)
    @permissions.include?(permission)
  end
end

覚えておくべき事項

  • 要素が含まれているかどうかの高速チェックではSetを使うことを検討しよう
  • Setに挿入されるオブジェクトは、ハッシュキーとしても使えなければならない。

nil、スカラーオブジェクトを配列に変換するには、Arrayメソッドを使おう

これ知らなかった。 こんな感じで配列を引数にとる場合、「配列」、「nil」、「引数1個」を一括で処理したいと思うことがあると思う。こんな時にこれを解決する方法があった。
これは使っていこう。

Effective Ruby

Effective Ruby

項目17 nilスカラーオブジェクトを配列に変換するには、Arrayメソッドを使おう

以下のコードをベースに説明。

class Pizza
  def initialize(toppings)
    toppings.each do |topping|
      add_and_price_topping(topping)
    end
  end
end

可変長引数

本書でも紹介されているが、引数を可変長引数に変えるというアプローチで対応していたのだけど、これだと、*を使う必要がある。また、受け付けた引数を配列に変換し、何を操作しているのかはっきりわかる方がいいとのこと。

class Pizza
  # 可変長引数を展開
  def initialize(*toppings)
    toppings.each do |topping|
      add_and_price_topping(topping)
    end
  end
end

# こうすると、以下に対応できる。
Pizza.new("cheeze", "bacon")
Pizza.new("cheeze")
Pizza.new(nil)

解決方法:Kernel#Array

Kernel#Array知らんかったわ。
to_aryを先に試して、to_aをそのあと試すとのこと。

> ? Kernel#Array

From: object.c (C Method):
Owner: Kernel
Visibility: private
Signature: Array(arg1)
Number of lines: 14

Returns arg as an Array.

First tries to call to_ary on arg, then to_a.
If arg does not respond to to_ary or to_a,
returns an Array of length 1 containing arg.

If to_ary or to_a returns something other than
an Array, raises a TypeError.

   Array(["a", "b"])  #=> ["a", "b"]
   Array(1..5)        #=> [1, 2, 3, 4, 5]
   Array(key: :value) #=> [[:key, :value]]
   Array(nil)         #=> []
   Array(1)           #=> [1]

例。

>> Array("Betelgeuse")
=> ["Betelgeuse"]

>> Array(nil)
=> []

>> Array(["Nadroj", "Retep"])
=> ["Nadroj", "Retep"]

# Hashは問題となる可能性がある
>> Array(a: 20)
=> [[:a, 20]]

最初のコードを変更すると

class Pizza
  def initialize(toppings)
    # これだけ
    Array(toppings).each do |topping|
      add_and_price_topping(topping)
    end
  end
end

# 以下に対応できる
Pizza.new(["cheeze", "bacon"])
Pizza.new("cheeze")
Pizza.new(nil)

# 以下はNG
# だが、引数の意味が分かりやすくなる
Pizza.new("cheeze", "bacon")

覚えておくべき事項

  • nilスカラーオブジェクトを配列に変換するには、Arrayメソッドを使う。
  • ArrayメソッドにHashを渡してはならない。Hashは一連のネストされた配列に変換されてしまう。

 

余談:to_aryとto_a

さらっと流されていたが、to_aryto_aの違いは暗黙的または暗黙的な変換かどうかという違い。*による引数展開は明示的変換。
ruby - What's the difference between to_a and to_ary? - Stack Overflow

Rubyのコレクション書き換え時の注意点

これも嵌りがちな内容。
コレクションのコピーについて。

Effective Ruby

Effective Ruby

項目16 コレクションを書き換える前に引数として渡すコレクションのコピーを作っておこう

ラジオのTunerを例に。

class Tuner
  def initialize(presets)
    @presets = presets
    clean
  end

  private
    def clean
      # 末尾が奇数のみを抽出
      @presets.delete_if { |f| f[-1].to_i.even? }
    end
end

>> presets = %w(90.1 106.2 88.5)
>> tuner = Tuner.new(presets)

# 書き換えられちゃった!
>> presets
=> ["90.1", "88.5"]

改善案(reject

Array#delete_if でなく Array#reject を使えば良い。
でも、どっかで書き換えられるかもしれない。

改善案(clone/dup

コピーすれば良い。
cloneはオブジェクトの状態(freezeと特メソッド)を残す。
dupは残さない。
大抵の場合はdupで良い。

class Tuner
  def initialize(presets)
    @presets = presets.dup
    clean
  end
end

コピー時の注意点

dup/cloneはシャロー(shallow)コピーを返す。
コレクションクラスの場合、コンテナのコピーは作られるが、要素のコピーは作られない。

>> a = ["Polar"]
>> b = a.dup << "Bear"
=> ["Polar", "Bear"]

>> b.each { |x| x.sub!("lar", "oh") }
=> ["Pooh", "Bear"]

# 書き換えられてる
>> a
=> ["Pooh"]

deepコピーが欲しい場合

Marashalを使えば手軽にできるが、メモリも食うし、Marshalみ対応していないオブジェクト(IO、Fileなど)もあるので要注意。

>> a = ["Polar"]
>> b = Marshal.load(Marshal.dump(a)) << "Bear"
=> ["Polar", "Bear"]

>> b.each { |x| x.sub!("lar", "oh") }
=> ["Pooh", "Bear"]

# 書き換えられていない!
>> a
=> ["Polar"]

覚えておくべき事項

  • Rubyのメソッド引数は値渡しではなく参照渡しである。ただし、この規則には、Fixnumオブジェクトという顕著な例外がある。
  • 引数として渡されたコレクションは、書き換える前にコピーを作ろう。
  • dup、cloneメソッドは、シャローコピーしか作らない。
  • ほとんどのオブジェクトでは、Marshalを使えば必要な時にディープコピーを作れる。