检查Go中的字符串切片是否包含某个值 [英] Check whether a string slice contains a certain value in Go

问题描述

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

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?

推荐答案

如果您具有任意顺序的字符串切片，则查找切片中是否存在值需要O(n)时间.这适用于所有语言.

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.

如果您打算一遍又一遍地进行搜索，则可以使用其他数据结构来加快查找速度.但是，构建这些结构至少需要O(n)时间.因此，只有多次使用数据结构进行查找，您才能获得好处.

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.

例如，您可以将字符串加载到地图中.然后查找将花费O(1)时间.插入也需要O(1)时间，从而使初始构建也需要O(n)时间:

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"])

您还可以对字符串切片进行排序，然后进行二进制搜索.二进制搜索发生在O(log(n))时间.建筑物可能要花O(n * log(n))的时间.

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.

这篇关于检查Go中的字符串切片是否包含某个值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！