mruby/mruby — pull request #2146 by utkarshkukreti (2014-04-28 06:48:56+00:00)
Title: Speed up Array#select! from O(n^2) to O(n).

Before:

```
$ cat select_bang.rb
array = []

200000.times { |i| array << i }

array.select! do |i|
i % 2 == 0
end

p array.size

$ time bin/mruby select_bang.rb
100000
bin/mruby select_bang.rb 16.74s user 0.04s system 99% cpu 16.846 total

$ time ruby select_bang.rb
100000
ruby select_bang.rb 0.11s user 0.01s system 98% cpu 0.125 total
```

After:

```
$ time bin/mruby select_bang.rb
100000
bin/mruby select_bang.rb 0.16s user 0.00s system 98% cpu 0.167 total
```

I was going to apply the same algorithm for `Array#reject!`, but apparently that cannot be done because the array needs to be updated after every block call according to the [docs](http://www.ruby-doc.org/core-2.1.1/Array.html#method-i-reject-21), so that would have to remain O(n^2) to comply with CRuby.