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 回答