检查字符串切片是否在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")

虽然理论上给出了无限多的值,但是地图更快,实际上搜索排序列表的速度更快.您需要自己进行基准测试.

Answer 2

要更换套件,你应该使用a map[string]struct{}.这是有效的,被认为是惯用的,"价值"绝对没有空间.

初始化集:

set := make(map[string]struct{})

放一件物品:

set["item"]=struct{}{}

检查项目是否存在:

_, isPresent := set["item"]

删除项目:

delete(set, "item")