Removing specific items from a slice

Question

Given a slice of unknown length (potentially very small or very large), and another slice containing (unique) integers indicating indices to be removed from that slice, the most straight forward way to achieve this would be to sort the indices in reverse order then remove each of them from the slice in turn via:

mySlice = append(mySlice[:i], mySlice[i+1:]...)

Alternatively I could create a new empty slice like:

newSlice = make([]*Whatever, 0, len(mySlice)-len(indices))

And build it up like:

sort.Ints(indices)
nextIndex := 0
for i, thing := range mySlice {
    if nextIndex == len(indices) || i == indices[nextIndex] {
        nextIndex++
    } else {
        newSlice = append(newSlice, mySlice[i])     
    }
}

I haven't benchmarked these yet, because I would rather understand why one would be faster than the other (and possibly under what conditions).

In particular, what actually happens in memory to the slice in the first strategy? I understand that slices are simple abstractions over arrays which are contiguous blocks of memory, but does removing the middle item of a slice require that memory to be moved around, such that it would be quicker to manage copying over every second item to a new slice/array than to remove every second item from the original slice?

Answer 1

You are using the builtin append() function, you can read its documentation what it does.

In summary, if the destination slice has enough capacity (cap()) to accomodate the elements you're appending to it, no new array will be allocated, but the destination slice will be resliced and the elements will be copied there.

If the destination slice does not have enough capacity, a new array will be allocated, and the current content of the destination slice will be copied into that, and the elements you're appended will follow. A slice referring to the newly allocated array will be returned.

In your case since you're removing elements, the slice will always have enough capacity, so no new array will be allocated. But still, the elements after the element/index being removed has to be copied forward by 1. In case of big slices this will be relatively much work. And it has to be as many times as many elements/indices you want to remove.

Your implementation does not work though. It causes a run-time panic if the removable indices slice does not contain the last index of the input slice, because your code increments nextIndex beyond len(indices) and indexes it like indices[nextIndex]. To make it work, you should use the following if:

if nextIndex < len(indices) && i == indices[nextIndex] {

Also it is much faster to allocate the new slice with len = len(input) - len(ind) than with len = 0 as you did; and use simple assignment to append 1 element instead of calling the built-in append() function:

s2 := make([]int, len(s)-len(idx))

sort.Ints(idx)
nexti, j := 0, 0
for i := range s {
    if nexti < len(idx) && i == idx[nexti] {
        nexti++
    } else {
        s2[j] = s[i]
        j++
    }
}

Next note that we don't need a new slice, we can do the removal "in-place", in the input slice:

sort.Ints(idx)
nexti, j := 0, 0
for i := range s {
    if nexti < len(idx) && i == idx[nexti] {
        nexti++
    } else {
        s[j] = s[i]
        j++
    }
}

s = s[:len(s)-len(idx)]

And as the final, fastest solution:

We will use the original slice, and we will not copy elements 1-by-1. Elements between the removable indices form a contigous part which we can copy in one step using the built-in copy() function. Note that the first part (before the first removable index) is already in place, we don't even have to copy that.

func remove4(s, idx []int) []int {
    if len(idx) == 0 {
        return s
    }
    sort.Ints(idx)

    prev := idx[0]
    for i := 1; i < len(idx); i++ {
        v := idx[i]
        copy(s[prev-i+1:], s[prev+1:v])
        prev = v
    }
    copy(s[prev-len(idx)+1:], s[prev+1:])

    return s[:len(s)-len(idx)]
}

Try all the examples on the Go Playground.

One final note:

By excluding certain elements from a slice by reslicing it, the underlying array will still contain reference to them, the value will remain in memory. It is recommended that whenever an element removed from a slice, always zero its place in the underlying array (its respective element in the slice) so the value will not remain in memory needlessly. This becomes even more critical if your slice contains pointers to big data structures.

In my example I used int, so no need to zero it.

As an easy example: if you want to remove the last element of a slice:

var s []*SomeType

// Remove last element, but first zero its value:
s[len(s)-1] = nil
s = s[:len(s)-1]