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 .