阅读： 1
1、引言
在https://blog.nsfocus.net/ip-cal/ 这篇博客中，笔者讲述了一种通过将IP映射到数轴上，进而判断其是否重叠的算法。
我们首先回顾一下上一篇的内容。
本文是这篇文章延续，该博客完整的讨论从一个算法落地为工程化的实现步骤。这是第二篇内容。对算法的实现进行扩展。
2、特殊情况的讨论
在第一篇博客中。我们考虑了将IP range解析为int，但有两例特殊情况我们没有讨论过。
第一类特殊情况是ipv6，众所周知，ipv6转化成数字后非常大。与ipv4位数不是一个量级。
举例来说:
“`
# Python 中 IPv6 转成的大整数
ipv6_int = 2**128 – 1
# 最大 IPv6 地址
# 浮点运算导致精度丢失
result = ipv6_int + 0.1print(result)
# 输出类似 3.402823669209385e+38，已不是精确整数
“`
因此我们可以考虑将算法并行化，设计两个数轴，分别存放ipv4，ipv6。用分治的思想，同时处理它们。算法伪代码如下：
“`
def build_ip_axis(iparr):
check_conflict(iparr)
def check_conflict_both(iparr):
“”” 分治处理 IPv4 和 IPv6 的冲突检测 “””
ipv4_ranges = []
ipv6_ranges = []
for ip in iparr:
if is_ipaddr_v6(ip):
ipv6_ranges.append(ip)
else:
ipv4_ranges.append(ip) # 分别检测，互不干扰
ok_v4, err_v4 = check_conflict(ipv4_ranges)
ok_v6, err_v6 = check_conflict(ipv6_ranges)
return ok_v4 and ok_v6, err_v4 + err_v6
“`
第二类特殊情况，是浮点运算。在计算机中，浮点运算是误差的。在第一篇博客中。我们有源代码如下
“`
if start == end:
start -= 0.1
end += 0.1
“`
我们这段代码的目的是让start/end相同的点展开一个极其“微弱”的距离（0.2），作为一个段参与整个运算。在ipv4下自然没问题。但是在ipv6下，由于计算机的浮点运算误差，它隐藏了一个偶发的问题：（补全此处）
因此我们需要修改代码，将数轴扩大，最小单位变为1，而不是0.1，以下为原始代码
“`
def check_conflict5(inets, src_inets=None, error_all=False):
“””
edit by [email protected]
所有ip范围映射到数轴，遍历一遍求和，无重叠的情况下数轴形如1,-1,1,-1,1,-1…，其他情况则说明有重叠
inets: 可能存在重叠iprange的iprange数组
src_inets: 原始的ipranges数组，当需要判断重叠的ipranges是否存在于某个集合中，可以把该集合传入src_inets
error_all: 是否发现所有重叠错误，为False则发现一处就会返回False
return: True无重叠, False有重叠
error_list为发生重叠冲突的ip范围集合
对于Ipv6来说，
Ipv6会被转化为大整数，在此大整数上做加减浮点数时会返回科学计数法的值，无法算出精确数字。
此时会影响效果。
因此采用变换坐标的形式，进行等比例缩放。
原IP段假设1~10，则有10个IP，每个数代表一个IP，
假设两个数代表一个IP，则1~20，共有10个IP。
放大比例尺。放大两倍（避免溢出）
“””
error_list = list()
if inets is None or len(inets) == 0:
return True, []
int_ranges = {}
ip_finds = {}
for ip in inets:
start, end = split_ipsegment_int(ip)
is_v6 = is_ipaddr_v6(ip)
if is_v6:
start *= 2
end *= 2
if start == end:
# 说明是单个ip
if is_v6:
start -= 1
end += 1
else:
start -= 0.1
end += 0.1
if start not in int_ranges.keys():
int_ranges[start] = 0
ip_finds[start] = []
if end not in int_ranges.keys():
int_ranges[end] = 0
ip_finds[end] = []
int_ranges[start] += 1
int_ranges[end] -= 1
ip_finds[start].append(ip)
ip_finds[end].append(ip)
temp_sum = 0
_sorted = sorted(int_ranges)
for index in range(0, len(_sorted)):
k = _sorted[index]
v = int_ranges[k]
temp_sum += v
if (v > 1 or v < -1) or (v == 1 and temp_sum > 1) or (v == -1 and temp_sum != 0):
# 1. 重叠的开始/结束
# 2. 是一个开始点，但是之前也有开始点
# 3. 是一个结束点，但经历结束点后和并没有变为0
error_list.extend(ip_finds[k])
if index – 1 >= 0:
# 把之前出问题的点也加上
# error_list.extend(ip_finds[_sorted[index – 1]])
pass
if not error_all:
break
error_list = set(error_list)
if src_inets is not None and len(src_inets) > 0:
if not isinstance(src_inets, set):
if isinstance(src_inets, list):
src_inets = set(src_inets)
error_list = error_list.intersection(src_inets)
else:
error_list = error_list.intersection(src_inets)
error_list = list(error_list)
if len(error_list) != 0:
return False, error_list
return True, error_list
“`
通过以上的修改，我们修复了两个问题：
- ipv4/v6在同一数轴上遍历的问题
- ipv6的精度丢失问题。
下一篇博客将讨论利用扫描线算法进一步拓展数轴的在ip属性搜索的方案。