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

cao627

@ouiki
一本没有索引的书，有1000页，每一页是你要的不同内容，设翻到任意页的时间为1t,所以你要查看任意一页内容，平均花费时间为500t.

将这本书家加上索引，索引占满一页，这时得到任意页你要的内容的时间为2t.

现在是:将原书每一页的内容拆成十页，原书变成10000页，索引变成10页，得到任意内容的时间变为6t，5t得到索引的平均时间，加1t根据索引值翻到相应页的时间。

那本没索引的1000页的书，用两分法翻的话10次之内一定能翻到任意要的内容，2的10次方等于1024。
所以平均5t就能翻到要的内容

ouiki

回复 21# cao627

高。
学习了。

seesea2517

回复 21# cao627


@ouiki
@cao627

cao627 发表于 2013-04-10 16:26
一本没有索引的书，有1000页，每一页是你要的不同内容，设翻到任意页的时间为1t,所以你要查看任意一页内容，平均花费时间为500t.
将这本书家加上索引，索引占满一页，这时得到任意页你要的内容的时间为2t.
现在是:将原书每一页的内容拆成十页，原书变成10000页，索引变成10页，得到任意内容的时间变为6t，5t得到索引的平均时间，加1t根据索引值翻到相应页的时间。
那本没索引的1000页的书，用两分法翻的话10次之内一定能翻到任意要的内容，2的10次方等于1024。
所以平均5t就能翻到要的内容

有点疑问。
你这个类比相当于是把 IP 的比较类比为页码的比较，根据 IP 得到地址信息类比为翻页。
假设 hash 和二分的方法都已经把数据读入内存（当然实际也是这么做的），那么根据 IP 得到地址的信息即是根据key取值，可以认为速度很快，且只需要一次操作，这个时间忽略。
那么实际的时间都是花费在比较“页码”的操作上，即 IP 地址的比较。

“一本没有索引的书，有1000页，每一页是你要的不同内容，设翻到任意页的时间为1t,所以你要查看任意一页内容，平均花费时间为500t.”
从这一句来看，这个类比其实说的是顺序查找法。这个 t 是一个页码的比较，结论没问题。

“将这本书家加上索引，索引占满一页，这时得到任意页你要的内容的时间为2t.”
这一句指的是将 IP 范围展开，所有 IP 都做成 key 的 hash 表，结论没问题。

“现在是:将原书每一页的内容拆成十页，原书变成10000页，索引变成10页，得到任意内容的时间变为6t，5t得到索引的平均时间，加1t根据索引值翻到相应页的时间。”
这一句和 lz 的设定不符，实际上没有“十页”，只有四页“索引”，每一页索引是要比较的，所以是4t，并且“翻页”时间是不计的，所以以最大比较次数来算，是 4t。
另外算法上做优化，比如有一些 IP 没有四页，所以结果要 < 4t。


“那本没索引的1000页的书，用两分法翻的话10次之内一定能翻到任意要的内容，2的10次方等于1024。所以平均5t就能翻到要的内容”
这个计算我就不在行了，以你的为准 5t。

那么结果是使用 hash 的方法略优于二分法。

cao627

@seesea2517
所有数据在中内存地位都相等。
不会因为你被人称呼为索引，混在其他1000条索引中和混在其他10000条索引中cpu找到你的时间都是一样的。

seesea2517

回复 24# cao627


    这个当然是。
    我说的意思是“比较”这个操作和“取值”这两个操作的时间是不一样的。举例说就是 ip > ip1，ip < ip2 这样的比较操作，找到所到的范围后，用 addr[ip] 这个来进行取值操作。 > < = 这些比较操作在这里是频繁的，而 [] 取值操作是一次处理中只做一次，并且二者时间不一样。取值操作在进行时间复杂度计算的时候，在这个例子中我认为是可以忽略的。
    在用翻书和查索引这个比喻里，翻书你要比较页码，这个是比较操作，找到页码后，你再正式翻开书，这个是取值操作。在你上面的描述我认为这两个操作你没有做区分所以我做了一个补充说明。

cao627

@seesea2517
我忽略比较操作，是因为我同时忽略了对一页索引中每一项的比较操作。
如果将“比较”考虑进去，那么一页索引中有1000个条目，key要和这一千个条目一一比对，才能知道value在第几页了。
难道索引神奇到 给出一个key不用比对就能知道自己在索引中存在还是不存在？

cao627

@seesea2517
这么说吧：
1000页的书，翻到任意页的时间忽略不记，判断一页的内容是你要的内容的时间为1t，所以找到一页内容的时间平均为500t
将书建一个索引。设在这个索引上判断每一项是否指定到你要的内容的时间0.001t（索引判断很快，但不能无休止的快吧，瞎设为快1000倍吧），所以有了索引，1t之内就能找到任意一页的内容。平均为0.5t就能找到内容。
现在是:将原书每一页的内容拆成十页，原书变成10000页，索引条目变成10000条，所以10t之内就能找到任意一页的内容。平均5t就能找到任意内容。
以下省略

索引上的比较比正常页上的比较快1000倍是个假设。对应于模拟 ：用几个or判断key是否在索引中存在花费的时间/读取数组的一项比较是否ip > ip1&ip < ip2 花费的时间的比值

建一个索引，原书页数增加10倍，即索引条目增加10倍，是一个假设。对应于模拟：构建hash表时，将原本占一项条目的ip段，拆成多个条目。

cao627

1. #!/bin/bash
   
2. a=(`seq 1000`)
   
3. for i in `seq 1000`
   
4. do
   
5. star=0
   
6. end=999
   
7. while [ $star -le $end ]
   
8. do
   
9.           mid=$((star+(end - star)/2))
   
10.           ((n[$i]++))
    
11.           if [ $i -lt ${a[$mid]} ];then
    
12.               end=$((mid-1))
    
13.            elif [ $i -gt ${a[$mid]} ];then
    
14.                star=$((mid+1))
    
15.            else
    
16.                #echo "${n[$i]}-- $i" #1--500  2--250 2--750 .....
    
17.                break
    
18.            fi
    
19.   done
    
20. done
    
21. m=0
    
22. for j in ${n[*]}
    
23. do
    
24. ((m=m+j))
    
25. done
    
26. echo $m  

复制代码

最后得到m为8987
因此对于含有1000个元素数组，用2分法查找，平均查找8.987次得到结果。
如果用顺序查找总次数显而易见为500500，平均查找次数为500.5.
但用二分法中每次查找中执行的语句比顺序查找多
按4倍算的话
耗时比在36：500 瞎猜！

expert1

hash是不是要解决一个碰撞问题，还是构造hash函数？
我都忘了hash算法了，不过此贴甚好，可以深入讨论一下，支持一个。

seesea2517

回复 29# expert1


    在 shell 里用关联数组来当作 hash 表不知道效率如何。