Issue #7268 has been updated by kouya (taifu kouya).

Assignee set to kouya (taifu kouya)

Array#select!ではO(n)で、Array#reject!ではO(n^2)であることをruby versionごとに確認して、一言追加しておく@RrubyHiroba2013
----------------------------------------
Feature #7268: Array#select!とArray#reject!の計算量の違いについて

https://bugs.ruby-lang.org/issues/7268#change-39613

Author: grafi (Shunsuke Shimizu)
Status: Open
Priority: Normal
Assignee: kouya (taifu kouya)
Category: 
Target version: 
reporter: 
ruby_version: 


Array#select!はブロックを評価した結果が真になる要素を配列の先頭側に寄せていって最後に配列を縮める実装となっているのに対し、Array#reject!ではブロックが評価した結果が真になる要素が見つかる度にそれを削除して配列を更新しているために、nの長さの配列に対する計算量がArray#select!ではO(n)で、Array#reject!ではO(n^2)となっています。

サンプル

require 'benchmark'
  a = (0..100000).to_a
  b = (0..100000).to_a
  Benchmark.bm do |x|
  x.report {a.reject!{|i|i&0 == 0}}
  x.report {b.select!{|i|i&0 != 0}}
end

この挙動はドキュメントに載っているのを見つけられませんでしたが、明らかに対称に思える二つの操作が計算量で違うというのはハマる人がいそうなので、ドキュメントに一言記載している方が良いように思えます。

なお、Array#reject!がこのような実装になっているのは、 ruby-trunk:#2545 で議論されているように、ブロック内でbreakで呼ばれたときに配列が壊れた状態にならないようにするためだと思われます。Array#select!はこのような実装になっていないのは、rejectは条件に合うような要素を配列から一つ一つ取り除いていくイメージなのでbreakしても壊れない方が自然で、selectは条件にあうような要素だけを集めた配列に置き換えるイメージなので途中でbreakしたら壊れてもまあ許せる、といったことから生じた非対称性でしょうか。



-- 
http://bugs.ruby-lang.org/

--
ML: ruby-reference-manual@m...
Info: http://QuickML.com/