英文:
Check whether a string slice contains a certain value in Go
问题
检查一个特定值是否在字符串切片中的最佳方法是什么？在其他语言中，我会使用Set，但Go语言没有Set。
到目前为止，我最好的尝试是这样的：
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
这个解决方案对于小切片来说应该是可以的，但对于包含许多元素的切片该怎么办？
英文:
What is the best way to check whether a certain value is in a string slice? I would use a Set in other languages, but Go doesn't have one.
My best try is this so far:
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
This solution should be ok for small slices, but what to do for slices with many elements?
答案1
得分: 64
如果您有一个任意顺序的字符串切片，在切片中查找一个值需要O(n)的时间。这适用于所有的编程语言。
如果您打算一遍又一遍地进行搜索，您可以使用其他数据结构来加快查找速度。然而，构建这些数据结构至少需要O(n)的时间。因此，只有在使用数据结构进行多次查找时才能获得好处。
例如，您可以将字符串加载到一个映射中。然后查找将需要O(1)的时间。插入也需要O(1)的时间，使得初始构建需要O(n)的时间：
set := make(map[string]bool)
for _, v := range list {
set[v] = true
}
fmt.Println(set["b"])
您还可以对字符串切片进行排序，然后进行二分查找。二分查找的时间复杂度为O(log(n))。构建可能需要O(n*log(n))的时间。
sort.Strings(list)
i := sort.SearchStrings(list, "b")
fmt.Println(i < len(list) && list[i] == "b")
尽管从理论上讲，给定无限数量的值，映射更快，但实际上，搜索排序列表很可能更快。您需要自己进行基准测试。
英文:
If you have a slice of strings in an arbitrary order, finding if a value exists in the slice requires O(n) time. This applies to all languages.
If you intend to do a search over and over again, you can use other data structures to make lookups faster. However, building these structures require at least O(n) time. So you will only get benefits if you do lookups using the data structure more than once.
For example, you could load your strings into a map. Then lookups would take O(1) time. Insertions also take O(1) time making the initial build take O(n) time:
set := make(map[string]bool)
for _, v := range list {
set[v] = true
}
fmt.Println(set["b"])
You can also sort your string slice and then do a binary search. Binary searches occur in O(log(n)) time. Building can take O(n*log(n)) time.
sort.Strings(list)
i := sort.SearchStrings(list, "b")
fmt.Println(i < len(list) && list[i] == "b")
Although in theory given an infinite number of values, a map is faster, in practice it is very likely searching a sorted list will be faster. You need to benchmark it yourself.
答案2
得分: 20
要替换集合，你应该使用map[string]struct{}。这是高效且被认为是惯用的，"values"不占用任何空间。
初始化集合：
set := make(map[string]struct{})
添加一个项：
set["item"]=struct{}{}
检查一个项是否存在：
_, isPresent := set["item"]
移除一个项：
delete(set, "item")
英文:
To replace sets you should use a map[string]struct{}. This is efficient and considered idiomatic, the "values" take absolutely no space.
Initialize the set:
set := make(map[string]struct{})
Put an item :
set["item"]=struct{}{}
Check whether an item is present:
_, isPresent := set["item"]
Remove an item:
delete(set, "item")
答案3
得分: 4
你可以使用一个map，并且将值设置为布尔类型。
m := map[string]bool{"a": true, "b": true, "x": true}
if m["a"] { // 如果"a"不在map中，将返回false
// 它在map中
}
还有一个sort包，你可以使用它对切片进行排序和二分查找。
英文:
You can use a map, and have the value e.g. a 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
}
There's also the sort package, so you could sort and binary search your slices
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论