Golang Project Structure

Tips and tricks for writing and structuring Go code

Removing Elements From a Slice

Language

  • unknown

by

I’ve written in the past about how to reverse the order of all the elements in a slice, but today I’m going to discuss some of the ways that elements can be removed — in other words, deleted — from a slice in Go.

A notepad next to scrunched up balls of paper, symbolizing data that is no longer needed.
Modern computers may have huge amounts of memory, but sometimes it’s wise to delete data that’s no longer needed, especially when we’re grouping the data together in arrays or slices in order to structure it or do some processing on it.

When looking at the various ways to remove one or more elements from a slice, we will compare the elegance and performance of the example code, since some operations will always be inherently more expensive than others, which means that our code will take longer to run with certain approaches than with others.

The Easiest Way to Remove an Element From a Slice

The simplest and most idiomatic way to remove an element from a slice is shown below:

package main

import "fmt"

func removeElementByIndex[T any](slice []T, index int) []T {
	return append(slice[:index], slice[index+1:]...)
}

func main() {
	values := []int{2, 4, 7, 11, 19, 20, 21, 24, 25}

	values = removeElementByIndex(values, 4)

	fmt.Println(values) // [2 4 7 11 20 21 24 25]
}

This is elegant and easy to understand, because we’re basically shrinking the original slice, reducing its length to the point just before element that we want to remove, and then appending all of the elements after the element we want to remove (if, indeed, there are any) to that newly shrunk slice.

However, since this involves moving all of the elements that come after the index of the removed element, it can be quite a costly operation, especially if you have a very large slice that contains lots of data. It is also much more costly if you’re removing an element from the beginning of a large slice than from the end of one.

Of course, in order to use the removeElementByIndex function, as its name suggests, you need to know the index of the element that you want to remove, but you can find that by making use of a simple function like the one below (or using slices.IndexFunc from an experimental package created by the Go team):

package main

import "fmt"

func findIndex[T any](slice []T, matchFunc func(T) bool) int {
	for index, element := range slice {
		if matchFunc(element) {
			return index
		}
	}

	return -1 // not found
}

func main() {
	values := []int{2, 4, 7, 11, 19, 20, 21, 24, 25}

	index := findIndex(values, func(n int) bool {
		return n == 19
	})

	fmt.Println(index) // 4

	index = findIndex(values, func(n int) bool {
		return n == 100
	})

	fmt.Println(index) // -1
}

In the example above, when we call the findIndex function initially, it tells us that index 4 contains the integer 19 (which is the element we removed in our previous example).

However, when we try searching for the integer 100, we get the result -1, meaning that it cannot be found in our slice. Every valid index will always be a positive integer (although they use the int, rather than uint, type), so -1 is traditionally used to signify an invalid index.

Note that the removeElementByIndex and findIndex functions that we’ve written above use the generic syntax that was recently introduced in version 1.18 of Go. If you don’t like generics, however, you can very easily rewrite the functions to take a specific type.

Improving Efficiency Without Preserving Order

There is, however, a more efficient way to write the removeElementByIndex function, so long as you don’t need to preserve the order of the remaining elements in the slice:

func removeElementByIndex[T any](slice []T, index int) []T {
	sliceLen := len(slice)
	sliceLastIndex := sliceLen - 1

	if index != sliceLastIndex {
		slice[index] = slice[sliceLastIndex]
	}

	return slice[:sliceLastIndex]
}

This works by swapping the last element in the slice with the one that is to be removed and then simply shrinking the size of the slice by one.

The fact that the order isn’t preserved can be a very real drawback, but it may not always pose a problem, even if you do need the slice to remain ordered, so long as you have some way to restore the ordering yourself.

If, for example, you have slice of integers that is already sorted in ascending order, you can use this function to remove one or more numbers, and then you can call the sort.Ints function from the Golang standard library in order to restore the ordering that was lost. Despite the added overhead of performing a sort after the removal, there may well be cases (depending on various factors such as the size of your slice and how many elements you want to remove) when this turns out to be a reasonably efficient way of mutating the slice.

Note that neither of the two version of the removeElementByIndex function we’ve created does any bounds checking, so if our slice does not actually contain the index that we’re trying to remove, the code will panic.

Performing a Benchmark

I told you above that the second version of our removeElementByIndex function would be significantly more performant than the first one. It’s easy to understand why this would be the case, since it doesn’t need to move all of the elements that come after the one removed as our first version did, but I think it’s still worth performing a benchmark to make sure that our intuition is correct.

In order to do that, I’ve created a file containing the two different implementations of our removeElementByIndex function, so that we can fairly test them against each other:

remove.go

package remove

func removeElementByIndexOne(slice []int, index int) []int {
	return append(slice[:index], slice[index+1:]...)
}

func removeElementByIndexTwo(slice []int, index int) []int {
	sliceLen := len(slice)
	sliceLastIndex := sliceLen - 1

	if index != sliceLastIndex {
		slice[index] = slice[sliceLastIndex]
	}

	return slice[:sliceLastIndex]
}

Now we can create two benchmark functions in a test file that simply run each of our implementations as many times as they can in a given period, always removing a single element from a slice that we instantiate on each iteration of the loop:

remove_test.go

package remove

import "testing"

func BenchmarkRemoveElementByIndexOne(b *testing.B) {
	for i := 0; i < b.N; i++ {
		var numbers = []int{5, 3, 99, -4, 2, -1, 9, 0, 6}

		numbers = removeElementByIndexOne(numbers, 7)
	}
}

func BenchmarkRemoveElementByIndexTwo(b *testing.B) {
	for i := 0; i < b.N; i++ {
		var numbers = []int{5, 3, 99, -4, 2, -1, 9, 0, 6}

		numbers = removeElementByIndexTwo(numbers, 7)
	}
}

To run these benchmarks, you can use the command below (the -bench flag takes a regular expression that matches the names of both test functions):

go test -bench="RemoveElementByIndex(?:One|Two)$"

On my machine, this produces the following output:

goos: windows
goarch: amd64
pkg: example.com
cpu: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
BenchmarkRemoveElementByIndexOne-16     583365337                2.036 ns/op
BenchmarkRemoveElementByIndexTwo-16     1000000000               0.2262 ns/op
PASS
ok      example.com     1.830s

As you can see, the second implementation is almost ten times as fast as the first, taking only a fifth of a nanosecond to run, as opposed to two whole nanoseconds. A nanosecond is a billionth — in other words, a thousand-millionth — of a second, so both of those times may seem incredibly small, but when you’re performing a very large number of operations or working with huge datasets, those small differences can soon add up and become much more noticeable.

In my opinion, unless there’s a strong reason to select another solution, it’s always best to choose the one that tends to be more efficient, especially when they’re both relatively simple to implement.

Removing Many Elements From a Slice

We can now build on the best of the two removeElementByIndex functions that we created above in order to create another function that can handle the removal of many indices (the plural of index) at once:

package main

import "fmt"

func removeElementByIndex[T any](slice []T, index int, indicesMap map[int]int) []T {
	sliceLen := len(slice)
	sliceLastIndex := sliceLen - 1

	if index != sliceLastIndex {
		slice[index] = slice[sliceLastIndex]
		indicesMap[sliceLastIndex] = indicesMap[index]
	}

	return slice[:sliceLastIndex]
}

func removeManyElementsByIndices[T any](slice []T, indices []int) []T {
	indicesMap := make(map[int]int)

	for _, index := range indices {
		indicesMap[index] = index
	}

	outputSlice := slice

	for _, index := range indices {
		mappedIndex := indicesMap[index]

		if mappedIndex < 0 || mappedIndex >= len(outputSlice) {
			continue
		}

		outputSlice = removeElementByIndex(outputSlice, indicesMap[index], indicesMap)
	}

	return outputSlice
}

func main() {
	values := []int{2, 4, 7, 11, 19, 20, 21, 24, 25}

	values = removeManyElementsByIndices(values, []int{0, 1, 3, 7})

	fmt.Println(values) // [25 20 7 21 19]
}

You may think that it would be as simple as iterating through each index and calling the function that handles the removal of each index on each iteration. However, it’s more complicated than that, because every time we remove an element at an index, we change the order of the remaining elements in the slice, as we discussed above. This means that the indices that the function is iterating through may no longer contain the original elements that we intended to delete.

In the example above, we have solved this problem by creating a map of our indices before we iterate through them (at this point, the key and value both contain the initial index). Then in the removeElementByIndex function, when we move an element from the last index to the index that used to contain the element that we no longer want to retain, we now set the key of the map to the element’s initial index and the value to the index that the element has moved to.

This allows us to do a simple lookup in future iterations, converting the index that we had originally been given to the one where the element that it used to contain has subsequently moved.

If we didn’t do this, we could end up not removing the correct elements or, worse, causing the code to panic when an index is given that is larger than the slice that gets shrunk every time an element is removed.

There is now also a simple validation check included, when we iterate through each index, making sure that it is at least zero and less than the slice’s length, so that we don’t try to remove any indices that don’t exist, which, as we mentioned earlier, would cause our function to panic.

A Slightly More Elegant Way to Remove Elements From a Slice

Given that we are shrinking the slice every time that we remove an element, it seems reasonable to assume that maybe we could create a single function that does the same work but only shrinks the slice once after all elements have been removed. This is what we have below:

package main

import "fmt"

func removeManyElementsByIndices[T any](slice []T, indices []int) []T {
	indicesMap := make(map[int]int)

	for _, index := range indices {
		indicesMap[index] = index
	}

	lastIndex := len(slice) - 1
	backIndex := lastIndex

	for _, index := range indices {
		if index < 0 || index > lastIndex {
			continue
		}

		mappedIndex := indicesMap[index]

		if mappedIndex == -1 {
			continue
		}

		if mappedIndex != backIndex {
			slice[mappedIndex] = slice[backIndex]

			indicesMap[backIndex] = indicesMap[mappedIndex]
		}

		indicesMap[index] = -1

		backIndex--
	}

	return slice[:backIndex+1]
}

func main() {
	values := []int{2, 4, 7, 11, 19, 20, 21, 24, 25}

	values = removeManyElementsByIndices(values, []int{0, 1, 3, 7})

	fmt.Println(values) // [25 20 7 21 19]
}

We store the final index of the slice in the backIndex variable, then we decrement it on every iteration of the loop where we remove an element. We can then infer that we need to shrink the size of the slice to backIndex+1 (since the length is always one greater than the last index), which we do before we return the slice to the caller.

The only other significant difference between this implementation of the removeManyElementsByIndices function and the previous one is that we set the index of the removed element to -1 in the indicesMap, which allows us to ignore an index if we have already handled it (i.e. if the slice of indices contains the same index more than once, which there is no good reason why it should).

Creating a Filter Function

Sometimes you know exactly which indices, or elements, you want to remove, but there are many other times when you simply know what kind of elements ought to be removed (i.e. elements that fail a given test, known as a predicate).

We can now use the removeManyElementsByIndices function to create another higher-level function that will make it even easier for us to get rid of the elements that we no longer want:

package main

import "fmt"

func removeManyElementsByIndices[T any](slice []T, indices []int) []T

func filter[T any](slice []T, predicate func(T) bool) []T {
	indices := make([]int, 0, len(slice))

	for index, element := range slice {
		if !predicate(element) {
			indices = append(indices, index)
		}
	}

	return removeManyElementsByIndices(slice, indices)
}

func main() {
	values := []int{2, 4, 7, 11, 19, 20, 21, 24, 25}

	values = filter(values, func(n int) bool {
		return n%2 == 0
	})

	fmt.Println(values) // [2 4 20 24]
}

You can see how the predicate function returns true if the element it is passed is an even number (i.e. is divisible by two with no remainder), and since we remove all elements that fail the predicate’s test, that means that we will remove all of the odd numbers from the slice. If you run the code, you will see that that’s exactly what happens.

Within the filter function, I have initialized the indices slice to have a capacity as large as the length of the input slice that we are filtering. This means that even if every element fails the predicate and every index needs to be removed, the indices slice will already be large enough to contain every index without any memory having to be reallocated.

Clearing a Slice

Of course, if you already know that you definitely do need to remove every element from a slice, without needing to run the predicate to make sure, you can simply clear the slice yourself by using the following line:

slice = slice[:0]

This will reduce the length of the slice to zero and remove all elements, making sure that you can no longer access them. It is interesting to note, however, that it won’t garbage-collect the removed elements, since the capacity of the slice will remain the same and all elements up to the capacity will still exist in memory, just no longer accessible.

You can see for yourself that its capacity will remain larger than its length (unless the capacity was zero to begin with):

package main

import "fmt"

func main() {
	slice := []int{2, 4, 7, 11, 19, 20, 21, 24, 25}

	slice = slice[:0]

	fmt.Println(len(slice)) // 0
	fmt.Println(cap(slice)) // 9
}

Another way to clear a slice that will actually remove its elements from memory is simply to set it to nil, like so:

slice = nil

fmt.Println(len(slice)) // 0
fmt.Println(cap(slice)) // 0

Filtering by Appending to a New Slice

Finally, we can create another implementation of our filter function that is even simpler (since it no longer needs to call the removeManyElementsByIndices function) and, if you plan to remove a large number of elements, potentially much more performant:

package main

import "fmt"

func filter[T any](slice []T, predicate func(T) bool) []T {
	result := make([]T, 0, len(slice))

	for _, element := range slice {
		if predicate(element) {
			result = append(result, element)
		}
	}

	return result
}

func main() {
	values := []int{2, 4, 7, 11, 19, 20, 21, 24, 25}

	values = filter(values, func(n int) bool {
		return n%2 == 0
	})

	fmt.Println(values) // [2 4 20 24]
}

The code above shows that sometimes the easiest way to remove elements from a slice involves a little lateral thinking: don’t bother getting rid of all the elements you no longer want, but rather create a new slice and only append the elements that you actually do want to keep. In effect, you’ll end up with much the same result.

If you have a very large slice and are only going to remove one or two elements, however, this implementation of the filter function may be less performant than the previous one, since it will need to re-append almost every element of the slice, rather than just removing the indices that are no longer needed.

This shows the importance of taking the context of code into account when judging its performance: a function that may be more efficient at handling certain inputs can suddenly become less efficient when given very different inputs.

Of course, if you’re ever in doubt, you can always run a benchmark, just as we did above!

Leave a Reply

Your email address will not be published.