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

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

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 个元素时，使用映射或进行二进制搜索来查找 id 会变得更有效，只要您可以避免每次都重新构建映射(或重新排序列表)。在数百个 id 时，使用 map 或二分搜索会变得更有效，即使您每次都必须重新构建它。

如果您希望保留 slice 的原始内容，则更合适的是:

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