algorithm - 如何对 trie 表中的 IP 地址进行排序？

Question

我想编写一些代码在我的 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 比较提出了很好的建议(也许这是我能做的最好的)，但在我看来有一种方法可以利用前缀长度对树进行排序，以便可以在更少的步骤中找到匹配项。这就是我要找的。

Answer 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() 已记录 here .