3 ms·
xg15's comment still makes sense if you replace "copy all ..." with "slide the remaining elements down by the number of removed elements" to match the mutative
by brandonbloom 10y ago
xg15's comment still makes sense if you replace "copy all ..." with "slide the remaining elements down by the number of removed elements" to match the mutative behavior.
However, a bigger problem is concurrent modification: What happens if your reject! predicate has a side effect which modifies the array? Ideally you'd receive a "ConcurrentModificationException" or the like.
- leereeves 10y agoThat would still require O(n) space (to store the list of elements to keep or remove) so why not simply use the regular `reject` ?
- brandonbloom 10y agoBecause you're saving the O(N) time copy... iirc, Ruby's array doesn't expose the distinction between length and capacity, but internally it may decide to amortize the cost of such copies. For example, if reject only removes a small % of elements, it may choose not to shrink capacity.
- leereeves 10y agoYou're not saving the O(N) time copy, just replacing it with an O(N) slide. (That's assuming you copy at all, instead of simply updating the reference.)
- brandonbloom 10y agoI meant O(N) space, as you said "That would still require O(n) space" - but a slide does not require additional space.
- junke 10y agoNo, before sliding elements, you set a local variable "dirty" to true. You iterate over all elements and keep the ones that are not rejected by moving them at the end of the current max index. When you code finishes normally, dirty is set to false. You have an "ensure" block (finally) protecting the code which handles the cases where dirty is true (moving all the remaining elements after the current max). Then you truncate the array.