Verificare se una sezione di stringa contiene un determinato valore in Go

Question

Qual è il modo migliore per verificare se un certo valore si trova in una sezione di stringa? Vorrei usare un Set in altre lingue, ma Go non ne ha uno.

Il mio miglior prova è questo finora:

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

Questa soluzione dovrebbe essere ok per piccole fette, ma cosa fare per le fette con molti elementi?

Answer 1

Se si dispone di una fetta di stringhe in un ordine arbitrario, trovando se esiste un valore nella fetta richiede O (n) tempo. Questo vale per tutte le lingue.

Se si intende eseguire una ricerca più e più volte, è possibile utilizzare altre strutture dati per rendere più rapide le ricerche. Tuttavia, la costruzione di queste strutture richiede almeno un tempo O (n). Quindi otterrai benefici solo se effettui ricerche utilizzando la struttura dei dati più di una volta.

Ad esempio, è possibile caricare le stringhe in una mappa. Quindi le ricerche richiederebbero O (1) tempo. Inserimenti anche prendere O (1) tempo a fare il tempo iniziale accumulo prendere O (n):

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

fmt.Println(set["b"]) 

È inoltre possibile ordinare la vostra fetta di stringa e poi fare una ricerca binaria. Le ricerche binarie avvengono nel tempo O (log (n)). La costruzione può richiedere il tempo O (n * log (n)).

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

Anche se, in teoria, dato un numero infinito di valori, una mappa è più veloce, in pratica, è molto probabile che alla ricerca di una lista ordinata sarà più veloce. È necessario confrontarlo da soli.

Answer 2

Per sostituire i set è possibile utilizzare uno map[string]whatever. Questo non sarebbe il più leggero che tu possa immaginare (c'è un puntatore al valore che non ti serve), ma a parte scrivere il tuo hash table è il più efficiente, ed è piuttosto ottimizzato in quanto è incorporato.

set := make(map[string]uint8) 

Per mettere un elemento:

set[item]=1 

Per verificare se un elemento è presente:

_, ok = set[item] 

Si tratta di un linguaggio comune in Go. Se ok è vero, allora l'oggetto era presente. Se ok è falso, l'elemento non era presente.

Answer 3

È possibile utilizzare una mappa e ottenere il valore es. 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 
} 

C'è anche il pacchetto sort, quindi si può ordinare e binari di ricerca le vostre fette