Remove multiple array elements by indices

Question

I prepared a method to make possible to select elements of the array except for some indexes.

def array_except(array, *indexes)
 indexes = 
 indexes
 .flat_map { |e| e.is_a?(Range) ? e.to_a : e }
 .map { |e| e.negative? ? e + array.length : e }
 array.values_at(*((0...array.length).to_a - indexes))
end

It works in such a way:

> a = ["a", "b", "c", "d", "e", "f", "g", "h"]
array_except(a, 1, -1, 2..3, -4..-2)
=> ["a"]
> array_except(a, 1, 2)
=> ["a", "d", "e", "f", "g", "h"]
> array_except(a, -2..-1)
=> ["a", "b", "c", "d", "e", "f"]

I feel like it might be done with a lower level of complexity. I spent a day playing with #each_with_object([]) but can't find the proper way. Maybe someone has any thoughts?

• Sᴀᴍ Onᴇᴌᴀ: Welcome to Code Review! Please see What to do when someone answers. I have rolled back Rev 5 → 3

Answer 1

The main concern with this implementation is not its complexity but the fact that you transform ranges into arrays of indices. It works fine for basic cases, but what if the range is huge? For example,

array_except(a, 1..100000000)

works with the significant delay on my laptop already, and infinite range will obviously cause your implementation to never terminate.

But you don't need to iterate over all the numbers within the range to check if the index belongs to it, right? It's enough to just check the boundaries. So, my suggestion is

def array_except(array, *indexes)
 array.reject.with_index do |_, i|
 indexes.any? do |index|
 index.is_a?(Range) ? index.cover?(i) : index == i
 end
 end
end
pry(main)> array_except(a, 1..Float::INFINITY) # => ["a"]

UPD. Please, note: it doesn't work with the negative ranges as is, but can be adjusted if you decide to go in this direction - for example, via converting ranges with the negative boundaries into "equivalent" ones with the proper positive boundaries:

def array_except(array, *indexes)
 array.reject.with_index do |_, i|
 indexes.any? do |index|
 if index.is_a?(Range)
 start = index.begin > 0 ? index.begin : array.length + index.begin
 stop = index.end > 0 ? index.end : array.length + index.end
 start <= i && i <= stop 
 else
 index == i
 end
 end
 end
end

The final version is more verbose than your initial implementation, but its performance doesn't depend on the size of the ranges provided as an input...

UPD2. If you don't care about the predictable performance and is just interested in a concise implementation, it can be made as short as

def array_except(array, *indexes)
 array.reject.with_index { |_, i| indexes.any? { |ind| Array(ind).include?(i) } }
end

UPD3. Good point raised in the comment. The second implementation works terribly bad in the cases when indexes parameter is a huge list of something (integers or ranges) applied to a large list. In this case we get stuck with O(m*n)... To beat this we need something more sophisticated. For example, we can first iterate over all indexes and fill some auxiliary data structure (with O(1) read access) with some "flags" (defining what to keep/delete) and then iterate over the array itself and clean it up. Very dirty implementation:

def array_except4(array, *indexes)
 to_delete = Array.new(array.size)
 indexes.each do |index|
 case index
 when Range
 start, stop = [index.begin, index.end].sort
 start = start < 0 ? [0, start + array.length].max : [start, array.length - 1].min
 stop = stop < 0 ? [stop + array.length, array.length - 1].min : [stop, array.length - 1].min
 (start..stop).each { |k| to_delete[k] = true }
 else
 to_delete[index] = true
 end
 end
 array.reject.with_index { |_, i| to_delete[i] }
end
```

• Alex Holubenko: The main problem that your suggestions is cool for big ranges but a bit slow for a big amount of indices :( You can check UPD
• Konstantin Strukov: Yeah, good point. Updated the answer too.