未分類
29 5 月 2020

有没有什么简单、性能也还过得去的 匹配 CIDR 集合（包含 IPv6 的 CIDR）的算法推荐？

有没有什么简单、性能也还过得去的 匹配 CIDR 集合（包含 IPv6 的 CIDR）的算法推荐？

資深大佬 : monsoon 2

需求很简单的，就是有一个 1W 个左右的 CIDR 集合（包括 IP 、CIDR ），想匹配一个 IP 在不在这里面。宿主语言是 Java 之类不直接操作指针的语言。输入结果是一个 true 或者 false 就可以了。 现在我只会 loop 的方法和 binary trie…… IPv6 和 IPv4 我会分成两个集合分开来匹配就可以了。

找了一下论文，感觉有很多的 Longest prefix match 的算法，但是不知道哪个改起来合适……写起来简单，性能也还可以，内存占用也不太。

大家有没有什么推荐的算法，不要那种要 128 次匹配（对于 IPv6 ）的那种。先谢谢了。

大佬有話說 (3)

  • 資深大佬 : rrfeng

    cidr ？要想快直接变数值，然后算出边界来直接比大小啊……简单写个二分查找就不会很差吧

  • 資深大佬 : iRiven

    统统转成 u128，然后排序 二分查找，最快

  • 主 資深大佬 : monsoon

    非常感谢上两位，转换成了一个 pair （表示 range ） 的 list，二分法非常好写。