关于二分法和HASH表效率比较的问题

ouiki

数据库应该是最慢的吧。不如文件快。

闸北陆小洪

这个问题  我来说下结论  亲测的

之前我是用最简单的方法在awk中遍历   大概耗时40分钟
使用二分查找后  只用了2分钟就完成了


至于楼主说的方法，当然没有问题。但是上哪里去找那么大的IP对照库是个问题啊。

ouiki

二分法用什么列表，主楼就用什么列表啊。

cjaizss

hash有个很郁闷的问题——查找存在方便，查找范围郁闷

ouiki

汗，感情我描述的这么不清楚啊。

列表                    HASH表(hash1)         
10.254.0.0/16             10.254               
10.2.0.0/10                 10.2
                                   10.3
                                    10.4
10.254.10.0/22            10.254.10
                                    10.254.11

不需要把所有的IP都列出来。
假设我要比较的IP是 10.254.1.2
只要 hash1{"10"},hash1{"10.254"},hash1{"10.254.1"},hash1{"10.254.1.2"} 中有一个成立就行。
再描述不清楚，我就死心了。

闸北陆小洪

你这么说  我就明白了  这样是可以的  没有任何问题   而且也很快

wenhq

回复 16# 闸北陆小洪


有测试的case么？


   

cao627

@ouiki
设两个ip段
1.56.0.0 - 1.58.255.255 x
1.68.0.0 - 1.71.255.255 y
要找出ip 1.58.1.1属于x还是y

你的方法
建表
1.56 -> x
1.57 -> x
1.58 -> x
1.68 -> y
1.69 -> y
1.70 -> y  
#原来两笔数据现在变成6笔了

判断有无key为1的项，没有   or  判断有无key为1.58的项，有。
#这里又用了or 进行了多次判断。

ouiki

我这段时间没有环境，前几天改一段代码，突然想到这个做法。
大概改了下然后让同事帮忙测一下，同事说比整个循环（不用二分法）快点有限。
我想着应该是至少快一个数量级，结果却只是快一点。
我就想不明白了，才来问大家的。

ouiki

回复 18# cao627


   对于hash来说，2项和200项的差别基本可以忽略吧？
我以为就是最后判断IP or 的时候需要判断4次。