30

特定の値が文字列スライスにあるかどうかを確認するための最良の方法は何ですか？他の言語でセットを使用しますが、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

マップを使用して、ブール値などの値を持つことができます

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 に答える