gscan_quic 1.8 版的去重算法反馈

新版更新了去重算法，对于上万的IP/IP段都是秒加载，但是这个算法呢，得看Go的快排有没有排好，有时好用有时不好用，所以也可称之为猴去重算法 :trollface:

举个例子，有这些IP/IP段，总共有 19 个

172.56.129.23
172.56.129.24
172.56.129.25
172.56.129.26
172.56.129.27
172.56.129.28
172.56.129.29
172.56.129.30
172.56.129.31
172.56.129.32
105.112.8.181
105.112.8.182
105.112.8.183
105.112.8.184
105.112.8.185
105.112.8.186
105.112.8.187
105.112.8.190
172.56.129.0/24

假如是以前的去重算法，那么结果应该是

105.112.8.181
105.112.8.182
105.112.8.183
105.112.8.184
105.112.8.185
105.112.8.186
105.112.8.187
105.112.8.190
172.56.129.0/24

因为 172.56.129.0/24 包含其他几个 172.56.129.xxx，所以这些都给去掉了，最终会剩下这9个结果

新版呢，可能会漏掉几个，可以看到有几个 172.56.129.xxx 的没有被去掉，最后剩下 12 个

172.56.129.25
172.56.129.24
172.56.129.0/24
105.112.8.181
105.112.8.182
105.112.8.183
105.112.8.184
105.112.8.185
105.112.8.186
105.112.8.187
105.112.8.190
172.56.129.32

所以这是一个不稳定算法，但是好处是性能比较好，其实很多人的IP段一般是没有重复的，所以去重就显得不那么重要

主要是我看有不少兄弟加载大量IP段，可能会加载几分钟或是几十分钟，这样一来就不划算了，所以即使搜到一些重复的，也比那样快，所以。。。

当然还是去重算法的不完美，以后有好的算法，还是会更新的。。。

有问题的话可以反馈

Sep 21 '17 13:09 Kisesy

更新到 1.9 了，去重效果跟以前是差不多的，上面说的漏IP情况基本没有了，不过我也没测试。。。性能比 1.8 降低了

Sep 21 '17 16:09 Kisesy

建议还是加个开关得了，其实个人都是自己去重了，才加载的，当然，估计很多人是不先去重的。不知道这个算法具体怎么运作，但是俺个人一般用宏或者手工来去重，以JS的“低效”，也是差不多“飞速”。是不是这个不单单是算法的问题？流程也是牵扯？不知道go语言的的具体操作，但是不是可以分为3部分、4部分？——①排序，并分开单个ip与24段（16等全部转为24？或者不转？——个人一直觉得直接上16段是很粗暴的，大大降低效率 😀 ）？②单个ip临时转为24段（并去重，这样大大减少数据量），并于现存24段比较？有的与没有的，作个标记③剔除先有24段已有的，然后把单独的ip与24段组合成一个list

基本上没怎么接触过算法，不知道用分步走、或者说流程来控制、简化下？如果算法是直接撸，即不排序，不分步走，每个ip都与24段比较，可能就会大量耗费资源了。

如果不设置开关，也可以考虑单独做一个网页js文件、或者python文件？但这里又带来一个隐忧，即重复的数据可能带来低效率的重复扫描。想想，可能还是集合进来比较好。甚至不设开关，但目前主要是会严重影响加载效率——或者说之前。

Sep 22 '17 07:09 blob2015

另外，之前在gp提出的剔除ip里非g家的、不对外的，这个设想，主要还是用在“精炼”阶段，即随着ip数量过万，甚至到了5万后，ip的鱼龙混杂，会有相对明显的影响，这时候，不时“精炼”一下，对于特定时段的顺滑使用，是有需要的。不过，在初次扫描时候，这个可能会耗费大量资源，倒是可以缓缓。这个倒是可以搞个开关？

Sep 22 '17 07:09 blob2015

@blob2015 现在的算法已经比较快了，以前的算法扫IP段还是可以的，但是扫纯IP是非常非常慢的。原因有很多，主要一个原因是以前的算法是我用了几分钟写出来的，没有任何优化 :trollface:

新版算法就是个简单的相邻重复元素去重算法，是原地去重的，在复杂度上是远远低于以前的重复遍历的正好利用了排完序后大范围的IP排在最前面，这样一来，也避免了排序时使用自定义排序优先度的问题

效率是很高的，举个例子：比如 xxnet 提供的纯IP是22万4000多，放到08年的电脑上跑，也能在10秒之内加载如果是 1.8 版，那么可以在1，2秒内加载再比如 qwerttaa 提供的 1万6000多个IP段，在1.9版也是秒加载

我更新说明里写的提高了多少倍性能，也是根本不准的，那是加载1万多个IP，算出来的而这个性能提高，是加载越多IP，那么性能倍数越高，比如:以前可能要加载 40 多分钟的，现在也能在1，2秒内加载完成。

Sep 22 '17 10:09 Kisesy

至于精炼IP段之类的，我可以另外写程序或脚本，因为这样可以经常性自行的调整有好想法，可以到 https://gitter.im/Kisesy/Lobby 聊天室里说说

Sep 22 '17 10:09 Kisesy

@Kisesy 这是我写的一个“转换、排序、去重”。你看下。 😄

https://github.com/XX-net/XX-Net-dev/issues/30#issuecomment-330179276

Sep 26 '17 13:09 MeABc

@MeABc 可以，但是不能操作 ipv6，得用标准库 ipaddress 还有，你这是什么格式转什么格式啊，光看代码，容易看懵

Sep 26 '17 14:09 Kisesy

1.0.0.0-1.0.0.255 转成 1.0.0.0/24

脚本思路：把文件里所有的 1.0.0.0-1.0.0.255 这种格式，枚举成单个 IP ，单个 IP 转成 1.0.0.0/24 这种格式，然后去重。结果是原有的位置不变 ---- 不排序。（我上面说错了，没有排序这功能。。。）

对的，这个不能转 ipv6。

Sep 26 '17 14:09 MeABc

def splitip(strline):
    """从每组地址中分离出起始IP以及结束IP"""
    begin = ""
    end = ""
    if "-" in strline:
        "xxx.xxx.xxx.xxx-xxx.xxx.xxx.xxx"
        begin, end = strline.split("-")
        if 1 <= len(end) <= 3:
            prefix = begin[0:begin.rfind(".")]
            end = prefix + "." + end
    elif strline.endswith("."):
        "xxx.xxx.xxx."
        begin = strline + "0"
        end = strline + "255"
    elif "/" in strline:
        "xxx.xxx.xxx.xxx/xx"
        (ip, bits) = strline.split("/")
        if checkipvalid(ip) and (0 <= int(bits) <= 32):
            orgip = from_string(ip)
            end_bits = (1 << (32 - int(bits))) - 1
            begin_bits = 0xFFFFFFFF ^ end_bits
            begin = to_string(orgip & begin_bits)
            end = to_string(orgip | end_bits)
    else:
        "xxx.xxx.xxx.xxx"
        begin = strline
        end = strline

return begin, end

对了，不单支持 1.0.0.0-1.0.0.255 这种。支持上在这几种。

Sep 26 '17 14:09 MeABc

@MeABc 额，这样去重我倒是想过... 但是这样有缺点，那就是会产生额外不应该扫的IP，比如我只想扫这几个IP

105.112.8.181
105.112.8.182
105.112.8.183
105.112.8.184
105.112.8.185
105.112.8.186
105.112.8.187
105.112.8.190

如果经过这个脚本就会精简成 105.112.8.0/24，这样就多扫了不少IP

Sep 26 '17 14:09 Kisesy

明白了。你们两个上面的对话说实话我没看完，太长了，抱歉。。

我再想想有啥好思路。

Sep 26 '17 14:09 MeABc

粗暴一点，直接把大于 /24 的都分解成 /24 和 /32，这样就好去重了。

Sep 26 '17 14:09 SeaHOH

@MeABc 有人讨论真是好，哈哈，想法越多越好

顺便说下，对于"192.168.1-2.1-10" 这种格式的IP，可以用另外的代码比如这个，这样可以精简分割IP然后再调用ipRange的过程，这是我以前写的，现在都看不懂了... :trollface:

from itertools import product
ip = "192.168.1-2.1-10" 

def split(x):
    r = list(map(int, x.split('-')))
    if '-' in x:
        return list(range(r[0],r[1]+1))
    return r

for x in product(*map(split, ip.split('.'))):
    print('.'.join(map(str,x)))

这代码只支持"192.168.1-2.1-10" 这种，不支持 1.0.0.0-1.0.0.255

Sep 26 '17 14:09 Kisesy

@SeaHOH 分解会产生大量IP段，这很浪费内存和时间，因为比对的数量也增加了

Sep 26 '17 14:09 Kisesy

那就全合并，然后分解成一定上限大小的段。

Sep 26 '17 14:09 SeaHOH

@SeaHOH 这样也是会出现多扫IP的情况举个例子，这个应该是好的结果

"1.9.22.0-255"
"1.9.0.0/16"
"1.9.22.0-255"
"1.9.22.0/24"
"1.9.22.0-255"
"1.9.22.0-1.9.22.100"
"1.9.22.0-1.9.22.255"
"1.9.0.0/16"
"3.3.3.0/24"
"3.3.0.0/16"
"3.3.3.0-255"
"1.1.1.0/24"
"1.9.0.0/16"
"2001:db8::1/128"
"127.0.0.0"
"127.0.0.1"
	  |
	  |
	  v
[1.9.0.0/16 3.3.0.0/16 1.1.1.0/24 203.0.113.0/24 2001:db8::1/128, 127.0.0.0, 127.0.0.1]

Sep 26 '17 14:09 Kisesy

哇，"192.168.1-2.1-10" 这种我没有看明白。。。

Sep 26 '17 14:09 MeABc

@MeABc 会生成

192.168.1.1
192.168.1.2
192.168.1.3
192.168.1.4
192.168.1.5
192.168.1.6
192.168.1.7
192.168.1.8
192.168.1.9
192.168.1.10
192.168.2.1
192.168.2.2
192.168.2.3
192.168.2.4
192.168.2.5
192.168.2.6
192.168.2.7
192.168.2.8
192.168.2.9
192.168.2.10

Sep 26 '17 14:09 Kisesy

@Kisesy 你也真是的，这种格式也想得出来。

Sep 26 '17 15:09 MeABc

@MeABc 这是别人想出来的，我把别人的代码抄来精简了一下这是原代码

try:
    from itertools import imap as map
    range = xrange
except:
    from functools import reduce

def expand(segment):
    if '-' in segment:
        start, end = map(int, segment.split('-'))
        return list(map(str, range(start, end+1)) )
    return [segment]

def parse_ip(ip):
    seg_list = list(map(expand, ip.split('.')))
    return reduce(lambda lx, ly: [x+'.'+y for x in lx for y in ly], seg_list)

# print ("\n".join(parse_ip("192.168.1-2.1-10")))

# ....................................................

from itertools import product

ip = "192.168.1-2.1-10" 
segs = [seg for seg in ip.split('.')] 
segs = [[int(iter) for iter in seg.split('-')] for seg in segs] 
segs = [range(seg[0], seg[1]+1) if len(seg)==2 else range(seg[0], seg[0]+1) for seg in segs] 
ips = product(*segs) 
join_fuc = lambda l: '.'.join([str(i) for i in l]) 
ips = [join_fuc(ip) for ip in ips]

# print ("\n".join(ips))

Sep 26 '17 15:09 Kisesy

为什么会多呢？合并和分解正确就不该有多余或重复的 IP/段。

Sep 26 '17 15:09 SeaHOH

@SeaHOH 我记的是会有多余，忘了，但是这算法挺复杂的吧，比如把 '1.0.0.0/16' 和 '192.0.2.1/32' 合并

Sep 26 '17 15:09 Kisesy

解析一行描述文本，生成起始和终止两个数值。
重复 1，把得到的两组数值进行合并。
重复 2 直到文本结束。
按一定上限大小从之前的数据中分离出新的起始和终止数值，直到数据分离完毕。

Sep 26 '17 15:09 SeaHOH

可以一次解析完毕，然后排序再做 2，速度要快很多倍。

Sep 26 '17 15:09 SeaHOH

@Kisesy

从文件中读取，再分两个 IP 池。一个池是单 IP，一个放 IP 段。 IP 段的枚举成单个 IP 。两个池合并、去重。

Sep 26 '17 15:09 MeABc

单个 IP 也可以看作是起始和终止数值相同的段。

Sep 26 '17 15:09 SeaHOH

@SeaHOH 嗯。但 @Kisesy 的要求是不要多扫 IP 。我再想想是不是我哪里理解错了。

Sep 26 '17 15:09 MeABc

效率？自己手写优化比标准库要快。（Python 之类的脚本语言不一定）

Sep 26 '17 15:09 SeaHOH

@SeaHOH 海哥说的我都懵B了，还是给个小例子吧

@MeABc 关于读取完IP段后，再分解，合并，这些过程都会产生大量内存而现在的算法是不会产生任何额外空间的

Sep 26 '17 15:09 Kisesy

我写一写，为什么写成现在的算法

Sep 26 '17 15:09 Kisesy

gscan_quic gscan_quic copied to clipboard

1.8 版的去重算法反馈

gscan_quic
gscan_quic copied to clipboard