1

Go プログラムで小さな「ルーティング テーブル」を作成するためのコードを少し作成したいと考えています。

http://github.com/petar/GoLLRBパッケージで左寄りの赤黒木を使用していますが、基本的には少しいじった後に動作するようですが、IP をソートしていないと思われます。ツリーを作成すると、正しく接頭辞が付けられます。私が実験的に使った「lessThan」関数は

func lessRoute(a, b interface{}) bool {
    aNet := a.(Route).Net
    bNet := b.(Route).Net

    for i, a := range aNet.IP {
        if a < bNet.IP[i] {
            return true
        }
        if a > bNet.IP[i] {
            return false
        }
    }
    return false
}

(完全なコードはhttps://gist.github.com/4283789にあります)

これは正しい結果をもたらすようですが、あまり効率的ではありません。

私のテストでは、ルートを追加しています

AddRouteString(tree, "10.0.0.0/8", 10)
AddRouteString(tree, "10.20.0.0/16", 20)
AddRouteString(tree, "10.21.0.0/16", 21)

10.22.0.1 のルートを検索すると、正しい結果を見つける前に 10.21.0.0/16 と 10.20.0.0/16 が検索されます。

適切な結果をより速く見つけるには、ツリーをどのように並べ替える必要がありますか?

更新: @jnml には、IP 比較を高速化する方法に関する優れた提案があります (おそらくそれが私にできる最善の方法です)。しかし、プレフィックス長を利用してツリーを並べ替える方法があるように思えますそのため、より少ない手順で一致を見つけることができます。それが私が探しているものです。

4

1 に答える 1

1

私はおそらく次のように書くでしょう：

if bytes.Compare([]byte(a), []byte(b)) < 0 {
        // ... whatever to do when address a < b (lexicographically)
}

または、ツリー コンパレータの場合:

func lessRoute(a, b interface{}) bool {
        return bytes.Compare([]byte(a.(Route).Net.IP), []byte(b.(Route).Net.IP)) < 0
}

bytes.Compare()ここに文書化されています。

于 2012-12-14T09:16:08.303 に答える