这是一个创建于 1638 天前的主题，其中的信息可能已经有所发展或是发生改变。
用户输入支持如下格式：
10.0.17.35
192.168.1.1/23
192.37.3.3-192.168.39.39
现在有一个黑名单功能，也支持如上的形式，想问问这两个集合如何高效的去重呢？
😝
第 1 条附言 · 2020-06-02 17:50:19 +08:00
小弟太菜了，在github上找了一个函数，https://github.com/cilium/cilium/blob/master/pkg/ip/ip.go#L122
5 条回复 • 2020-05-23 06:43:51 +08:00
 |
1
GeruzoniAnsasu 2020-05-22 19:57:53 +08:00 via Android
首先不考虑域名和 url
我当时的实现大概这样 一个 - 指定的范围可以解析成若干个 cidr 或 ip 那现在只需要考虑 cidr 一种情况（ ip 可以看做 /32 ） 用二叉 trie 来存这些 cidr，在深度为 N 的节点有一个 cidr 对象表示这个 cidr 是 /N 如果某个节点左右子树都存在则递归向上合并节点 插入过程中途遇到某个节点说明这节点已经包含了待插入地址，跳过 然后就没有去重这一说了，匹配就是走这个 trie 跟插入流程几乎一样的 当时没有去重合并完还要导出合并结果的需求 |
|
2
GeruzoniAnsasu 2020-05-22 20:03:26 +08:00 via Android
还有一种方式是直接把 ip 地址算成线性空间，每个区间有左右界，合并的时候先按左界排序，然后判断
下一个区间的左界有没有落在前一个区间中，如果在，那么区间右界设成下一个区间右界，如果否，那么第一个区间已处理完毕，可以处理 23 区间 |
 |
3
wbrobot 2020-05-22 21:01:35 +08:00
ip2long，然后算数
|
 |
4
msg7086 2020-05-23 00:36:50 +08:00
听上去就是个和 trie 差不多的结构。
|
 |
5
singerll 2020-05-23 06:43:51 +08:00 via Android
转换为 10 进制？
|
Select Language