Czy Go ma konstrukcję „if x in” podobną do Pythona?

289

Bez iteracji po całej tablicy, jak mogę sprawdzić, czy xw tablicy za pomocą Go? Czy język ma konstrukcję?

Jak Python: if "x" in array: ...


źródło
2
Może to być dupek stackoverflow.com/q/8307478/180100
7
AFAIK, Nie ma na to skrótu. Wewnętrznie Python również iteruje po tablicy, nie można tego obejść.
Danish94
6
BTW, ważna uwaga na ten temat jest taka, że ​​nie ma możliwości zrobienia tego (jak prosisz) „ [bez] iteracji po całej tablicy”. Wyrażenie takich pętli jawnie (lub za funkcją taką jak strings.Index) pomaga uczynić bardziej oczywistym, co robi kod. Mam wrażenie, że może myślisz, że Python in array:robi coś szybko / magicznie. AFAIK to nie jest. Wyraźne określenie pętli pomaga autorowi (i wszystkim czytelnikom) uświadomić sobie i rozważyć inne implementacje (np. Mapę).
Dave C
5
Jeśli jednak „x” w zestawie jest rzeczywiście bardzo szybki.
Roberto Alsina,
6
Nie sądzę, żebyśmy prosili o programowo szybkie podejście, po prostu prosimy o zwięzłe (i wciąż nie ma ...)
Migwell

Odpowiedzi:

340

W Go nie ma wbudowanego operatora. Musisz iterować po tablicy. Aby to zrobić, możesz napisać własną funkcję:

func stringInSlice(a string, list []string) bool {
    for _, b := range list {
        if b == a {
            return true
        }
    }
    return false
}

Jeśli chcesz mieć możliwość sprawdzenia członkostwa bez iteracji po całej liście, musisz użyć mapy zamiast tablicy lub wycinka, jak poniżej:

visitedURL := map[string]bool {
    "http://www.google.com": true,
    "https://paypal.com": true,
}
if visitedURL[thisSite] {
    fmt.Println("Already been here.")
}
andybalholm
źródło
4
czy można to zrobić bez określania typu? powiedzmy, że jeśli chcę tylko ogólną funkcję igły InHaystack (igła, stóg siana) bez osobnych metod dla każdego typu
Allen
25
Można to zrobić za pomocą pakietu odbicia, ale byłoby to dość nieefektywne (prawdopodobnie tak wolne, jakbyś napisał go w dynamicznym języku, takim jak Python). Poza tym nie. To ludzie mają na myśli, mówiąc, że Go nie ma leków generycznych.
andybalholm
2
Każdy, kto natknie się na tę odpowiedź, musi pamiętać, że NIE MOŻESZ sortować map. Duży minus korzystania z map go.
RisingSun
4
nie można również sortować map (obiektów) w JavaScript. Jest to błąd v8, w którym obiekty zwracają wartości w porządku alfabetycznym.
kumarharsh
7
mapy nie są sortowane w większości języków - jest to takie samo, jak w przypadku struktury danych mapy (mapy skrótów).
Hejazzman
100

Inne rozwiązanie, jeśli lista zawiera wartości statyczne.

np .: sprawdzanie poprawności wartości z listy prawidłowych wartości:

func IsValidCategory(category string) bool {
    switch category {
    case
        "auto",
        "news",
        "sport",
        "music":
        return true
    }
    return false
}
sebest
źródło
11
Tak, co jeśli twoje „prawidłowe wartości” pochodzą z bazy danych?
Rami Dabain
Tak, jest to schludne, ale tylko wtedy, gdy wartości te można wcześniej zdefiniować.
skarbonka
2
@RonanDejhero, a następnie mógłbym użyć GDZIE: myValue IN (podzapytanie) :)
anilech
3
Jest to
fajne w
50

Oto cytat z książki „Programowanie w ruchu: tworzenie aplikacji na XXI wiek”:

Korzystanie z prostego wyszukiwania liniowego, takiego jak to, jest jedyną opcją dla nieposortowanych danych i jest odpowiednie dla małych plasterków (do setek elementów). Jednak w przypadku większych wycinków - zwłaszcza jeśli przeprowadzamy wyszukiwanie wielokrotnie - wyszukiwanie liniowe jest bardzo nieefektywne, wymagając średnio połowy wyników za każdym razem.

Go zapewnia metodę sort.Search (), która wykorzystuje algorytm wyszukiwania binarnego: To wymaga porównania tylko log2 (n) elementów (gdzie n jest liczbą elementów) za każdym razem. Aby spojrzeć na to z perspektywy, liniowe wyszukiwanie 1000000 pozycji wymaga średnio 500000 porównań, w najgorszym przypadku porównań 1000000; wyszukiwanie binarne wymaga co najwyżej 20 porównań, nawet w najgorszym przypadku.

files := []string{"Test.conf", "util.go", "Makefile", "misc.go", "main.go"}
target := "Makefile"
sort.Strings(files)
i := sort.Search(len(files),
    func(i int) bool { return files[i] >= target })
if i < len(files) && files[i] == target {
    fmt.Printf("found \"%s\" at files[%d]\n", files[i], i)
}

https://play.golang.org/p/UIndYQ8FeW

AlexTT
źródło
10
Ma to sens tylko w przypadku wielokrotnego wyszukiwania. W przeciwnym razie masz złożoność n * log (n) * log (n) dla sortowania i wyszukiwania binarnego, w porównaniu do tylko n dla wyszukiwania liniowego.
chrześcijanin
1
To właściwie tylko n*log(n) + log(n)dwie konsekwentne niezależne operacje
pomo_mondreganto
27

Powyższy przykład z użyciem sortowania jest zamknięty, ale w przypadku łańcuchów wystarczy użyć SearchString:

files := []string{"Test.conf", "util.go", "Makefile", "misc.go", "main.go"}
target := "Makefile"
sort.Strings(files)
i := sort.SearchStrings(files, target)
if i < len(files) && files[i] == target {
    fmt.Printf("found \"%s\" at files[%d]\n", files[i], i)
}

https://golang.org/pkg/sort/#SearchStrings

Robert Weber
źródło
2
Ta odpowiedź wygląda na mniej pouczającą kopię wkleju odpowiedzi poniżej, która miała miejsce przed tą odpowiedzią.
cytinus
@cytinus Do jakiej odpowiedzi się odnosisz? To jedyny oparty na sort.SearchStrings.
akim
1
Otrzymałem przyspieszenie 100x przy wielokrotnym wyszukiwaniu przez duży kawałek.
Xeoncross
20

Właśnie miałem podobne pytanie i postanowiłem wypróbować niektóre sugestie z tego wątku.

Przeprowadziłem testy porównawcze najlepszych i najgorszych scenariuszy 3 rodzajów wyszukiwania:

  • za pomocą mapy
  • za pomocą listy
  • za pomocą instrukcji switch

oto kod funkcji:

func belongsToMap(lookup string) bool {
list := map[string]bool{
    "900898296857": true,
    "900898302052": true,
    "900898296492": true,
    "900898296850": true,
    "900898296703": true,
    "900898296633": true,
    "900898296613": true,
    "900898296615": true,
    "900898296620": true,
    "900898296636": true,
}
if _, ok := list[lookup]; ok {
    return true
} else {
    return false
}
}


func belongsToList(lookup string) bool {
list := []string{
    "900898296857",
    "900898302052",
    "900898296492",
    "900898296850",
    "900898296703",
    "900898296633",
    "900898296613",
    "900898296615",
    "900898296620",
    "900898296636",
}
for _, val := range list {
    if val == lookup {
        return true
    }
}
return false
}

func belongsToSwitch(lookup string) bool {
switch lookup {
case
    "900898296857",
    "900898302052",
    "900898296492",
    "900898296850",
    "900898296703",
    "900898296633",
    "900898296613",
    "900898296615",
    "900898296620",
    "900898296636":
    return true
}
return false
}

w najlepszych przypadkach wybierz pierwszy element z listy, w najgorszym przypadku nieistniejąca wartość.

Oto wyniki:

BenchmarkBelongsToMapWorstCase-4 2000000 787 ns/op BenchmarkBelongsToSwitchWorstCase-4 2000000000 0.35 ns/op BenchmarkBelongsToListWorstCase-4 100000000 14.7 ns/op BenchmarkBelongsToMapBestCase-4 2000000 683 ns/op BenchmarkBelongsToSwitchBestCase-4 100000000 10.6 ns/op BenchmarkBelongsToListBestCase-4 100000000 10.4 ns/op

Switch wygrywa do końca, najgorszy przypadek jest znacznie szybszy niż najlepszy. Mapy są najgorsze, a lista jest bliżej zmiany.

Morał brzmi: jeśli masz statyczną, względnie małą listę, instrukcja switch jest właściwym rozwiązaniem.

Igor
źródło
Nie wiem, czy Go optymalizuje ten przypadek, ale czy robi to różnicę, jeśli inicjujesz listę / mapę poza funkcją testową?
w00t
Ciekawe, jak potoczy się porównanie z posortowaną listą i czy sortowanie byłoby tego warte
Michael Draper,
Co powiesz na :zamiast ,w instrukcji switch? Czy to przyspiesza?
Thomas Sauvajon,
Próbowałem użyć wielu caseinstrukcji zamiast jednej sprawy. Wyniki są zasadniczo takie same dla obu funkcji.
Thomas Sauvajon,
7

Inną opcją jest użycie mapy jako zestawu. Używasz tylko kluczy, a wartość ma wartość logiczną, co zawsze jest prawdą. Następnie możesz łatwo sprawdzić, czy mapa zawiera klucz, czy nie. Jest to przydatne, jeśli potrzebujesz zachowania zestawu, a jeśli dodasz wartość wiele razy, będzie to tylko raz w zestawie.

Oto prosty przykład, w którym dodaję losowe liczby jako klucze do mapy. Jeśli ten sam numer zostanie wygenerowany więcej niż raz, nie ma to znaczenia, pojawi się na ostatecznej mapie tylko raz. Następnie używam prostego, jeśli sprawdź, czy klucz jest na mapie, czy nie.

package main

import (
    "fmt"
    "math/rand"
)

func main() {
    var MAX int = 10

    m := make(map[int]bool)

    for i := 0; i <= MAX; i++ {
        m[rand.Intn(MAX)] = true
    }

    for i := 0; i <= MAX; i++ {
        if _, ok := m[i]; ok {
            fmt.Printf("%v is in map\n", i)
        } else {
            fmt.Printf("%v is not in map\n", i)
        }
    }
}

Oto plac zabaw w ruchu

dostojny
źródło
0

Jest to tak blisko, jak tylko mogę uzyskać naturalne odczucie operatora „in” Pythona. Musisz zdefiniować własny typ. Następnie możesz rozszerzyć funkcjonalność tego typu, dodając metodę typu „has”, która zachowuje się tak, jakbyś miał nadzieję.

package main

import "fmt"

type StrSlice []string

func (list StrSlice) Has(a string) bool {
    for _, b := range list {
        if b == a {
            return true
        }
    }
    return false
}

func main() {
    var testList = StrSlice{"The", "big", "dog", "has", "fleas"}

    if testList.Has("dog") {
        fmt.Println("Yay!")
    }
}

Mam bibliotekę narzędzi, w której definiuję kilka typowych rzeczy takich jak ten dla kilku rodzajów wycinków, takich jak te zawierające liczby całkowite lub moje własne inne struktury.

Tak, działa w czasie liniowym, ale nie o to chodzi. Chodzi o to, aby zapytać i dowiedzieć się, jakie konstrukcje języka wspólnego ma Go, a czego nie. To dobre ćwiczenie. Czy ta odpowiedź jest głupia, czy użyteczna, zależy od czytelnika.

IcarusNM
źródło