queensf
总版主
总版主
  • 注册日期2003-12-04
  • 发帖数735
  • QQ
  • 铜币3枚
  • 威望0点
  • 贡献值0点
  • 银元0个
阅读:3149回复:3

数据结构学习(C++)续——查找(搜索)【1】

楼主#
更多 发布于:2004-05-10 22:21
<P ><FONT size=3>相信每个人都曾感受过找东西的痛苦,大多数人也感受过计算机参与资料管理后所带来的便捷,而学过编程的也曾为了某个问题(比如实现“如果不存在则加入”这样的算法描述——排列组合算法的初级阶段)而实现过查找。在SGI-STL的stl_algo.h里面有这样一段代码:</FONT></P>
<P ><FONT size=3>template <class _InputIter, class _Tp></FONT></P>
<P ><FONT size=3>inline _InputIter find(_InputIter __first, _InputIter __last,</FONT></P>
<P ><FONT size=3>                       const _Tp; __val,</FONT></P>
<P ><FONT size=3>                       input_iterator_tag)</FONT></P>
<P ><FONT size=3>{</FONT></P>
<P ><FONT size=3>  while (__first != __last ;; !(*__first == __val))</FONT></P>
<P ><FONT size=3>    ++__first;</FONT></P>
<P ><FONT size=3>  return __first;</FONT></P>
<P ><FONT size=3>}</FONT></P>
<P ><FONT size=3>这个应该能代表我们曾经写过的所有顺序查找代码,关于为什么写成了这个样子,《C++沉思录》第17章有详细的说明。或许VC6的STL代码更容易理解些:</FONT></P>
<P ><FONT size=3>template<class _II, class _Ty> inline</FONT></P>
<P ><FONT size=3>       _II find(_II _F, _II _L, const _Ty; _V)</FONT></P>
<P ><FONT size=3>       {for (; _F != _L; ++_F)</FONT></P>
<P ><FONT size=3>              if (*_F == _V)</FONT></P>
<P ><FONT size=3>                     break;</FONT></P>
<P ><FONT size=3>       return (_F); }</FONT></P>
<P ><FONT size=3>要是这样就完事了该多好,但是,上面的代码只是对于无规则数据的通用查找方法,如果我们想更快,就必须给数据排列添加规则,这样我们就能利用规则来提高查找效率。O(n)和O(logn)毕竟是不能同日而语的,更不要提O(1)了。</FONT></P>
<P ><FONT size=3>正是人们对于速度的追求才导致了这一部分由上面的3行代码变成了庞大无比的一大系算法(其实这也是不得以的事情,5分钟的等待就足以令一个人发狂了)。对于速度的明显提高是建立在n很大的基础上的,这样就不得不涉及到外存,你可以看到,下面的很多演化是因为外存的介入,如果不注意这点,常常会对我们所做的努力感到疑惑。</FONT></P>
<P ><FONT size=3>回忆一下查英汉字典的过程,将有助于我们发现一些查找策略——理论来自于实践,好像不会再有人对这句话有异议了吧?</FONT></P>
<P ><FONT size=3>首先,字典的正文是字典有序的(这个提法有些古怪,和字典的排序方法一样的称作字典有序,然后我又说字典是字典有序的——反正查字典的人都明白字典是怎么排序的,我就不解释了),因此,有些英汉字典没有目录——只要前言和附录不是太多,一般都不会有目录——实际上我们查字典也通常不用目录。具体怎么查呢?</FONT></P>
<P ><FONT size=3>大体上翻一下——a打头就少翻点,p打头就多翻点——如果当前页的末单词(一般来说在页的右上角的单词)排在所查单词的前面,就往后翻——翻多少页自己估量——如果当前页的首单词排在所查单词的后面,就往前翻——翻多少页自己估量。重复这个过程,直到所查单词位于当前页的首末单词之间,然后在当前页查找——这个过程也可以前后比较,但通常都是从前向后搜索一遍。</FONT></P>
<P ><FONT size=3>回忆这个过程,我们能得到很多启示,首先就是“折半查找”思想。</FONT></P>
<H3 ><FONT size=5>折半查找</FONT></H3>
<P ><FONT size=3>当前值大于所查值就往前搜索,小于就往后搜索,这是折半查找的基本思想。想当年曾经为这个算法花费了不少脑细胞,看来还是我太笨的缘故:</FONT></P>
<P ><FONT size=3>int binfind(int a[], int N, int x)</FONT></P>
<P ><FONT size=3>{</FONT></P>
<P ><FONT size=3>       int low = 0, high = N - 1, mid;</FONT></P>
<P ><FONT size=3>       while (low <= high)</FONT></P>
<P ><FONT size=3>       {</FONT></P>
<P ><FONT size=3>              mid = (low + high) / 2;</FONT></P>
<P ><FONT size=3>              if (a[mid] == x) return mid;</FONT></P>
<P ><FONT size=3>              if (a[mid] < x) low = mid + 1;</FONT></P>
<P ><FONT size=3>              else high = mid - 1;</FONT></P>
<P ><FONT size=3>       }</FONT></P>
<P ><FONT size=3>       return N;</FONT></P>
<P ><FONT size=3>}</FONT></P>
<P ><FONT size=3>没有写成模板形式的,是因为支持折半查找的限制比较多,上面的虽然适用范围很小,但是很容易理解。注意到“查字典”的向前(向后)翻的页数是自己估量的,一个查字典熟练的人和一个生手的差别就常常体现在这里。在计算机里,这个“估量”就是插值。这很容易理解——一本书1000页,怎样快速翻到第300页?很显然,翻到书厚度3/10的地方,当然,这不会很准确,但离第300页已经很近了。这个例子的启示是,在均匀序列里,插值应该是有效的。</FONT></P>
<P ><FONT size=3>int insfind(int a[], int N, int x)</FONT></P>
<P ><FONT size=3>{</FONT></P>
<P ><FONT size=3>       int low = 0, high = N - 1, mid;</FONT></P>
<P ><FONT size=3>       if (x > a[high]) return N;//防止越界</FONT></P>
<P ><FONT size=3>       while (low < high)</FONT></P>
<P ><FONT size=3>       {</FONT></P>
<P ><FONT size=3>              <B>mid = low + (x - a[low])*(high - low)/(a[high] - a[low]);<p></p></B></FONT></P>
<P ><FONT size=3>              if (a[mid] == x) return mid;</FONT></P>
<P ><FONT size=3>              if (a[mid] < x) low = mid + 1;</FONT></P>
<P ><FONT size=3>              else high = mid - 1;</FONT></P>
<P ><FONT size=3>       }</FONT></P>
<P ><FONT size=3>       return N;</FONT></P>
<P ><FONT size=3>}</FONT></P>
<P ><FONT size=3>测试程序</FONT></P>
<P ><FONT size=3>#include <cstdio></FONT></P>
<P ><FONT size=3>#include <cstdlib></FONT></P>
<P ><FONT size=3>#include <ctime></FONT></P>
<P ><FONT size=3>#include "find.h"</FONT></P>
<P ><FONT size=3>#define N 30000</FONT></P>
<P ><FONT size=3>int a[N];</FONT></P>
<P ><FONT size=3>class timer//单位ms</FONT></P>
<P ><FONT size=3>{</FONT></P>
<P ><FONT size=3>public:</FONT></P>
<P ><FONT size=3>       void start() { start_t = clock(); }</FONT></P>
<P ><FONT size=3>       clock_t time() { return (clock() - start_t); }</FONT></P>
<P ><FONT size=3>private:</FONT></P>
<P ><FONT size=3>       clock_t start_t;</FONT></P>
<P ><FONT size=3>};</FONT></P>
<P ><FONT size=3>int main()</FONT></P>
<P ><FONT size=3>{</FONT></P>
<P ><FONT size=3>       timer TIMER; int i, t;</FONT></P>
<P ><FONT size=3>       for (i = 0; i < N; i++) a = 2*i+1;</FONT></P>
<P ><FONT size=3>       TIMER.start();</FONT></P>
<P ><FONT size=3>//     for (i = 0; i < N; i++) seqfind(a, N, rand()%N);</FONT></P>
<P ><FONT size=3>       t = TIMER.time();</FONT></P>
<P ><FONT size=3>       printf("N=%d %dseqfind TimeSpared: %dms\n", N, N, t);</FONT></P>
<P ><FONT size=3>//     printf("%d", a[seqfind(a, N, 2763)]);</FONT></P>
<P ><FONT size=3>       TIMER.start();</FONT></P>
<P ><FONT size=3>       for (i = 0; i < N; i++) binfind(a, N, rand()%N);</FONT></P>
<P ><FONT size=3>       t = TIMER.time();</FONT></P>
<P ><FONT size=3>       printf("N=%d %dbinfind TimeSpared: %dms\n", N, N, t);</FONT></P>
<P ><FONT size=3>//     printf("%d", a[binfind(a, N, 2763)]);</FONT></P>
<P ><FONT size=3>       TIMER.start();</FONT></P>
<P ><FONT size=3>       for (i = 0; i < N; i++) insfind(a, N, rand()%N);</FONT></P>
<P ><FONT size=3>       t = TIMER.time();</FONT></P>
<P ><FONT size=3>       printf("N=%d %dinsfind TimeSpared: %dms\n", N, N, t);</FONT></P>
<P ><FONT size=3>//     printf("%d", a[insfind(a, N, 2763)]);</FONT></P>
<P ><FONT size=3>       return 0;</FONT></P>
<P ><FONT size=3>}</FONT></P>
<P ><FONT size=3>测试结果</FONT></P>
<P ><FONT size=3>N=30000 30000seqfind TimeSpared: 12107ms</FONT></P>
<P ><FONT size=3>N=30000 30000binfind TimeSpared: 40ms</FONT></P>
<P ><FONT size=3>N=30000 30000insfind TimeSpared: 10ms</FONT></P>
<P ><FONT size=3>注意,这个测试里面包含了查找失败的情况,否则简单的顺序查找的性能不会那么差。</FONT></P>
<!--内容结束//-->
喜欢0 评分0
[color=blue][size=4][i][b][u] 【 解决不了的事情,就不要想。世界不会因为我而改变。 】 [/size][/u][/b][/i][/color]
jinyu1123
路人甲
路人甲
  • 注册日期2006-07-05
  • 发帖数67
  • QQ
  • 铜币262枚
  • 威望0点
  • 贡献值0点
  • 银元0个
1楼#
发布于:2007-11-14 01:02
好算法!<img src="images/post/smile/dvbbs/em01.gif" /><img src="images/post/smile/dvbbs/em01.gif" /><img src="images/post/smile/dvbbs/em01.gif" />
迷茫啊! Email : jinyu1123@163.com.
举报 回复(0) 喜欢(0)     评分
liqihu
路人甲
路人甲
  • 注册日期2005-04-26
  • 发帖数62
  • QQ
  • 铜币316枚
  • 威望0点
  • 贡献值0点
  • 银元0个
2楼#
发布于:2007-12-10 23:31
个人的就是最好的,因为自己只能想到那些了。
举报 回复(0) 喜欢(0)     评分
engineerup
路人甲
路人甲
  • 注册日期2007-02-27
  • 发帖数129
  • QQ
  • 铜币450枚
  • 威望0点
  • 贡献值0点
  • 银元0个
3楼#
发布于:2008-01-03 21:47
good info, thanks
举报 回复(0) 喜欢(0)     评分
游客

返回顶部