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?
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.
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 {returntrue}}returnfalse}
Vous pouvez utiliser une carte si cette recherche est une partie importante de votre code, mais les cartes ont également un coût.
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
16
Si la tranche est triée, une recherche binaire est implémentée dans le sortpackage .
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))}
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.
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.
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.Interfaceif arrV.Index(i).Interface()== elem {returntrue}}}returnfalse}
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 Foostruct{Field1stringField2int}
func Test(m Foo)bool{var allItems []Fooreturn 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 {returntrue}}returnfalse}
Goderive prend en charge de nombreuses autres méthodes d'aide utiles pour appliquer un style de programmation fonctionnel en cours.
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 Identifiableinterface{GetIdentity()string}
func IsIdentical(thisIdentifiable, that Identifiable)bool{return(&this==&that)||(this.GetIdentity()== that.GetIdentity())}
func contains(s []Identifiable, e Identifiable)bool{for _, a := range s {ifIsIdentical(a,e){returntrue}}returnfalse}
"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.
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){returntrue}}returnfalse}
s :=[]string{"a","b","c","o"}// test if s contains "o"
ok :=Contains(len(s), func(i int)bool{return s[i]=="o"})
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é.
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,"
Réponses:
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 unmap[string]struct{}
exemple. L'utilisation d'un espace videstruct{}
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.la source
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).map[string] bool
compare-t-il àmap[string] struct{}
.map[string] struct{}
semble être un hack, surtout en initialisant une structure videstruct {}{}
Non, une telle méthode n'existe pas, mais est banale à écrire:
Vous pouvez utiliser une carte si cette recherche est une partie importante de votre code, mais les cartes ont également un coût.
la source
interface{}
Si la tranche est triée, une recherche binaire est implémentée dans le
sort
package .la source
Au lieu d'utiliser un
slice
,map
peut être une meilleure solution.exemple simple:
http://play.golang.org/p/CEG6cu4JTf
la source
sliceToMap
qui fait toute la préparation. Après cela, interroger la carte est trivial et efficace.Le package de tri fournit les blocs de construction si votre tranche est triée ou si vous souhaitez la trier.
SearchString
promet de revenirthe 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.la source
O(n)
et cette solution le faitO(n*log(n))
.contains
sontO(log(n))
, mais l'approche globale estO(n*log(n))
due au tri.Vous pouvez utiliser le package de réflexion pour parcourir une interface dont le type concret est une tranche:
https://play.golang.org/p/jL5UD7yCNq
la source
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;
Pour générer la méthode deriveContainsFoo:
go get -u github.com/awalterschulze/goderive
goderive ./...
dans votre dossier d'espace de travailCette méthode sera générée pour deriveContains:
Goderive prend en charge de nombreuses autres méthodes d'aide utiles pour appliquer un style de programmation fonctionnel en cours.
la source
la source
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.
la source
Contains()
est implémentéList<T>
, vous n'avez donc qu'à l'implémenterEquals()
pour ce travail.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.
la source
Le style go:
la source
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
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é.
la source
exSlice := ["yes and no", "maybe", "maybe another"]
","+strings.Join(exSlice,",")+","
",maybe,"