From 6e9a088efbe678c93310cb22eb6612434b9f7a09 Mon Sep 17 00:00:00 2001 From: Utkarsh Kukreti Date: Mon, 28 Apr 2014 12:11:40 +0530 Subject: Speed up Array#select! from O(n^2) to O(n). --- mrbgems/mruby-array-ext/mrblib/array.rb | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-) (limited to 'mrbgems/mruby-array-ext/mrblib/array.rb') diff --git a/mrbgems/mruby-array-ext/mrblib/array.rb b/mrbgems/mruby-array-ext/mrblib/array.rb index bddcd8ab8..3a4b1460b 100644 --- a/mrbgems/mruby-array-ext/mrblib/array.rb +++ b/mrbgems/mruby-array-ext/mrblib/array.rb @@ -675,16 +675,11 @@ class Array def select!(&block) return to_enum :select! unless block_given? - idx = 0 - len = self.size - while idx < self.size do - if block.call(self[idx]) - idx += 1 - else - self.delete_at(idx) - end + result = [] + self.each do |x| + result << x if block.call(x) end - return nil if self.size == len - self + return nil if self.size == result.size + self.replace(result) end end -- cgit v1.2.3