Establece la estructura de datos en Golang

69

Realmente me gusta Google Golang, pero ¿alguien podría explicar cuál es la razón para que los implementadores hayan omitido una estructura de datos básica como los conjuntos de la biblioteca estándar?

cobie
fuente
8
El lenguaje en realidad se llama Go, no golang
jozefg
92
Pero "golang" se puede buscar más
Matt
18
Mucho más buscable. Google "go set" devuelve imágenes de una tabla de madera con piezas en blanco y negro.
Doug Richardson

Respuestas:

68

Una razón potencial para esta omisión es que es realmente fácil modelar conjuntos con un mapa.

Para ser honesto, creo que también es un poco descuidado, sin embargo, mirando a Perl, la historia es exactamente la misma. En Perl obtienes listas y tablas hash, en Go obtienes matrices, sectores y mapas. En Perl, generalmente usaría una tabla hash para todos y cada uno de los problemas relacionados con un conjunto, lo mismo se aplica a Go.

Ejemplo

Para imitar un conjunto de entradas en Go, definimos un mapa:

set := make(map[int]bool)

Agregar algo es tan fácil como:

i := valueToAdd()
set[i] = true

Eliminar algo es solo

delete(set, i)

Y la incomodidad potencial de esta construcción se abstrae fácilmente:

type IntSet struct {
    set map[int]bool
}

func (set *IntSet) Add(i int) bool {
    _, found := set.set[i]
    set.set[i] = true
    return !found   //False if it existed already
}

Y eliminar y obtener se puede definir de manera similar, tengo la implementación completa aquí . La principal desventaja aquí es el hecho de que ir no tiene genéricos. Sin embargo, es posible hacer esto, interface{}en cuyo caso habría emitido los resultados de get.

jozefg
fuente
3
Aquí está mi versión ligeramente revisada con los métodos Contiene y Tamaño: play.golang.org/p/tDdutH672-
Rick-777
19
En lugar de map[int]booluno puede usar map[int]struct{}en su lugar. Prefiero el último
pepper_chico
20
map[int]struct{}.. El struct{}toma 0 bytes.
Boopathi Rajaa
2
github.com/fatih/set es una implementación de mi basada en mapas y estructuras vacías. Es seguro para subprocesos y tiene una API simple.
Fatih Arslan
66
Con map[int]struct{}usted no puede hacer if mymap["key"] {para verificar la membresía. Google recomienda usarbool (busque "Se puede implementar un conjunto").
Timmmm
3

Creo que esto tiene que ver con el golangenfoque en la simplicidad. sets llegar a ser realmente útil con difference, intersection, union, issubset, y así sucesivamente .. métodos. Quizás el golangequipo consideró que es demasiado para una estructura de datos. Pero por lo demás, es un "conjunto tonto" que solo tiene add, containsy removepuede ser fácilmente replicado con maplo explicado por @jozefg.

Akavall
fuente
Estoy en desacuerdo. un conjunto se usa principalmente para comprobaciones de membresía y semántica única. una implementación establecida sería perfectamente utilizable sin esos métodos. Dicho esto, también son triviales de implementar.
Sedat Kapanoglu
2

La respuesta anterior funciona SOLO SI la clave es un tipo incorporado. Para complementar la respuesta anterior, aquí hay una manera de implementar un conjunto cuyos elementos son tipos definidos por el usuario:

package math

// types

type IntPoint struct {
    X, Y int
}

// set implementation for small number of items
type IntPointSet struct {
    slice []IntPoint 
}

// functions

func (p1 IntPoint) Equals(p2 IntPoint) bool {
    return (p1.X == p2.X) && (p1.Y == p2.Y)
}

func (set *IntPointSet) Add(p IntPoint) {
    if ! set.Contains(p) {
        set.slice = append(set.slice, p)
    }
}

func (set IntPointSet) Contains(p IntPoint) bool {
  for _, v := range set.slice {
    if v.Equals(p) {
      return true
    }
  }
  return false
}

func (set IntPointSet) NumElements() int {
    return len(set.slice)
}

func NewIntPointSet() IntPointSet {
  return IntPointSet{(make([]IntPoint, 0, 10))}
}
amahfouz
fuente
8
"funciona SOLO SI las claves son de tipo incorporado" está mal . type mySet map[IntPoint]boolFunciona perfectamente bien. Todo lo que se requiere del tipo de clave utilizado en un mapa es que tiene ==y!= . La igualdad de los tipos de estructura está bien definida, su Equalsmétodo debe ser justo p1 == p2.
Dave C
1
Es cierto que la igualdad para las estructuras está bien definida, pero si la estructura contiene mapas o sectores como campos, se compararán por referencia, en lugar de por valor. Esto puede no ser lo que quieres.
Chaim-Leib Halbert
1
Tengo un pequeño problema con esta solución, porque Containstoma tiempo lineal, mientras que aMap[]toma tiempo constante, independientemente del número de miembros. Una solución mejor crearía internamente una clave única basada en el contenido de cada miembro y aprovecharía las consultas de tiempo constante que mapproporciona el tipo. Incluso existen soluciones más rápidas que consideran el comportamiento de la caché, etc.
Chaim-Leib Halbert