如何在Go中高效地从切片中删除元素？

Question

删除切片元素有多种方法。但是，如果我有一个需要大量处理切片的应用程序怎么办？ Go 切片对于添加新元素进行了很好的优化，但是有没有有效的方法从切片中删除元素（不仅通过速度，还通过内存）。

我知道 Go 1.21 中引入的 slices.Delete 函数，但在幕后它使用了以下众所周知的技术：

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

看起来在这种情况下底层数组不会减少。这对速度很有好处，但如果我们有很多元素（例如 100k 或 1M），然后将其减少到很少（例如只有 10 个），该怎么办？看起来没有任何内存优化，比如用于增加切片容量的内存优化。

当我们不需要保留切片中元素的顺序时，可以使用以下方法（go Playground 链接）：

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

当我们要删除大切片和小部分元素时，这可能很有用（其背后的想法是复制少量切片元素）。

关于内存，两种情况下容量都是一样的，不会减少。例如：

    // 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  

那么，有没有办法优化内存使用呢？例如，如果切片的长度小于其容量的一半，则将容量减少一半。

我也想知道如何有效地做到这一点，例如这样的技术

s[:len(s):len(s)]

（slices.Clip使用完整切片表达式）不会减少底层数组 - 它只会将切片结构中的新容量保存到在将新元素附加到子切片的情况下，避免重写父切片元素（如此提案中所述）。

Answer 1

不存在“一般最佳”解决方案。您在问题中展示了多种方法，对于特定场景，每种方法都可能比其他方法更好。

这对速度很有好处，但如果我们有很多元素（例如，100k 或 1M），然后将其减少到很少（例如，只有 10 个）怎么办？

如果您遇到这样的情况，当您想保留许多元素中的少数元素时，甚至不要开始删除这些元素。用这几个元素构建一个新切片。除了速度更快之外，这肯定也解决了内存问题。

除了分配和使用新切片之外，您无法通过使用完整切片表达式来减少内存使用量。只要存在对后备数组的引用，它就不会缩小（至少在当前的 Go 版本中不会）。如果您遇到分配了大后备数组但只使用其中一小部分的情况，您可以分配一个新切片并手动复制元素以让大数组被垃圾收集。

还要考虑到，如果您有一个大切片，您可能需要从中删除许多元素，那么切片可能不是最好的数据结构。例如，您可以尝试使用链表，或者甚至可以尝试映射：从链表或映射中删除元素会快得多，映射也将提供快速 (

O(n)

) 查找时间。

Answer 2

如果，正如您所说（我没有理由怀疑），切片非常适合附加项目但在删除项目时效率不高的用例，并且您有一个需要执行大量高效操作的用例从大型项目集合中删除，那么您也许应该考虑使用切片以外的其他东西。

容器/列表可以是候选者。