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

pitonas

厉害。厉害。

expert1

回复 30# seesea2517


    我现在使用以下方法：
awk 'NR==FNR{a[$2]=$0;next} {for(ip in a) {if(int(ip)>=$1 && int(ip)<=$2) {print a[ip]"\t"$3"\t"$4"\t"$5"\t"$6}}}'  文件1 文件2

这种awk的数组就是hash方法，但是for i in a,会逐个遍历key，效率很低。

这种和主题讨论的不是一回事吧。

cao627

是否可以这样理解：hash是一种上层观念，数组是底层基础，二分法是观念和基础之外的方法。
所以对于一本书而言索引不是基础，而是观念。基础是索引本身也避不开的一页一页。

seesea2517

回复 32# expert1


    嗯。我认为lz所说的用 hash 的方法肯定不再要用 for in 来遍历的了。因为构造 hash 就是为了避免遍历。

这是一个简化的例子（不然在构造 hash 表的那一步比较复杂，反而影响到对根本问题的查看了）。在 awk 里先根据对应文件做出一个 hash 表，第二步就直接进行 hash 查找了，不需要遍历的。这时候程序的主要花费其实是在构造表，而查找则只是一个 hash 映射就行了。当然，hash 表的效率要看具体的实现了。具体的 zooyo 版主比较熟悉，我只会说不会做。
不知道 lz 的意思是不是这样，不是的话还请 lz 补充。

1. 
   
2. [seesea@UC ~]$ head *
   
3. ==> 1.txt <==
   
4. 1.2.3.4 CN
   
5. 1.2.3.5 CN
   
6. 1.2.3.6 US
   
7. 1.2.3.7 KR
   
8. ==> 2.txt <==
   
9. 1.2.3.4
   
10. 1.2.3.5
    
11. 1.2.3.6
    
12. 1.2.3.7
    
13. ==> addr.awk <==
    
14. NR == FNR {
    
15.     # 根据第一个文件构造 hash 表，这里简化例子，实际的构造要复杂一些
    
16.     addr[$1] = $2
    
17. }
    
18. 
    
19. NR != FNR {
    
20.     # 直接通过 IP 进行 hash 查找，不需要遍历
    
21.     print $1 "的位置是：" addr[$1]
    
22. }
    
23. 
    
24. [seesea@UC ~]$ awk -f addr.awk 1.txt 2.txt
    
25. 1.2.3.4的位置是：CN
    
26. 1.2.3.5的位置是：CN
    
27. 1.2.3.6的位置是：US
    
28. 1.2.3.7的位置是：KR

复制代码

expert1

回复 34# seesea2517


    这种看起来是很简单，但你这地址是展开了，比如192.168.0.1  --- 192.168.0.255 CN (# 举例而已）

那么你首先得一个个列出来，xxx.0.1 cn 然后到0.255 cn 这样实际上也就是逐个扫描了。姑且不论后边的部分。

seesea2517

回复 35# expert1


    嗯，要根据需求来做了。可以说 hash 是先全体扫描，然后再做的时候就不需要扫描了，对于查询多的情况就合算；二分查找或顺序查等方法则是有查询需求的时候再进行扫描，对于重复的查询需要同样的消耗，但如果需要查找的数量不多，则就更合算。

cao627

可以说 hash 是先全体扫描，然后再做的时候就不需要扫描了，对于查询多的情况就合算；二分查找或顺序查等方法则是有查询需求的时候再进行扫描，对于重复的查询需要同样的消耗，但如果需要查找的数量不多，则就更合算

站在高层的观点看是这这样
但从底层看呢呢
庞大的hash表在内存中的结构神奇到cpu不用遍历这块空间就能知道任意的key是存在还是不存在吗？

seesea2517

回复 37# cao627


    嗯。你看看 zooyo 版主空间有一个文章有一点相关内容（http://blog.chinaunix.net/uid-10540984-id-3533875.html
），或者搜索 hash 的相关资料研究研究。

cao627

@seesea2517
我觉得hash和不hash是一回事
二分和不二分是一回事
但hash和二分不是一回事


好比
hash，一辆性能好的汽车
不hash，一辆性能不好的汽车
二分，一个驾驶水平好的司机
不二分，一个驾驶水平不好的司机

seesea2517

回复 39# cao627


    精辟，厉害!