如何在Go中有效地从切片中删除元素?

jgovgodb  于 2023-09-28  发布在  Go
关注(0)|答案(2)|浏览(130)

有几种方法可以删除切片元素(-s)。但是如果我有一个应用程序,密集地使用切片。Go语言的切片在添加新元素方面做了很好的优化,但是是否有一种有效的方法来从切片中删除元素(-s)(不仅是速度,而且是内存优化)。
我知道slices.Delete函数是在Go 1.21中引入的,但在幕后它使用了以下众所周知的技术:

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

在这种情况下,看起来底层数组不会减少。这对速度有好处,但是如果我们有很多元素(例如,100 k或1 M),然后将它们减少到非常少(例如,只有10个)。看起来没有像用于增加切片容量那样的内存优化。
当我们不需要保留切片中元素的顺序时,可以使用以下方法(go 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]
}

当我们有大切片和少量元素要删除时,这可能很有用(它背后的想法是复制少量切片元素)。
关于存储器,在两种情况下,容量将是相同的,并且不会减少。举例来说:

// 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使用完整的切片表达式)不会减少底层数组-它只在切片结构中节省新的容量,以避免在向子切片添加新元素的情况下重写父切片元素(如this proposal中所述)。

0wi1tuuw

0wi1tuuw1#

没有“最佳”的解决方案。您在问题中展示了多种方法,对于特定场景,每种方法都可能比其他方法更好。
这对速度有好处,但是如果我们有很多元素(例如,100k或1M),然后将其减少到非常少(例如,只有10)。
如果你有这样的情况,当你想保留几个元素的许多,甚至不开始删除这些。用这几个元素构建一个新的切片。这当然也解决了内存问题,而且速度更快。
除了分配和使用一个新的切片,您不能通过使用一个完整的切片表达式来减少内存使用。只要存在对后台数组的引用,它就不会收缩(至少在当前的Go版本中不会)。如果你在一个情况下,一个大的后备数组被分配,但你只使用它的一小部分,你可以分配一个新的切片,并手动复制元素,让大的一个得到垃圾收集。
还要考虑到,如果你有一个大的切片,你可能必须从其中删除许多元素,切片可能不是最好的数据结构。例如,你可以尝试使用一个链表,或者你甚至可以尝试使用一个map:从链表或Map中删除一个元素会快得多,Map也会提供快速(O(n))查找时间。

5fjcxozz

5fjcxozz2#

如果像你说的那样(我没有理由怀疑它),切片非常适合那些正在追加项但在删除项时效率不高的用例,并且你有一个用例,需要从大型项集合中执行大量有效的删除,那么你可能应该考虑使用切片以外的东西。
container/list可以是候选者。

相关问题