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

Answer 1

我在我的机器上做了一些微基准测试,尝试了这里的回复中给出的大多数方法,当你在id列表中有大约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中,即使您每次都必须重建它,使用地图或二进制搜索也会变得更有效率.

如果您希望保留切片的原始内容,则更合适:

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