Enthält die Methode für ein Slice

214

Gibt es etwas Ähnliches wie eine slice.contains(object)Methode in Go, ohne jedes Element in einem Slice durchsuchen zu müssen?

Vosmith
quelle

Antworten:

226

Mostafa hat bereits darauf hingewiesen, dass das Schreiben einer solchen Methode trivial ist, und mkb gab Ihnen einen Hinweis zur Verwendung der binären Suche aus dem Sortierpaket. Wenn Sie jedoch viele solcher Überprüfungen durchführen möchten, können Sie stattdessen auch eine Karte verwenden.

Es ist trivial, mithilfe der value, ok := yourmap[key]Redewendung zu überprüfen, ob ein bestimmter Kartenschlüssel vorhanden ist . Da Sie nicht an dem Wert interessiert sind, können Sie beispielsweise auch einen erstellen map[string]struct{}. Die Verwendung eines struct{}Leerzeichens hier hat den Vorteil, dass kein zusätzlicher Speicherplatz erforderlich ist und der interne Kartentyp von Go für diese Art von Werten optimiert ist. Daher map[string] struct{}ist eine beliebte Wahl für Sets in der Go-Welt.

tux21b
quelle
27
Beachten Sie auch, dass Sie schreiben müssen struct{}{}, um den Wert der leeren Struktur zu erhalten, damit Sie ihn an Ihre Map übergeben können, wenn Sie ein Element hinzufügen möchten. Probieren Sie es einfach aus und fragen Sie bei Problemen. Sie können auch die Mostafa-Lösung verwenden, wenn dies für Sie leichter zu verstehen ist (es sei denn, Sie verfügen über große Datenmengen).
Tux21b
5
Die Lösung ist einfach, das stimmt. Aber was braucht es, um solche grundlegenden Funktionen zur Laufzeit hinzuzufügen? Ich habe solche Probleme in Go Repo auf Github nicht gefunden. Das ist traurig und seltsam.
Igor Petrov
1
Wie map[string] boolvergleicht man mit map[string] struct{}. map[string] struct{}scheint ein Hack zu sein, der vor allem eine leere Struktur initialisiertstruct {}{}
vadasambar
@IgorPetrov stimmte zu, ich bin überrascht, dass eine solche Grundfunktion noch nicht zur Laufzeit vorhanden ist.
JCollum
179

Nein, eine solche Methode existiert nicht, ist aber trivial zu schreiben:

func contains(s []int, e int) bool {
    for _, a := range s {
        if a == e {
            return true
        }
    }
    return false
}

Sie können eine Karte verwenden, wenn diese Suche ein wichtiger Bestandteil Ihres Codes ist, aber Karten haben auch Kosten.

Mostafa
quelle
257
Eigentlich ist es nicht trivial, weil Sie für jeden verwendeten Typ einen schreiben müssen und weil es keine Überladung gibt, müssen Sie jede Funktion anders benennen, wie in C. append () kann generisch funktionieren, weil es spezielle Laufzeitunterstützung bietet. Ein generisches enthält wäre aus dem gleichen Grund nützlich, aber in Wirklichkeit ist die generische Lösung nur die Unterstützung von Generika in der Sprache.
Eloff
15
@ Eloffinterface{}
Alex Lockwood
2
@ Alex Lockwood funktioniert das tatsächlich mit Schnittstellen?
Ory Band
101
trivial == 7 Codezeilen einschließlich 1 Schleife 1 Zweig if-Anweisung und 1 Vergleich? Ich glaube, ich vermisse hier etwas ...
tothemario
3
Aber warum nicht diese in go core selbst hinzufügen?
Luna Lovegood
16

Wenn die Scheibe sortiert wird, gibt es eine binäre Suche in implementiert das sortPaket .

mkb
quelle
11

Stattdessen wird eine der Verwendung slice, mapkann eine bessere Lösung sein.

einfaches Beispiel:

package main

import "fmt"


func contains(slice []string, item string) bool {
    set := make(map[string]struct{}, len(slice))
    for _, s := range slice {
        set[s] = struct{}{}
    }

    _, ok := set[item] 
    return ok
}

func main() {

    s := []string{"a", "b"}
    s1 := "a"
    fmt.Println(contains(s, s1))

}

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

Heilige
quelle
34
In der aktuellen Form bietet dieser Code keinen Vorteil, da es keinen Sinn macht, eine Karte aus einem Slice zu erstellen, wenn Sie sie nur einmal verwenden. - Um nützlich zu sein, sollte dieser Code eher eine Funktion bereitstellen sliceToMap, die die gesamte Vorbereitung übernimmt. Danach ist das Abfragen der Karte trivial und effizient.
Roland Illig
9

Das Sortierpaket enthält die Bausteine, wenn Ihr Slice sortiert ist oder Sie bereit sind, es zu sortieren.

input := []string{"bird", "apple", "ocean", "fork", "anchor"}
sort.Strings(input)

fmt.Println(contains(input, "apple")) // true
fmt.Println(contains(input, "grow"))  // false

...

func contains(s []string, searchterm string) bool {
    i := sort.SearchStrings(s, searchterm)
    return i < len(s) && s[i] == searchterm
}

SearchStringverspricht zurückzukehren the index to insert x if x is not present (it could be len(a)), also zeigt eine Überprüfung, ob die Zeichenfolge das sortierte Slice enthält.

Henrik Aasted Sørensen
quelle
In Bezug auf die Zeit ist die regelmäßige Suche O(n)und diese Lösung macht es O(n*log(n)).
Bitte
@plesiv es ist eine binäre Suche, AFAICS. Wäre das nicht O (log n)?
Henrik Aasted Sørensen
Ja, binäre Suche und die Funktion containssind O(log(n)), aber der Gesamtansatz ist O(n*log(n))auf die Sortierung zurückzuführen.
Bitte
3

Mit dem Reflect- Paket können Sie über eine Schnittstelle iterieren, deren konkreter Typ ein Slice ist:

func HasElem(s interface{}, elem interface{}) bool {
    arrV := reflect.ValueOf(s)

    if arrV.Kind() == reflect.Slice {
        for i := 0; i < arrV.Len(); i++ {

            // XXX - panics if slice element points to an unexported struct field
            // see https://golang.org/pkg/reflect/#Value.Interface
            if arrV.Index(i).Interface() == elem {
                return true
            }
        }
    }

    return false
}

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

Ethan Kennedy
quelle
3
Sicher können Sie das Reflect-Paket verwenden, aber nur weil Sie es können, heißt das nicht, dass Sie es sollten. Reflexion ist sehr teuer.
Justin Ohms
3

Wenn es nicht möglich ist, eine Karte zum Suchen von Elementen basierend auf einem Schlüssel zu verwenden, können Sie das Goderive- Tool in Betracht ziehen . Goderive generiert eine typspezifische Implementierung einer Include-Methode, wodurch Ihr Code sowohl lesbar als auch effizient wird.

Beispiel;

type Foo struct {
    Field1 string
    Field2 int
} 

func Test(m Foo) bool {
     var allItems []Foo
     return deriveContainsFoo(allItems, m)
}

So generieren Sie die deriveContainsFoo-Methode:

  • Installiere goderive mit go get -u github.com/awalterschulze/goderive
  • Führen Sie es goderive ./...in Ihrem Arbeitsbereichsordner aus

Diese Methode wird für deriveContains generiert:

func deriveContainsFoo(list []Foo, item Foo) bool {
    for _, v := range list {
        if v == item {
            return true
        }
    }
    return false
}

Goderive unterstützt einige andere nützliche Hilfsmethoden, um einen funktionalen Programmierstil in go anzuwenden.

Alexander van Trijffel
quelle
2
func Contain(target interface{}, list interface{}) (bool, int) {
    if reflect.TypeOf(list).Kind() == reflect.Slice || reflect.TypeOf(list).Kind() == reflect.Array {
        listvalue := reflect.ValueOf(list)
        for i := 0; i < listvalue.Len(); i++ {
            if target == listvalue.Index(i).Interface() {
                return true, i
            }
        }
    }
    if reflect.TypeOf(target).Kind() == reflect.String && reflect.TypeOf(list).Kind() == reflect.String {
        return strings.Contains(list.(string), target.(string)), strings.Index(list.(string), target.(string))
    }
    return false, -1
}
Jim Hsiang
quelle
2

Ich bin mir nicht sicher, ob hier Generika benötigt werden. Sie brauchen nur einen Vertrag für Ihr gewünschtes Verhalten. Das Folgende ist nicht mehr als das, was Sie in anderen Sprachen tun müssten, wenn Sie möchten, dass sich Ihre eigenen Objekte in Sammlungen verhalten, indem Sie beispielsweise Equals () und GetHashCode () überschreiben.

type Identifiable interface{
    GetIdentity() string
}

func IsIdentical(this Identifiable, that Identifiable) bool{
    return (&this == &that) || (this.GetIdentity() == that.GetIdentity())
}

func contains(s []Identifiable, e Identifiable) bool {
    for _, a := range s {
        if IsIdentical(a,e) {
            return true
        }
    }
    return false
}
JonPen
quelle
1
"ist nicht mehr als das, was Sie in anderen Sprachen tun müssten" ist nicht wirklich wahr - zB in C # Contains()ist auf implementiert List<T>, so dass Sie immer nur Equals()für diese Arbeit implementieren müssen .
George
1

Mit den Lösungen aus diesen Antworten habe ich einen sehr einfachen Benchmark erstellt.

https://gist.github.com/NorbertFenk/7bed6760198800207e84f141c41d93c7

Es ist kein wirklicher Benchmark, da ich anfangs nicht zu viele Elemente eingefügt habe, mich aber frei fühle, sie zu teilen und zu ändern.

F. Norbert
quelle
Ich habe darüber nachgedacht, aber es ist nicht so repräsentativ, weil meine Maschine nicht so leistungsstark ist.
F. Norbert
0

Es kann als etwas "hacky" angesehen werden, aber je nach Größe und Inhalt des Slice können Sie das Slice zusammenfügen und eine Zeichenfolgensuche durchführen.

Zum Beispiel haben Sie ein Slice, das einzelne Wortwerte enthält (z. B. "Ja", "Nein", "Vielleicht"). Diese Ergebnisse werden an eine Scheibe angehängt. Wenn Sie überprüfen möchten, ob dieses Slice "Vielleicht" -Ergebnisse enthält, können Sie verwenden

exSlice := ["yes", "no", "yes", "maybe"]
if strings.Contains(strings.Join(exSlice, ","), "maybe") {
  fmt.Println("We have a maybe!")
}

Wie geeignet dies wirklich ist, hängt von der Größe der Scheibe und der Länge ihrer Mitglieder ab. Es kann Leistungs- oder Eignungsprobleme für große Schichten oder lange Werte geben, aber für kleinere Scheiben mit endlicher Größe und einfachen Werten ist es ein gültiger Einzeiler, um das gewünschte Ergebnis zu erzielen.

chopper24
quelle
Funktioniert nicht in Situationen, in denen Elemente einen ähnlichen Text haben, aber nicht genau den gleichenexSlice := ["yes and no", "maybe", "maybe another"]
Raees Iqbal
Dies ist ein ziemlich guter Ansatz, um eine schnelle und schmutzige Einzeilerlösung zu erzielen. Sie müssen nur ein eindeutiges Trennzeichen benötigen (könnte ein Komma sein) und die zusätzliche Arbeit erledigen, um beide Zeichenfolgen in Klammern zu setzen : ","+strings.Join(exSlice,",")+",", und",maybe,"
nobar
-1

Der Go-Stil:

func Contains(n int, match func(i int) bool) bool {
    for i := 0; i < n; i++ {
        if match(i) {
            return true
        }
    }
    return false
}


s := []string{"a", "b", "c", "o"}
// test if s contains "o"
ok := Contains(len(s), func(i int) bool {
    return s[i] == "o"
})
Roy O'Young
quelle
2
Dies beantwortet weder die Frage noch gibt es zusätzliche Informationen.
Croolman