有没有什么简单、性能也还过得去的 匹配 CIDR 集合（包含 IPv6 的 CIDR）的算法推荐？
monsoon · 2020-05-27 22:54:51 +08:00 · 1441 次点击这是一个创建于 1639 天前的主题，其中的信息可能已经有所发展或是发生改变。
需求很简单的，就是有一个 1W 个左右的 CIDR 集合（包括 IP 、CIDR ），想匹配一个 IP 在不在这里面。宿主语言是 Java 之类不直接操作指针的语言。输入结果是一个 true 或者 false 就可以了。 现在我只会 loop 的方法和 binary trie…… IPv6 和 IPv4 我会分成两个集合分开来匹配就可以了。
找了一下论文，感觉有很多的 Longest prefix match 的算法，但是不知道哪个改起来合适……写起来简单，性能也还可以，内存占用也不太。
大家有没有什么推荐的算法，不要那种要 128 次匹配（对于 IPv6 ）的那种。先谢谢了。
 |
1
rrfeng 2020-05-27 23:30:13 +08:00 via Android  1
cidr ？要想快直接变数值，然后算出边界来直接比大小啊……简单写个二分查找就不会很差吧
|
 |
2
iRiven 2020-05-28 09:46:22 +08:00 via Android 1
统统转成 u128，然后排序 二分查找，最快
|
 |
3
monsoon OP 非常感谢楼上两位，转换成了一个 pair （表示 range ） 的 list，二分法非常好写。
|
Select Language