How to efficiently remove elements from a slice in Go?

php editor Apple introduces you how to efficiently delete elements from slices in Go. In the Go language, deleting elements in a slice is a common operation. However, due to the characteristics of slices, directly deleting an element may cause the length of the slice to change, thus affecting subsequent operations. In order to efficiently delete elements in a slice, we can use the characteristics of the slice and some built-in functions to achieve this. Several commonly used methods will be introduced in detail below.

Question content

There are multiple ways to delete slice elements. But what if I have an application that does a lot of processing of slices? Go slices are well optimized for adding new elements, but is there an efficient way to remove elements from a slice (not only for speed, but also memory optimized).

I'm aware of the slices.Delete function introduced in Go 1.21, but behind the scenes it uses the following well-known techniques:

return append(s[:i], s[j:]...)

It looks like the underlying array is not reduced in this case. This is great for speed, but what if we have a lot of elements (like 100k or 1M) and then reduce them to very few (like only 10)? It looks like there are no memory optimizations like those used to increase slice capacity.

When we don't need to preserve the order of elements in a slice, we can use the following method (go to playground link):

func sliceDel[S ~[]E, E any](s S, i, j int) S {
    lastIdx := len(s) - (j - i)
    copy(s[i:], s[lastIdx:])
    return s[:lastIdx]
}

This is useful when we have a large slice and a small number of elements to remove (the idea behind it is to copy a small number of slice elements).

Regarding memory, the capacity is the same in both cases and will not be reduced. For example:

// Reduce slice almost to zero
    for i := 0; i < sliceSize/2-1; i++ {
        sl = sliceDel(sl, 0, 2)
    }
    fmt.Printf("len = %d, cap = %d", len(sl), cap(sl))
        // Output: len = 2, cap = 100000

    // Reduce slice almost to zero
    for i := 0; i < sliceSize/2-1; i++ {
        sl = slices.Delete(sl, 0, 2)
    }
    fmt.Printf("len = %d, cap = %d", len(sl), cap(sl))
        // Output: len = 2, cap = 100000

So, is there any way to optimize memory usage? For example, if the length of a slice is less than half its capacity, reduce the capacity by half.

I would also like to know how to do this efficiently, for example a technique like this s[:len(s):len(s)] (full slice expression used by slices.Clip) does not would reduce the underlying array - it only holds the new capacity in the slice structure to avoid overwriting the parent slice element when appending a new element to a child slice (as mentioned in this proposal).

Solution

There is no "generally best" solution. You show multiple approaches in your question, each approach may be better than the others for a specific scenario.

If you encounter a situation like this, when you want to keep a few elements out of many, don't even start removing those elements. Build a new slice with these elements. In addition to being faster, this definitely solves the memory issue as well.

You cannot reduce memory usage by using full slice expressions other than allocating and using new slices. As long as there is a reference to the backing array, it will not shrink (at least not in current versions of Go). If you encounter a situation where a large backing array is allocated but only a small portion of it is used, you can allocate a new slice and manually copy the elements to allow the large array to be garbage collected.

Also consider that if you have a large slice that you may need to remove many elements from, a slice may not be the best data structure to use. For example, you could try using a linked list, or you could even try a map: deleting elements from a linked list or a map will be much faster, and a map will also provide a fast (O(n)) lookup time, as shown below Bar.

The above is the detailed content of How to efficiently remove elements from a slice in Go?. For more information, please follow other related articles on the PHP Chinese website!