title: [Reprint] Tips on Slice Operations
date: 2021-08-11 10:47:54
comment: false
toc: true
category:
- Golang
tags: - Reprint
- Go
- Slice
- Operations
This article is a reprint from: [Translation] Tips on Slice Operations | Li Wen Zhou's Blog
This article is translated from the official wiki and summarizes some tips on slice operations in the Go language.
Note: Due to the need for writing, there may be some differences in details compared to the original text.
Common Techniques for Slice Operations#
Copying#
Copy the elements from slice a to slice b.
The simplest and most commonly used method is to use the built-in copy function.
b = make([]T, len(a)) // Allocate enough memory at once
copy(b, a)
In addition to using the built-in copy function, there are two other methods to copy a slice using the append function.
b = append([]T(nil), a...)
b = append(a[:0:0], a...)
These two methods are usually slower than using the copy function to copy a slice, but if there are more elements to be added to b after copying, they will be more efficient.
Slicing#
Cut out the elements from index i to j in slice a.
You can use the append function to accomplish this as follows.
a = append(a[:i], a[j:]...)
Deletion#
Delete the element at index i in slice a.
You can also use the append function in the same way as slicing to accomplish the deletion.
a = append(a[:i], a[i+1:]...)
Or use the copy function with slice expressions to accomplish the deletion.
a = a[:i+copy(a[i:], a[i+1:])]
In addition, if you only need to delete the element at index i without preserving the original order of the slice elements, you can use the following simple method to delete.
a[i] = a[len(a)-1] // Move the last element to index i
a = a[:len(a)-1] // Truncate the last element
Memory Leaks Caused by Slicing or Deletion Operations#
It should be noted that if the elements in slice a are of pointer type or contain pointer fields in a struct type (which need to be garbage collected), the example code for slicing and deletion mentioned above may cause a potential memory leak problem: some elements with values are still referenced by slice a and cannot be collected by the garbage collection mechanism. The following code can solve this problem.
Slicing#
copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k < n; k++ {
a[k] = nil // or the zero value of type T
}
a = a[:len(a)-j+i]
Deletion#
copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of type T
a = a[:len(a)-1]
Deletion without Preserving the Original Order of Elements#
a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]
Internal Expansion#
Expand j elements after index i in slice a.
Use two append functions to accomplish this, that is, first append the elements after index i to a slice with a length of j, and then append all the elements in this slice after index i in slice a.
a = append(a[:i], append(make([]T, j), a[i:]...)...)
The expanded part of the elements is the zero value of type T.
Tail Expansion#
Expand the space of j elements at the end of slice a.
a = append(a, make([]T, j)...)
The expanded part of the elements is also the zero value of type T.
Filtering#
Filter the elements in slice a in place according to certain rules.
Assuming that the filtering condition is encapsulated as the keep function, use a for range loop to iterate through all the elements in slice a and call the keep function one by one for filtering.
n := 0
for _, x := range a {
if keep(x) {
a[n] = x // Keep this element
n++
}
}
a = a[:n] // Truncate the slice to keep the elements
Insertion#
Insert element x at index i in slice a.
Use two append functions to accomplish the insertion of x.
a = append(a[:i], append([]T{x}, a[i:]...)...)
The second append function creates a new slice with its own underlying array and copies the elements in a[i:] to this slice, and then the first append function copies these elements back to slice a.
We can avoid creating a new slice (and the resulting memory garbage) and the second copy by using another method:
a = append(a, 0 /* Use the zero value of the element type here */)
copy(a[i+1:], a[i:])
a[i] = x
Appending#
Append element x to the end of slice a.
Simply use the append function here.
a = append(a, x)
Popping#
Pop the last element of slice a.
Use slice expressions to accomplish this.
x, a = a[len(a)-1], a[:len(a)-1]
Pop the first element of slice a.
x, a = a[0], a[1:]
Prepending#
Prepend element x to the beginning of slice a.
a = append([]T{x}, a...)
Other Techniques#
Filtering without Allocating Memory#
This technique relies on the fact that slice b shares the same underlying array and capacity as the original slice a, so the original storage space is reused for the filtered slice. Of course, the content of the original slice is modified.
b := a[:0]
for _, x := range a {
if f(x) {
b = append(b, x)
}
}
For elements that need to be garbage collected, the following code can be added after the above operation:
for i := len(b); i < len(a); i++ {
a[i] = nil // or the zero value of type T
}
Reversing#
Reverse the order of elements in slice a.
This is done by iterating and swapping elements pairwise.
for i := len(a)/2-1; i >= 0; i-- {
opp := len(a)-1-i
a[i], a[opp] = a[opp], a[i]
}
The same operation can be done as follows:
for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {
a[left], a[right] = a[right], a[left]
}
Shuffling#
Shuffle the order of elements in slice a.
Fisher-Yates algorithm:
for i := len(a) - 1; i > 0; i-- {
j := rand.Intn(i + 1)
a[i], a[j] = a[j], a[i]
}
Starting from go1.10, you can use math/rand.Shuffle.
rand.Shuffle(len(a), func(i, j int) {
a[i], a[j] = a[j], a[i]
})
Batch Processing with Minimal Allocation#
This can be useful if you want to process the elements of a large slice a in batches.
actions := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
batchSize := 3
batches := make([][]int, 0, (len(actions) + batchSize - 1) / batchSize)
for batchSize < len(actions) {
actions, batches = actions[batchSize:], append(batches, actions[0:batchSize:batchSize])
}
batches = append(batches, actions)
The result is as follows:
[[0 1 2] [3 4 5] [6 7 8] [9]]
In-place Removal of Duplicate Elements (Comparable Elements)#
import "sort"
in := []int{3,2,1,4,3,2,1,4,1} // The elements in the slice can be any sortable type
sort.Ints(in)
j := 0
for i := 1; i < len(in); i++ {
if in[j] == in[i] {
continue
}
j++
// If you need to preserve the original data
// in[i], in[j] = in[j], in[i]
// If you only need to keep the required data
in[j] = in[i]
}
result := in[:j+1]
fmt.Println(result) // [1 2 3 4]
Move to Front if Exists, Insert to Front if Not#
If the given element exists in the slice, move it to the front of the slice; if it does not exist, insert it at the front of the slice.
// moveToFront moves or adds needle to the front of haystack
func moveToFront(needle string, haystack []string) []string {
if len(haystack) != 0 && haystack[0] == needle {
return haystack
}
prev := needle
for i, elem := range haystack {
switch {
case i == 0:
haystack[0] = needle
prev = elem
case elem == needle:
haystack[i] = prev
return haystack
default:
haystack[i] = prev
prev = elem
}
}
return append(haystack, prev)
}
haystack := []string{"a", "b", "c", "d", "e"} // [a b c d e]
haystack = moveToFront("c", haystack) // [c a b d e]
haystack = moveToFront("f", haystack) // [f c a b d e]
Sliding Window#
Generate sliding windows of size size from slice input.
func slidingWindow(size int, input []int) [][]int {
// Return the input slice as the first element
if len(input) <= size {
return [][]int{input}
}
// Allocate the slice with the exact size needed
r := make([][]int, 0, len(input)-size+1)
for i, j := 0, size; j <= len(input); i, j = i+1, j+1 {
r = append(r, input[i:j])
}
return r
}
Example:
a := []int{1, 2, 3, 4, 5}
res := slidingWindow(2, a)
fmt.Println(res)
Output:
[[1 2] [2 3] [3 4] [4 5]]