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

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

Answer 2

这里是一个选择，但我希望有清洁/更快更多的功能期待的：

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 
} 

Answer 3

使用vector package's Delete method为一个指南，或者只是使用一个矢量而不是一个切片。

Answer 4

对于您所描述的情况，其中len（ids）约为10，len（* 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} 

Answer 5

而不是反复搜索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] 
} 

Answer 6

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

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中不是非惯用的，并且它避免了强制将分片放在callsite处。

Answer 7

有了足够大的L和IDS这将是更有效的排序（）两个列表，然后再办一个循环而不是两个嵌套循环