Как бы вы реализовали функцию 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.
}
Я сделал несколько микро-бенчмаркинга на своей машине, опробовав большинство подходов, приведенных в ответах здесь, и этот код получается быстрее всего, когда у вас есть до 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]
}
По мере увеличения числа идентификаторов, так же как и стоимость линейного поиска. Примерно в 50 элементах использование карты или выполнение двоичного поиска для поиска идентификатора становится более эффективным, если вы не можете каждый раз перестраивать карту (или прибегать к списку). В нескольких сотнях идентификаторов становится более эффективным использование карты или двоичного поиска, даже если вам приходится перестраивать его каждый раз.
Если вы хотите сохранить исходное содержимое фрагмента, что-то вроде этого более подходит:
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 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]
}
(Примечание: непроверенный.)
Никаких распределений, ничего необычного и предполагая грубый размер списка записей и список идентификаторов, которые вы представили, простой линейный поиск, скорее всего, будет делать, а также более интересные вещи, но без каких-либо накладных расходов. Я понимаю, что моя версия мутирует срез и возвращает новый срез, но он не является идиоматическим в Go, и он избегает принуждения среза на колл-сайт быть выделенной кучей.
В описанном вами случае, где 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}
Вместо повторного поиска идентификаторов вы можете использовать карту. Этот код предопределяет полный размер карты, а затем просто перемещает элементы массива на место. Других распределений нет.
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 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
}
При достаточно больших l и идентификаторах будет более эффективно сортировать оба списка, а затем сделать один цикл над ними вместо двух вложенных циклов