检查Go中的字符串切片是否包含某个值

Question

检查字符串切片中是否存在某个值的最佳方法是什么？我会用其他语言的Set，但Go没有。

到目前为止，我最好的尝试是：

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

对于小切片，此解决方案应该可以，但是对于包含许多元素的切片，该怎么办？

Answer 1

如果您具有任意顺序的字符串切片，则查找切片中是否存在值需要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")

尽管理论上给定无限数量的值，但映射会更快，但实际上，很有可能搜索排序列表会更快。您需要自己对其进行基准测试。