[ruby-list:46383] Re: 最も低コストの方法は？

From: Tetsuo Sakaguchi <[e-mail]>
Subject: [ruby-list:46382] Re: 最も低コストの方法は？
Date: Sat, 12 Sep 2009 15:37:11 +0900

> all?, any? どちらもブロックを与えられるので、それを使えば
> 一発じゃないですか？
> 例えば、{ | x | x.empty? } とか。
> (参考: http://doc.okkez.net/static/187/class/Enumerable.html)

その通りです。
しかし、Rubyのブロックはコストがでかいです。
全要素が nil であるかどうかを判定するのにブロックを使う場合と使わない場合を比較してみます。
高速化したければ、適切なアルゴリズム（メソッド）とデータ構造（nilが使えるなら使え）を選べということです。

# -*- coding: euc-jp -*-
require 'benchmark'
Benchmark.bm(15) do |b|         # 全要素がnil
  # 全要素を走査するので時間がかかる
  ary = Array.new(100000, nil)
  ary.all? {|x| x == nil }      # => true
  ary.none?                     # => true
  b.report("with block")    { ary.all? {|x| x == nil } }
  b.report("without block") { ary.none? }
end
Benchmark.bm(15) do |b|         # 1つの要素が非nil
  # 途中で処理が打ち切られる
  ary = Array.new(100000, nil); ary[550] = "a"
  ary.all? {|x| x == nil }      # => false
  ary.none?                     # => false
  b.report("with block")    { ary.all? {|x| x == nil } }
  b.report("without block") { ary.none? }
end
RUBY_VERSION                    # => "1.9.2"
# >>                      user     system      total        real
# >> with block       0.040000   0.000000   0.040000 (  0.036237)
# >> without block    0.000000   0.000000   0.000000 (  0.005338)
# >>                      user     system      total        real
# >> with block       0.000000   0.000000   0.000000 (  0.000228)
# >> without block    0.000000   0.000000   0.000000 (  0.000043)

RUBY_VERSION                    # => "1.8.8"
# >>                      user     system      total        real
# >> with block       0.110000   0.000000   0.110000 (  0.113428)
# >> without block    0.030000   0.000000   0.030000 (  0.027634)
# >>                      user     system      total        real
# >> with block       0.000000   0.000000   0.000000 (  0.000443)
# >> without block    0.000000   0.000000   0.000000 (  0.000126)

--
rubikitch
Blog: http://d.hatena.ne.jp/rubikitch/
Site: http://www.rubyist.net/~rubikitch/
Twit: http://twitter.com/rubikitch/
『Ruby逆引きハンドブック』 http://d.hatena.ne.jp/rubikitch/20090525/rubybook