Go: Каков самый быстрый/самый чистый способ удаления нескольких записей из среза?

Как бы вы реализовали функцию 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.
}

Ответы

Ответ 1

Я сделал несколько микро-бенчмаркинга на своей машине, опробовав большинство подходов, приведенных в ответах здесь, и этот код получается быстрее всего, когда у вас есть до 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]
}

Ответ 2

Для личного проекта я сделал что-то вроде этого:

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, и он избегает принуждения среза на колл-сайт быть выделенной кучей.

Ответ 3

В описанном вами случае, где 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}

Ответ 4

Вместо повторного поиска идентификаторов вы можете использовать карту. Этот код предопределяет полный размер карты, а затем просто перемещает элементы массива на место. Других распределений нет.

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

Ответ 6

Вот один из вариантов, но я надеюсь, что есть более чистые/более функционально выглядящие:

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
}

Ответ 7

При достаточно больших l и идентификаторах будет более эффективно сортировать оба списка, а затем сделать один цикл над ними вместо двух вложенных циклов