set - tag - Compruebe si un segmento de cadena contiene un cierto valor en Go

tag mailchimp name

Question

¿Cuál es la mejor manera de verificar si un determinado valor está en un segmento de cadena? Yo usaría un Set en otros idiomas, pero Go no tiene uno.

Mi mejor intento es esto hasta ahora:

package main

import "fmt"

func main() {
    list := []string{"a", "b", "x"}
    fmt.Println(isValueInList("b", list))
    fmt.Println(isValueInList("z", list))
}

func isValueInList(value string, list []string) bool {
    for _, v := range list {
        if v == value {
            return true
        }
    }
    return false
}

http://play.golang.org/p/gkwMz5j09n

Esta solución debería estar bien para cortes pequeños, pero ¿qué hacer para cortes con muchos elementos?

Answer 1

Para reemplazar conjuntos debes usar una map[string]struct{} . Esto es eficiente y considerado idiomático, los "valores" no ocupan espacio alguno.

Inicializar el conjunto:

set := make(map[string]struct{})

Poner un artículo:

set["item"]=struct{}{}

Compruebe si un elemento está presente:

_, isPresent := set["item"]

Eliminar un artículo:

delete(set, "item")

Answer 2

Puede usar un mapa y tener el valor, por ejemplo, un bool

m := map[string] bool {"a":true, "b":true, "x":true}
if m["a"] { // will be false if "a" is not in the map
    //it was in the map
}

También está el paquete de sort , por lo que puede ordenar y buscar binarios en sus segmentos

Answer 3

Si tiene un segmento de cadenas en un orden arbitrario, para encontrar si un valor existe en el segmento requiere O (n) tiempo. Esto se aplica a todos los idiomas.

Si tiene la intención de realizar una búsqueda una y otra vez, puede utilizar otras estructuras de datos para que las búsquedas sean más rápidas. Sin embargo, la construcción de estas estructuras requiere al menos O (n) de tiempo. Por lo tanto, solo obtendrá beneficios si realiza búsquedas utilizando la estructura de datos más de una vez.

Por ejemplo, podría cargar sus cadenas en un mapa. Entonces las búsquedas tomarían O (1) tiempo. Las inserciones también toman O (1) tiempo, lo que hace que la construcción inicial tome O (n) tiempo:

set := make(map[string]bool)
for _, v := range list {
    set[v] = true
}

fmt.Println(set["b"])

También puede ordenar su segmento de cadena y luego hacer una búsqueda binaria. Las búsquedas binarias ocurren en tiempo O (log (n)). La construcción puede tomar tiempo O (n * log (n)).

sort.Strings(list)
i := sort.SearchStrings(list, "b")
fmt.Println(i < len(list) && list[i] == "b")

Aunque en teoría dado un número infinito de valores, un mapa es más rápido, en la práctica es muy probable que buscar una lista ordenada sea más rápido. Usted necesita compararlo usted mismo.