Go: 从一个切片中删除多个条目的最快/最干净的方法是什么？

Question

你如何在下面的代码中实现deleteRecords函数：

Example:

type Record struct {
  id int
  name string
}

type RecordList []*Record

func deleteRecords( l *RecordList, ids []int ) {
   // Assume the RecordList can contain several 100 entries.
   // and the number of the of the records to be removed is about 10.
   // What is the fastest and cleanest ways to remove the records that match
   // the id specified in the records list.
}

- Jeroen Dirks

Answer 1

我在我的计算机上进行了一些微基准测试，尝试了这里提供的大多数方法，并且当ids列表中有大约40个元素时，这段代码运行速度最快：

func deleteRecords(data []*Record, ids []int) []*Record {
    w := 0 // write index

loop:
    for _, x := range data {
        for _, id := range ids {
            if id == x.id {
                continue loop
            }
        }
        data[w] = x
        w++
    }
    return data[:w]
}

你没有说明在列表中是否重要保留记录的顺序。如果不需要保留，那么这个函数比上面的函数更快，并且仍然相当简洁。

func reorder(data []*Record, ids []int) []*Record {
    n := len(data)
    i := 0
loop:
    for i < n {
        r := data[i]
        for _, id := range ids {
            if id == r.id {
                data[i] = data[n-1]
                n--
                continue loop
            }
        }
        i++
    }
    return data[0:n]
}

随着id数量的增加，线性搜索的成本也随之上升。当元素数达到约50个时，使用map或者进行二分查找来查找id变得更加高效，只要你能避免每次都重建map（或排序列表）。当有几百个id时，即使需要每次重新构建map，使用map或二分查找也会更加高效。

如果您希望保留切片的原始内容，则像这样处理更为合适：

func deletePreserve(data []*Record, ids []int) []*Record {
    wdata := make([]*Record, len(data))
    w := 0
loop:
    for _, x := range data {
        for _, id := range ids {
            if id == x.id {
                continue loop
            }
        }
        wdata[w] = x
        w++
    }
    return wdata[0:w]
}

- rog

---

我已经进行了一些基准测试，并确认您的方法非常快。在重新排序函数上，我没有发现太多加速。似乎函数调用仍然很慢（至少在Windows 8g上是这样）。也许如果编译器开始内联，情况会有所改变。 - Jeroen Dirks

很好，我只是想知道为什么Go团队没有提供一种安全的方法来从切片中删除单个/多个条目。这显然是一种常见的方法。 - Shane Hou

如果您需要经常执行此操作，请考虑使用container/list提供的双向链表。 - mk12

Answer 2

"

对于一个个人项目，我做了类似于这样的事情：

"

func filter(sl []int, fn func(int) bool) []int {
    result := make([]int, 0, len(sl))
    last := 0
    for i, v := range sl {
        if fn(v) {
            result = append(result, sl[last:i]...)
            last = i + 1 
        }   
    }   
    return append(result, sl[last:]...)
}

它不会改变原始数据，但应该相对高效。最好只执行以下操作：

func filter(sl []int, fn func(int) bool) (result []int) {
    for _, v := range sl {
       if !fn(v) {
         result = append(result, v)
       }
    }
    return
}

更简单更清晰。 如果您想原地执行，您可能需要类似以下的东西：

func filter(sl []int, fn func(int) bool) []int {
    outi := 0
    res := sl
    for _, v := range sl {
        if !fn(v) {
            res[outi] = v 
            outi++
        }   
    }   
    return res[0:outi]
}

你可以优化此代码，使用 copy 来复制元素范围，但这会使代码量增加一倍，可能不值得。因此，在这种特定情况下，我可能会采取以下措施：

func deleteRecords(l []*Record, ids []int) []*Record {
    outi := 0
L:
    for _, v := range l { 
        for _, id := range ids {
            if v.id == id {
                continue L
            }   
        }   
        l[outi] = v 
        outi++
    }   
    return l[0:outi]
}

(注意: 未经测试。)

不进行分配，没有花哨的东西，并且假设您提供的记录列表和 id 列表的大致大小，简单的线性搜索很可能能够像花哨的东西一样完成任务，但是没有任何开销。 我意识到我的版本会改变切片并返回一个新的切片，但这在 Go 中不算不惯用，并且它避免了在调用端强制将切片分配到堆上。

- Kyle C

Answer 3

针对您所描述的情况，即ids的长度约为10，而*l的长度则在几百个左右，这应该是相对较快的，因为它通过就地更新来最小化内存分配。

package main

import (
    "fmt"
    "strconv"
)

type Record struct {
    id   int
    name string
}

type RecordList []*Record

func deleteRecords(l *RecordList, ids []int) {
    rl := *l
    for i := 0; i < len(rl); i++ {
        rid := rl[i].id
        for j := 0; j < len(ids); j++ {
            if rid == ids[j] {
                copy(rl[i:len(*l)-1], rl[i+1:])
                rl[len(rl)-1] = nil
                rl = rl[:len(rl)-1]
                break
            }
        }
    }
    *l = rl
}

func main() {
    l := make(RecordList, 777)
    for i := range l {
        l[i] = &Record{int(i), "name #" + strconv.Itoa(i)}
    }
    ids := []int{0, 1, 2, 4, 8, len(l) - 1, len(l)}
    fmt.Println(ids, len(l), cap(l), *l[0], *l[1], *l[len(l)-1])
    deleteRecords(&l, ids)
    fmt.Println(ids, len(l), cap(l), *l[0], *l[1], *l[len(l)-1])
}

输出：

[0 1 2 4 8 776 777] 777 777 {0 name #0} {1 name #1} {776 name #776}
[0 1 2 4 8 776 777] 772 777 {1 name #1} {3 name #3} {775 name #775}

- peterSO

Answer 4

不要反复搜索ID，可以使用映射。这段代码预先分配了映射的完整大小，然后只需在原地移动数组元素。没有其他的分配。

func deleteRecords(l *RecordList, ids []int) {
    m := make(map[int]bool, len(ids))
    for _, id := range ids {
        m[id] = true
    }
    s, x := *l, 0
    for _, r := range s {
        if !m[r.id] {
            s[x] = r
            x++
        }
    }
    *l = s[0:x]
}

- Sonia

Answer 5

可以使用向量包的Delete方法作为指南，或者直接使用向量而不是切片。

- Matt K

---

等一下，我看到你的回复后意识到我误解了问题。 - Matt K

有趣。我会等待并观察其他解决方案，然后进行一些基准测试，以找出解决方案之间是否存在很大差异。 - Jeroen Dirks

我敢打赌，这并不重要，因为你只是复制指针而不是整个结构体。 - Matt K

Answer 6

这里有一个选项，但我希望有更干净/更快速/更具功能性的选择：

func deleteRecords( l *RecordList, ids []int ) *RecordList {
    var newList RecordList
    for _, rec := range l {
        toRemove := false
        for _, id := range ids {
        if rec.id == id {
            toRemove = true
        }
        if !toRemove {
            newList = append(newList, rec)
        }
    }
    return newList
}

- Jeroen Dirks

---

append() 可能会在每次循环迭代中分配内存。 - Jesse

我假设append操作在需要重新分配内存时会将容量翻倍。虽然我在文档中没有找到相关说明... - Jeroen Dirks

为什么不使用make([]RecordList, len(*l))创建newList呢？ - Matt K

虽然append()在循环的每次迭代中都可以进行分配，但实际上并没有这样做。当前的实现是在文件src/pkg/runtime/slice.c中的runtime appendslice1函数中过度分配的。 - peterSO

返回值与类型不匹配 - newacct

经过一些基准测试，我发现在像这样的代码中，Go 中的函数调用具有显着的开销，因此重复的 append（以及底层数组的重新分配）使得该解决方案变慢。 - Jeroen Dirks

Answer 7

如果l和ids足够大，最好先对两个列表进行Sort()排序，然后再使用单个循环而不是两个嵌套循环。

- snakeru