Speed up Array#select! from O(n^2) to O(n).
authorUtkarsh Kukreti <[email protected]>
Mon, 28 Apr 2014 06:41:40 +0000 (28 12:11 +0530)
committerUtkarsh Kukreti <[email protected]>
Mon, 28 Apr 2014 06:44:15 +0000 (28 12:14 +0530)
mrbgems/mruby-array-ext/mrblib/array.rb

index bddcd8a..3a4b146 100644 (file)
@@ -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