Sprawdź, czy plaster łańcuchowy zawiera określoną wartość w Go

Question

Jaki jest najlepszy sposób sprawdzenia, czy pewna wartość znajduje się w wycinku łańcucha? Używałbym zestawu w innych językach, ale Go go nie ma.

Moja najlepsza próba jest to tak daleko:

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

Rozwiązanie to powinno być ok dla małych plasterki, ale co zrobić na plasterki z wielu elementów?

Answer 1

Jeśli masz kawałek strun w dowolnej kolejności, znalezienie jeśli wartość istnieje w plaster wymaga O (n) czas. Dotyczy to wszystkich języków.

Jeśli zamierzasz wykonywać wyszukiwanie w kółko, możesz użyć innych struktur danych, aby wyszukiwanie było szybsze. Jednak budowanie tych struktur wymaga co najmniej O (n) czasu. Otrzymasz więc korzyści tylko wtedy, gdy korzystasz ze struktur danych więcej niż raz.

Na przykład można załadować łańcuchy do mapy. Wtedy wyszukiwania zajęłyby O (1) czas. Wstawki wziąć także O (1) czas podejmowania czas początkowy build odbioru O (n):

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

fmt.Println(set["b"]) 

Można również sortować Twój kawałek ciąg, a następnie zrobić wyszukiwania binarnego. Wyszukiwania binarne występują w czasie O (log (n)). Budynek może trwać od O (n * log (n)).

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

Choć teoretycznie podano nieskończoną liczbę wartości, mapa jest szybszy, w praktyce jest to bardzo prawdopodobne, szukając uporządkowany wykaz będzie szybciej. Musisz to zrobić samemu.

Answer 2

Aby wymienić zestawy, można użyć map[string]whatever. To nie byłaby lżejsza, jaką możesz sobie wyobrazić (jest wskaźnik do wartości, której nie potrzebujesz), ale oprócz pisania własnego stołu haszowego jest to najbardziej wydajny i jest całkiem zoptymalizowany, ponieważ jest wbudowany.

set := make(map[string]uint8) 

Aby umieścić element:

set[item]=1 

Aby sprawdzić, czy dany element jest obecny:

_, ok = set[item] 

jest to wspólny idiom w Go. Jeśli ok jest prawdziwe, to element był obecny. Jeśli ok jest fałszem, element nie był obecny.

Answer 3

Możesz użyć mapy i mieć wartość np. 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 
} 

Istnieje również pakiet sort, więc można sortować i wyszukiwania binarne twoje plastry