Go 删除切片元素

最简单的方法

我们都知道，删除切片元素的写法是：

1
2
3

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

但是，由于这涉及移动已删除元素索引之后的所有元素，如果切片很大，性能大受影响。

如果从大切片的开头删除元素，则成本也比从大切片的末尾删除要高得多。

而且为了使用上面写的 removeElementByIndex , 你需要知道要删除的元素的索引，可以通过使用一个简单的函数（或从 Go 实验包中使用 slices.IndexFunc ）来找到它：

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
}

在不需要保持原来顺序的情况下提高效率

但是，有一种更有效的方法来编写 removeElementByIndex 函数，只要您不需要保留切片中其余元素的顺序：

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]
}

其工作原理是将切片中的最后一个元素与要删除的元素交换，然后简单地将切片的大小缩小 1。

不保留顺序的事实可能是一个非常现实的缺点，但它可能并不总是构成问题，即使您确实需要切片保持有序状态，只要您有某种方法可以自己恢复顺序。

基准测试：

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)
	}
}

要运行这些基准测试，您可以使用以下命令（该 -bench 标志采用与两个测试函数的名称匹配的正则表达式）：

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

BenchmarkRemoveElementByIndexOne-16     583365337                2.036 ns/op
BenchmarkRemoveElementByIndexTwo-16     1000000000               0.2262 ns/op
PASS
ok      example.com     1.830s

正如你所看到的，第二个实现的速度几乎是第一个的十倍，运行时间只有五分之一纳秒，而不是整整两个纳秒。

从切片中删除许多元素

现在，我们可以在上面创建的两个 removeElementByIndex 函数中最好的函数的基础上进行构建，以创建另一个可以同时处理多个索引（索引的复数）删除的函数：

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]
}

您可能认为它就像遍历每个索引并调用处理每次迭代中删除每个索引的函数一样简单。

然而，它比这更复杂，因为每次我们在索引中删除一个元素时，我们都会改变切片中剩余元素的顺序，正如我们上面所讨论的。

这意味着函数迭代的索引可能不再包含我们打算删除的原始元素。

在上面的示例中，我们通过在遍历索引之前创建索引映射来解决这个问题（此时，键和值都包含初始索引）。然后在函数中 removeElementByIndex ，当我们将元素从最后一个索引移动到曾经包含我们不想再保留的元素的索引时，我们现在将映射的键设置为元素的初始索引，将值设置为元素移动到的索引。

这允许我们在未来的迭代中进行简单的查找，将最初提供给我们的索引转换为它曾经包含的元素随后移动的索引。

如果我们不这样做，我们最终可能无法删除正确的元素，或者更糟糕的是，当给定的索引大于每次删除元素时缩小的切片时，会导致代码出现 panic 。

现在还包括一个简单的验证检查，当我们遍历每个索引时，确保它至少为零且小于切片的长度，这样我们就不会尝试删除任何不存在的索引，正如我们之前提到的，这会导致我们的函数崩溃。

一种从切片中删除元素的更优雅的方法

鉴于每次删除元素时我们都会缩小切片，因此似乎可以合理地假设我们可以创建一个函数来执行相同的工作，但仅在删除所有元素后收缩切片一次。这就是我们在下面的内容：

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]
}

我们将切片的最终索引存储在变量中 backIndex ，然后在每次删除元素的循环迭代中递减它。然后，我们可以推断出我们需要将切片的大小缩小到 backIndex+1 （因为长度总是比最后一个索引大一个），我们在将切片返回给调用方之前这样做。

这个 removeManyElementsByIndices 函数的实现与前一个函数之间的唯一另一个显着区别是，我们在 indicesMap 中将删除元素的索引设置为 -1，这允许我们在已经处理过索引的情况下忽略它（即，如果索引切片包含相同的索引不止一次，那么它没有充分的理由这样做）。

创建过滤器函数

有时，您确切地知道要删除哪些索引或元素，但在其他许多时候，您只是知道应该删除哪种元素（即未通过给定测试的元素，称为谓词）。

我们现在可以使用该 removeManyElementsByIndices 函数创建另一个更高级别的函数，这将使我们更容易摆脱不再需要的元素：

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]
}

如果传递的元素是偶数（即可以被 2 整除，没有余数），您可以看到谓词函数如何返回 true ，并且由于我们删除了所有未通过谓词测试的元素，这意味着我们将从切片中删除所有奇数。

通过追加到新切片进行筛选

最后，我们可以创建函数的另一个 filter 实现，它甚至更简单（因为它不再需要调用函数 removeManyElementsByIndices ），并且，如果您计划删除大量元素，则性能可能会更高：

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]
}