你將如何實現在下面的代碼的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.
}
我做了一些微基準測試我的機器上，嘗試在大多數這裏的答覆給出的方法，而這種代碼出來最快的，當你起牀到的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]
}
這裏是一個選擇，但我希望有清潔/更快更多的功能期待的：
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
}
使用vector package's Delete method爲一個指南，或者只是使用一個矢量而不是一個切片。
對於您所描述的情況，其中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}
而不是反覆搜索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]
}
對於一個個人項目，我做了這樣的事情：
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處。
有了足夠大的L和IDS這將是更有效的排序（）兩個列表，然後再辦一個循環而不是兩個嵌套循環
append（）可以在該循環的每次迭代中分配。 – Jessta 2011-02-16 21:43:34
我假設如果需要重新分配，append的容量就會增加一倍。儘管我在文檔中找不到它... – 2011-02-16 21:50:50
爲什麼不用`make（[] RecordList，len（* l））``創建`newList`？ – mkb 2011-02-16 21:53:33