30

检查某个值是否在字符串切片中的最佳方法是什么？我会在其他语言中使用 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

这个解决方案对于小切片应该没问题，但是对于有很多元素的切片怎么办？

4

3 回答 3

56

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

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

于 2012-11-22T21:26:20.153 回答
14

要替换集合，您应该使用map[string]struct{}. 这是有效的并且被认为是惯用的，“价值观”绝对没有空间。

初始化集合：

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

放一个项目：

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

检查项目是否存在：

_, isPresent := set["item"]

删除一个项目：

delete(set, "item")
于 2012-11-22T21:23:47.593 回答
3

您可以使用地图，并具有值，例如 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
}

还有sort包，因此您可以对切片进行排序和二进制搜索

于 2012-11-22T21:24:08.090 回答