algorithm - Go のコンテナーの種類

Question

私はGoに慣れようとしているので、いくつかの検索機能を実装しようとしましたが、コンテナタイプのドキュメントを調べましたが、組み込みのタイプはcontainsメソッドを実装していません. 何か足りないものがありますか?そうでない場合、メンバーシップのテストを行うにはどうすればよいですか? 独自のメソッドを実装する必要がありますか、それともすべての要素を反復処理する必要がありますか? もしそうなら、コンテナ型のこの基本的なメソッドを省略した理由は何ですか?

Answer 1

標準ライブラリのコンテナ型では、要素を引き出すときに型アサーションを行う必要があります。コンテナー自体には、コンテナーに含まれている型がわからず、比較を行う方法がないため、メンバーシップのテストを行う方法がありません。

Ric Szopa のスキップ リストの実装は、探しているものかもしれません。これには、Contains メソッドを実装する Set タイプがあります。

https://github.com/ryszard/goskiplist

私はそれを本番環境で使用しており、非常に満足しています。

Answer 2

ただし、マップは、メソッドではなく「含む」構造を持つ組み込みタイプです。

http://play.golang.org/p/ddpmiskxqS

package main

import (
    "fmt"
)

func main() {
    a := map[string]string{"foo": "bar"}
    _, k := a["asd"]
    fmt.Println(k)
    _, k = a["foo"]
    fmt.Println(k)
}

Answer 3

container/list パッケージを使用すると、独自のループを作成して検索します。パッケージでこれを提供しない理由は、おそらく Dystroy が言ったように、O(n) 操作を隠すためです。

メソッドを追加することはできないので、ループを書くだけです。

for e := l.Front(); e != nil; e = e.Next() {
    data := e.Value.(dataType) // type assertion
    if /* test on data */ {
        // do something
        break
    }
}

それは十分に単純であり、O(n) の複雑さは明らかです。

検索をサポートする Go で提供されるデータ構造のレビューでは、sort パッケージをお見逃しなく。そこにある関数を使用すると、スライスを O(n log(n)) でソートし、O(log(n)) 時間でバイナリ検索できます。

最後に、ダニエルが提案したように、サードパーティのパッケージを検討してください。コンテナー タイプには、人気のある成熟したパッケージがいくつかあります。