

rubyで配列やHashなどのselectやmapなどを繰り返し呼んだ時ループは何回行われるのでしょうか？

例えば下記のコードでは

[code]

    (1..100)
      .select{|val| val % 2 == 0}
      .map{|val| val.to_s}
      .join " "
    
[/code]

行われるループは３回、あるいは１回ループで３つの処理をするのでしょうか？

言語によっては遅延評価をしてループの回数を減らしてくれることもあるのでベンチマークをとって見たのですが、非常に混乱する結果でした。

試したのは下記のベンチです。比較のためeach_with_objectを使った処理も入れて見ました。

[code]

    Benchmark.ips do |x|
      x.report("repeat map") do
        (1..10000)
          .map{|val| val.to_s}
          .map{|val| val.to_i}
          .map{|val| val.to_s}
          .map{|val| val.to_i}
      end
    
      x.report("each_with_object") do
        (1..10000).each_with_object([]) do |val, res|
          val = val.to_s
          val = val.to_i
          val = val.to_s
          val = val.to_i
        end
      end
    
      x.report("repeat each") do
        range = (1..10000)
        range.each do |val|
          val = val.to_s
        end
        range.each do |val|
          val = val.to_i
        end
        range.each do |val|
          val = val.to_s
        end
        range.each do |val|
          val = val.to_i
        end
      end
      x.compare!
    end
    
[/code]

結果はこんな感じです（数が多いほど早いです）。

[code]

          repeat map    140.435  (± 8.5%) i/s -    700.000  in   5.023912s
    each_with_object    176.636  (± 5.1%) i/s -    884.000  in   5.017814s
         repeat each    186.010  (± 5.4%) i/s -    936.000  in   5.048520s
    
[/code]

`repeat map`が繰り返しループされるのかわからないですが、`repeat
each`が`each_with_object`とほぼ変わらないのが解せませんでした。多分、私のテストしたコードになにか問題があるのだと思いますが・・・

配列やHashに対して気軽に、繰り返しselectやreject、mapなどを呼んでも良いのか気になったので投稿しました。

よろしくお願いします。


CC BY-SA 3.0
2017-10-31T15:35:23.193
39186
2017-11-04T10:54:25.437
15048
question
ruby
rubyのselectやmapなどの計算量について


`obj.map{...}.map{...}.map{...}` とした場合は各 `map` が全要素を処理した後に次の `map` に渡します。

Ruby2.0 から `Enumerable#lazy` が導入され、`obj.lazy.map{...}.map{...}.map{...}`
とすることで、要素毎に各 `map` を処理するようになります。

<http://magazine.rubyist.net/?0041-200Special-lazy> が参考になると思います。


CC BY-SA 3.0
2017-11-01T02:09:12.643
39191
2017-11-01T02:09:12.643
3249
39186
answer


Rubyは自動でループの回数を減らすような最適化を行うようなことはなかったはずです。

[code]

    (1..100)
      .select{|val| val % 2 == 0}
      .map{|val| val.to_s}
      .join " "
    
[/code]

は

  1. (1..100)を`select`した配列を生成
  2.     1. の配列に対し`map`した配列を生成
  3.     2. の配列を`join`

という処理になります。

> mapが遅延評価であれば速さの比較が、repeat map ≈ each_with_object > repeat each
> となり、mapが繰り返しループするならeach_with_object > repeat map ≈
> each_with_objectとなると思ったのですが、実際にはrepeat each ≈ each_with_object > repeat
> mapとなりました。repeat mapがrepeat eachよりも明らかに遅い理由がわかりません。

このベンチマークのコードであれば、mapが遅延評価されようがされまいが、基本的な計算量は10000×4です。それ自体に基本的に差は出ません。

ところが、計算自体のコストが低いためにいろいろな影響を受けています。

repeat mapは中間的な他と違い配列の生成が10000要素×4回必要になります。(遅いのはそれとGCに起因するものでしょう。

repeat
eachとeach_with_objectでは、Range#eachが呼ばれループを開始するためのコストが前者が高い一方で、each_with_objectは第二引数への代入処理が発生します。また、行われる処理が異なっています。(to_iのレシーバがIntegerなのかStringなのか）

結局、条件が異なるので何を測定しているのかよくわからないベンチマークになっています。


CC BY-SA 3.0
2017-11-02T02:51:11.633
39235
2017-11-02T02:51:11.633
5793
39186
answer


遅延評価されようがされまいがブロック内の各変換の処理回数が同じです。最終的に全てを処理するのであれば、ブロック内の処理自体回数が減ると言うことはありません。かといって、それ以外の部分の影響を考えるのであれば、より多くのmapを重ねるなど工夫をしないど有意義な差異を見つけることは難しいです。また、最終的な演算結果が同じで無ければ、パフォーマンスが優れているかの比較にはなりません。

以上を踏まえて、ベンチマークを作り直しました。

[code]

    # frozen_string_literal: true
    
    require 'benchmark/ips'
    
    module Convertize
      refine Integer do
        def collatz
          if self.even?
            self / 2
          else
            self * 3 + 1
          end
        end
      end
    end
    using Convertize
    
    MAX_NUM = 10_000
    REPEAT_COUNT = 10
    METHOD = 'collatz'
    
    SCRIPTS = {
      'repeat map' =>
        'list = list' + ".map{|n|n.#{METHOD}}" * REPEAT_COUNT,
      'repeat map!' =>
        'list' + ".map!{|n|n.#{METHOD}}" * REPEAT_COUNT,
      'repeat map lazy' =>
        'list = list.lazy' + ".map{|n|n.#{METHOD}}" * REPEAT_COUNT + '.to_a',
      'repeat map + assign' =>
        "list = list.map{|n|n.#{METHOD}}\n" * REPEAT_COUNT,
      'repeat each + push' =>
        "temp = [];list.each{|n|temp << n.#{METHOD}};list = temp\n" * REPEAT_COUNT,
      'repeat each_index + replace' =>
        "list.each_index{|i|list[i] = list[i].#{METHOD}}\n" * REPEAT_COUNT,
      'one map' =>
        'list = list.map{|n|n' + ".#{METHOD}" * REPEAT_COUNT + '}',
      'one each + push' =>
        'temp = [];list.each{|n|temp << n' + ".#{METHOD}" * REPEAT_COUNT +
        '};list = temp',
      'one each_index + replace' =>
        'list.each_index{|i|list[i] = list[i]' + ".#{METHOD}" * REPEAT_COUNT + '}',
    }.freeze
    
    p SCRIPTS
    
    list = (1..MAX_NUM).to_a
    eval(SCRIPTS['repeat map'])
    EXPECTED_LIST = list.freeze
    
    Benchmark.ips do |x|
      SCRIPTS.each do |name, script|
        x.report(name) do
          list = (1..MAX_NUM).to_a
          eval(script)
          raise unless list == EXPECTED_LIST
        end
      end
      x.compare!
    end
    
[/code]

手元の2.4.2での結果は下記のようになりました。

[code]

    Comparison:
                 one map:      108.6 i/s
         one each + push:      108.6 i/s - same-ish: difference falls within error
    one each_index + replace:      105.9 i/s - same-ish: difference falls within error
             repeat map!:       59.4 i/s - 1.83x  slower
              repeat map:       57.2 i/s - 1.90x  slower
      repeat each + push:       54.0 i/s - 2.01x  slower
    repeat each_index + replace:       49.7 i/s - 2.18x  slower
     repeat map + assign:       47.9 i/s - 2.27x  slower
         repeat map lazy:       38.9 i/s - 2.79x  slower
    
[/code]

ブロック内処理の部分は一応意味があるコラッツ数列の次が作られるようにしています。`MAX_NUM`や`REPEAT_COUNT`を変える事で、配列の大きさやmapを繰り返す数を変更できます。

* * *

では、結果を踏まえた推測をします。

最も速いのは`map`を一回で行う処理(one
map)です。`map`はその処理毎に配列を生成し、要素を埋めていくことになるため、それ自体にそれなりのコストがかかります。`map`を複数回繰り返す処理(repeat
map)では、そのコスト分がのしかかっていると考えらます。

と言いたいところですが、そうであれば配列を生成せずに置き換えていく`map!`を使った処理(repeat
map!)はもうちょっと速くてもいいと思われます。repeat系のその他もさほど変わらないところを見ると、ブロック自体の処理のコストとも考えられます。one系でのブロック呼び出しは`MAX_NUM`ですがrepeat系のブロック呼び出しは`MAX_NUM
* REPEACT_COUNT`と大きく異なりますので、その差分があらわれたとみても良いでしょう。

最後に`lazy`は一番遅いです。これは、最後の配列にする段階で、一つ一つ戻りながら処理をしていくためと考えられます。Arrayの作りなどが通常の正格評価を想定しており、遅延評価でパフォーマンスが出るように作られているわけではないためではないかと推測されます。ただし、配列を全て出さずに最初の1個だけ求めると言った場合は、one
mapの十倍以上の速度をたたき出すことができます。

Rubyの`map`は配列を毎回生成するため遅いという意見もありますが、実用面では十分なほど高速であり、ほとんどの場合は問題になりません。生成コストをなくすために`map!`を使ってもほとんど変わりません。処理を一つにまとめればそれなりの速度向上は望めますが、通常のコードでは微々たるものでしょう。むしろ`lazy`は使い所が限られます。配列を全て求める場合などは逆に遅くなる場合が多いでしょう。全部では無く最初の一部だけ求める場合等以外では使わない方が良いかと思われます。


CC BY-SA 3.0
2017-11-04T10:54:25.437
39288
2017-11-04T10:54:25.437
7347
39186
answer