array - list golang

Ir: ¿Cuál es la forma más rápida/limpia de eliminar varias entradas de un sector?

Question

¿Cómo implementarías la función deleteRecords en el siguiente código:

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

Aquí hay una opción, pero espero que sean más limpias / rápidas y de aspecto más funcional:

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 2

Con l y ids suficientemente grandes, será más efectivo ordenar () las dos listas primero y luego hacer un solo bucle sobre ellas en lugar de dos bucles anidados

Answer 3

En lugar de buscar identificadores repetidamente, puedes usar un mapa. Este código preasigna el tamaño completo del mapa y, a continuación, simplemente mueve los elementos de la matriz en su lugar. No hay otras asignaciones.

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 4

Para el caso que describió, donde len (ids) es aproximadamente 10 y len (* l) está en varios cientos, esto debería ser relativamente rápido, ya que minimiza las asignaciones de memoria al actualizar en su lugar.

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

Salida:

[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

Para un proyecto personal, hice algo como esto:

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:]...)
}

No muta el original, pero debe ser relativamente eficiente. Probablemente es mejor simplemente hacer:

func filter(sl []int, fn func(int) bool) (result []int) {
    for _, v := range sl {
       if !fn(v) {
         result = append(result, v)
       }
    }
    return
}

Más sencillo y limpio. Si quieres hacerlo en el lugar, probablemente quieras algo como:

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

Puede optimizar esto para usar copy para copiar rangos de elementos, pero eso es el doble del código y probablemente no valga la pena.

Entonces, en este caso específico, probablemente haría algo como:

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

(Nota: no probado).

Sin asignaciones, nada sofisticado, y asumiendo el tamaño aproximado de la lista de Registros y la lista de ID que presentó, es probable que una simple búsqueda lineal se realice tan bien como las cosas más sofisticadas pero sin ningún tipo de sobrecarga. Me doy cuenta de que mi versión muta la división y devuelve una nueva división, pero eso no es un tanto idiomático en Go, y evita forzar la asignación de la división en el sitio de llamada.

Answer 6

Realicé algunos puntos de referencia en mi máquina, probando la mayoría de los enfoques que se dan en las respuestas aquí, y este código sale más rápido cuando tienes hasta 40 elementos en la lista de ID:

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

No dijo si es importante conservar el orden de los registros en la lista. Si no lo hace, esta función es más rápida que la anterior y todavía bastante limpia.

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

A medida que aumenta el número de identificadores, también aumenta el costo de la búsqueda lineal. Con alrededor de 50 elementos, usar un mapa o realizar una búsqueda binaria para buscar el ID se vuelve más eficiente, siempre que pueda evitar reconstruir el mapa (o volver a ordenar la lista) cada vez. Con varios cientos de ID, se vuelve más eficiente usar un mapa o una búsqueda binaria, incluso si tiene que reconstruirlo cada vez.

Si desea conservar el contenido original de la división, algo como esto es más apropiado:

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 7

Use el método Eliminar del paquete de vectores como guía, o simplemente use un Vector en lugar de un sector.