Contient une méthode pour une tranche

214

Existe-t-il quelque chose de similaire à une slice.contains(object)méthode dans Go sans avoir à effectuer une recherche dans chaque élément d'une tranche?

vosmith
la source

Réponses:

226

Mostafa a déjà souligné qu'une telle méthode est triviale à écrire, et mkb vous a donné un indice pour utiliser la recherche binaire à partir du package de tri. Mais si vous allez faire beaucoup de ces contrôles contient, vous pouvez également envisager d'utiliser une carte à la place.

Il est trivial de vérifier si une clé de carte spécifique existe en utilisant l' value, ok := yourmap[key]idiome. Puisque vous n'êtes pas intéressé par la valeur, vous pouvez également créer un map[string]struct{}exemple. L'utilisation d'un espace vide struct{}ici a l'avantage de ne pas nécessiter d'espace supplémentaire et le type de carte interne de Go est optimisé pour ce type de valeurs. Par conséquent, map[string] struct{}est un choix populaire pour les décors du monde Go.

tux21b
la source
27
Notez également que vous devez écrire struct{}{}pour obtenir la valeur de la structure vide afin de pouvoir la transmettre à votre carte lorsque vous souhaitez ajouter un élément. Essayez-le et si vous rencontrez des problèmes, n'hésitez pas à demander. Vous pouvez également utiliser la solution de Mostafa si cela vous est plus facile à comprendre (sauf si vous avez d'énormes quantités de données).
tux21b
5
La solution est simple, c'est vrai. Mais que faut-il pour ajouter de telles fonctionnalités de base à l'exécution? Je n'ai pas trouvé de tels problèmes dans Go repo sur github. C'est triste et étrange.
Igor Petrov
1
Comment se map[string] boolcompare-t-il à map[string] struct{}. map[string] struct{}semble être un hack, surtout en initialisant une structure videstruct {}{}
vadasambar
@IgorPetrov a accepté, je suis surpris qu'une telle fonctionnalité de base ne soit pas déjà dans le runtime.
jcollum
180

Non, une telle méthode n'existe pas, mais est banale à écrire:

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

Vous pouvez utiliser une carte si cette recherche est une partie importante de votre code, mais les cartes ont également un coût.

Mostafa
la source
258
En fait, ce n'est pas trivial, car vous devez en écrire un pour chaque type que vous utilisez, et parce qu'il n'y a pas de surcharge, vous devez nommer chaque fonction différemment, comme dans C. append () peut fonctionner de manière générique car il a un support d'exécution spécial. Un générique contient serait utile pour la même raison, mais en réalité la solution générique n'est qu'un support générique dans le langage.
Eloff
15
@Eloffinterface{}
Alex Lockwood
2
@Alex Lockwood cela fonctionnera-t-il réellement avec les interfaces?
Ory Band
101
trivial == 7 lignes de code dont 1 boucle 1 branche if et 1 comparaison? Je pense qu'il me manque quelque chose ici ...
tothemario
3
Mais pourquoi ne pas les ajouter à go core lui-même?
Luna Lovegood
12

Au lieu d'utiliser un slice, mappeut être une meilleure solution.

exemple simple:

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

holys
la source
34
Dans sa forme actuelle, ce code n'offre aucun avantage, car il est inutile de construire une carte à partir d'une tranche si vous ne l'utilisez qu'une seule fois. - Pour être utile, ce code devrait plutôt fournir une fonction sliceToMapqui fait toute la préparation. Après cela, interroger la carte est trivial et efficace.
Roland Illig
9

Le package de tri fournit les blocs de construction si votre tranche est triée ou si vous souhaitez la trier.

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
}

SearchStringpromet de revenir the index to insert x if x is not present (it could be len(a)), donc une vérification de cela révèle si la chaîne contient la tranche triée.

Henrik Aasted Sørensen
la source
En termes de temps, la recherche régulière est O(n)et cette solution le fait O(n*log(n)).
plesiv
@plesiv c'est une recherche binaire, AFAICS. Cela ne ferait-il pas O (log n)?
Henrik Aasted Sørensen
oui, la recherche binaire et la fonction le containssont O(log(n)), mais l'approche globale est O(n*log(n))due au tri.
plesiv
3

Vous pouvez utiliser le package de réflexion pour parcourir une interface dont le type concret est une tranche:

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
la source
3
Bien sûr, vous pouvez utiliser le package de réflexion, mais ce n'est pas parce que vous le pouvez que vous le devriez. La réflexion coûte très cher.
Justin Ohms
3

S'il n'est pas possible d'utiliser une carte pour trouver des éléments en fonction d'une clé, vous pouvez envisager l' outil goderive . Goderive génère une implémentation spécifique au type d'une méthode contains, rendant votre code à la fois lisible et efficace.

Exemple;

type Foo struct {
    Field1 string
    Field2 int
} 

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

Pour générer la méthode deriveContainsFoo:

  • Installez goderive avec go get -u github.com/awalterschulze/goderive
  • Exécuter goderive ./...dans votre dossier d'espace de travail

Cette méthode sera générée pour deriveContains:

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

Goderive prend en charge de nombreuses autres méthodes d'aide utiles pour appliquer un style de programmation fonctionnel en cours.

Alexander van Trijffel
la source
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
la source
2

Pas sûr que les génériques soient nécessaires ici. Vous avez juste besoin d'un contrat pour votre comportement souhaité. Faire ce qui suit n'est rien de plus que ce que vous auriez à faire dans d'autres langues si vous vouliez que vos propres objets se comportent dans les collections, en remplaçant Equals () et GetHashCode () par exemple.

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
la source
1
"n'est pas plus que ce que vous auriez à faire dans d'autres langages" n'est pas vraiment vrai - par exemple, en C # Contains()est implémenté List<T>, vous n'avez donc qu'à l'implémenter Equals()pour ce travail.
George
1

J'ai créé un benchmark très simple avec les solutions de ces réponses.

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

Ce n'est pas une vraie référence car au départ, je n'ai pas inséré trop d'éléments mais n'hésitez pas à le fork et à le changer.

F. Norbert
la source
J'y ai pensé mais ce n'est pas si représentatif car ma machine n'est pas si puissante.
F. Norbert
-1

Le style go:

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
la source
2
Cela ne répond pas à la question et ne donne pas d'informations supplémentaires.
Croolman
-1

Cela peut être considéré comme un peu «hacky» mais en fonction de la taille et du contenu de la tranche, vous pouvez joindre la tranche ensemble et faire une recherche de chaîne.

Par exemple, vous avez une tranche contenant des valeurs de mot unique (par exemple "oui", "non", "peut-être"). Ces résultats sont ajoutés à une tranche. Si vous souhaitez vérifier si cette tranche contient des résultats "peut-être", vous pouvez utiliser

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

Son adéquation dépend en réalité de la taille de la tranche et de la longueur de ses membres. Il peut y avoir des problèmes de performances ou d'adéquation pour les grandes tranches ou les valeurs longues, mais pour les tranches plus petites de taille finie et de valeurs simples, il s'agit d'une doublure valide pour obtenir le résultat souhaité.

chopper24
la source
Ne fonctionnera pas dans une situation où les éléments ont un texte similaire mais pas exactement le mêmeexSlice := ["yes and no", "maybe", "maybe another"]
Raees Iqbal
Il s'agit d'une approche plutôt agréable pour réaliser une solution de revêtement simple et rapide. Vous avez juste besoin d'exiger un délimiteur sans ambiguïté (peut être une virgule) et de faire le travail supplémentaire pour mettre les deux chaînes entre crochets ","+strings.Join(exSlice,",")+","",maybe,"
:,