免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: OwnWaterloo

[算法][C]二叉搜索树的两路二分查找 [复制链接]

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-07 21:04 |显示全部楼层
回复 70# starwing83

为何不是指"为何要这样定义",而是指"为何总是在"?"为何区间一定会减少"?

我的原帖里对这两个问题都有说明(而不是显而易见就带过),有具体说明如何划分区间,并且:
前者是分了3种情况,说明无论哪种情况,target都在算法选择的那个区间里。
后者是因为每次循环中淘汰的那个区间都不是空区间。

也许"区间一定会减少"与"被排除的区间非空"在你看来是一回事。但如果你要说明前者(结论),就必须把后者(原因)给说出来。



就像T a[m][n];中的元素是连续排列的。我觉得这也是显而易见的事。很长时间内都没去想过为什么,直接将它作为结论使用了。
这些都是在心里的解释 —— 知道它是对的,而且太显然了,显然到连"它为什么是对的"的疑问都没产生。
而纸上的解释,推出(而且每一步都是在严格定义下)相连元素的地址差是sizeof(T)是证明元素连续排列的一种方法。

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-08-08 06:03 |显示全部楼层
回复 71# OwnWaterloo


    没……我们方向不一样,你写了个具体代码,当然得说明“为何总是在”神马的。我是提出的这些invariant,也就是说,我根本就没有实现这些算法,只是提出了这些算法的指导方向。我们方向完全是反的。你是先给出算法,然后分情况总结这个算法满足什么性质。我是先给出性质,然后说明满足这个性质的算法一定是对的,然后这个性质就是具体算法的实现参考了。至于怎么写代码能满足所有的这些性质,我是不管的,那是另外一回事了。你是在解释算法,我是在设计算法。你是在有算法的前提下分类提取规律,我是在有规律的前提下设计算法。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-08 07:16 |显示全部楼层
本帖最后由 OwnWaterloo 于 2012-08-08 07:25 编辑

回复 72# starwing83

CU发帖又失败了,幸好发送前手抖了一下按了Ctrl+C。真正的回复看下一帖。

同时下一帖最末尾有一个地方复制引文部分时忘改了。
边界可达到

对应的是
left,right所定义的区间在每次循环中减小

而非
确保循环会在区间减小到1(或者0——看你的需求)时结束。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-08 07:18 |显示全部楼层
starwing83 发表于 2012-08-07 20:04
其实无论upper-bound还是lower-bound或者精确查询什么的,通过循环不变式可以非常非常简单的解释。
starwing83 发表于 2012-08-08 06:03
你是在解释算法,我是在设计算法。


我本来就是在解释算法。
那你到底是在做什么?已经承认不是在解释算法了?至少没法非常非常简单的解释算法了?

我再给你举个例子,关于显而易见/直觉反应。
固定周长下,什么图形的面积最大?非常非常显而易见是圆形。这是直觉反应,也恰好是正确反应。
你可以不加证明的先使用这个结论,但你要解释这个结论本身就不能靠这种显而易见。


starwing83 发表于 2012-08-08 06:03
我是提出的这些invariant,也就是说,我根本就没有实现这些算法,只是提出了这些算法的指导方向。
我是先给出性质,然后说明满足这个性质的算法一定是对的,然后这个性质就是具体算法的实现参考了。

你提出的只是一个"骨架"。不将肉填完整,对错如何说起?
定义一个interface,然后说满足这个interface的代码一定是对的?当然可以这么说,但这是废话。
定义另外的interface/性质,并提供符合要求的实现也一定是对的 —— 对任何interface都可以这么说。
真正有意义的是这个interface本身设计是否是对的 —— 是否是诸多有效、合理设计中的一种。


starwing83 发表于 2012-08-08 06:03
至于怎么写代码能满足所有的这些性质,我是不管的,那是另外一回事了。

怎样才能非常非常简单?当然答案是不做最简单。

starwing83 发表于 2012-08-08 06:03
你是在有算法的前提下分类提取规律,

提取啥?若干情况,说明每种情况都符合定义?这叫规律?
管这叫不叫规律,总之,这就是你不管的那部分。


starwing83 发表于 2012-08-08 06:03
我是在有规律的前提下设计算法。

如前,我不认为你是在解释一个完整的算法

要比我解释得更清晰与简单自然是可能的。
但你想象中的那种非常非常简单的解释,其实不是解释:
要么只是直觉反应而已。就是我前面回复的,只在你心里,不在你的文字中。
要么只是一个框架。

根据后续回复,貌似是后者?
你是在有规律 —— 我怎么闻到一股死套设计模式的味道? —— 的前提下提出一种设计,算法的框架。

那你可以试试,按照你的框架,将完整算法解释清楚是不是一个非常非常简单的事情 —— 这是不是一个设计得很好的interface。


最后,你说那三条其实本质上与我使用的 —— 只是没有循环不变式这么响亮的名字 —— 方法是相同的,它们分别叫做:
starwing83 发表于 2012-08-07 20:04
  - 无论如何循环,middle永远在left和right所定义的区间(根据你的定义,也许是[left, right],也许是[left, right)

递归定义
starwing83 发表于 2012-08-07 20:04
  - 确保循环会在区间减小到1(或者0——看你的需求)时结束。

边界定义
starwing83 发表于 2012-08-07 20:04
  - 确保循环会在区间减小到1(或者0——看你的需求)时结束。

边界可达到

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-08-08 10:13 |显示全部楼层
本帖最后由 starwing83 于 2012-08-08 10:16 编辑

回复 74# OwnWaterloo


    好吧,我以为对着聪明人,有些话不必说全,既然你坚持,我就说全好了= =

所谓循环不变式,是的,就是个interface,它用于两个方面:1. 说明满足这些条件的算法是正确的(必要性)2. 说明按照这些条件可以很容易设计算法(充分性)。

下面详细解释,为了简单,我们以upper-bound为例,lower-bound反之亦然。

upper-bound的定义是:在[left, right)中找到一个合适的值v,并且这个v是所有v的最右边的一个。

为了找到满足这个定义的算法,我们可以给出一系列的限制条件。

1. v一定在[left, right)范围内(由定义可得)。
2. 二分查找一定会结束(由“算法”这个概念的定义可得)。
  2.1. 推论:查找中,每次递归必须收缩范围(因为查找每次递归行为相同,可以一次不收缩,就意味着会永远不搜索,从而导致条件2被违背——反证法)。
  2.2. 推论:查找必须要有一个终结条件(由条件2直接得出)。
3. 我们规定,在最后剩下一个元素的时候(即left == right时),退出查找(由2.2和定义可得)。

通过推论,我们得到了上面的三条invariant。现在我们要保证这三条invariant在每次循环中必须遵守(此为循环不变式)。

接下来分析upper-bound本身的性质:根据二分查找原理和upper-bound定义,当遇到相同的元素时,我们应该选择右半(包含该元素)的部分。
证明:因为遇到了相同元素,我们可知,相同元素一定出现在唯一一个相同元素区间(因为二叉树本身是有序的)。
        那么,我们所求的upper-bound,一定在这个元素的右边,或者就是这个元素(由upper-bound定义可得)。
        结论:我们应该选择该元素的右半部分,并包含该元素。

你看,几乎所有推论都是由定义得的。如果这还不叫简单,我不知道还有什么叫简单。现在我们用得到的四条规律实现一个算法(算法实现),当实现以后,我们说明实现的算法是满足这四条规律的(!!),那么这四条规律的证明过程(如你所见,非常简单)就是对算法正确性的证明。

首先给出最简单的,有序数组查找方法(原因是,这种方式很容易在二分的时候,包含相等元素自身,方便设计,容易看出那四条规律):

  1. int array_upper_bound(int *begin, int *end, int v) {
  2.     while (begin + 1 < end) { /* 当begin + 1 == end时,区间只有一个元素,满足算法结束条件 */
  3.         int *middile = &begin[(end - begin)>>1];
  4.         if (v >= *middle) /* 由第四条规律直接可得。 */
  5.             begin = middle; /* 注意包含了middle本身,选择后半部分 */
  6.         else
  7.             end = middle + 1; /* 注意包含middle本身,选择前半部分 */
  8.     }
  9.     return *begin; /* 退出循环意味着begin,end区间只有一个元素,此即所求元素 */
  10. }
复制代码
对这个算法的说明是,当v不存在时,*begin会返回最接近upper-bound的那个元素,因为下取整的原因,会选择最接近upper-bound的前一个元素。可以根据需要,在最后做一次判定,排除这个情况。当输入的begin == end的时候,区间不存在,返回*begin也应该是违法的,也可以通过判断排除这一条。注意这个算法是直接根据四规律得到的,没有经过任何修饰,是直接翻译,所以可以有更好的等价变换,排除这些不合法情况。

我们很详细的说明了四条指导方针是如何设计算法的。几乎算法的每一条都是由四条方针直接可得。有一条无法表现在算法中,即范围一定缩小。这一条应该标记在int *middle那行,不过位置太小,我写不下,就写在这里好了。

根据结束条件,只有end紧跟begin的时候才会退出,这时会剩余一个元素,在这种情况下,范围不缩小是允许的(直接触发结束条件)。那么,算法范围不缩小也不退出就只会有一个情况,即新计算的end没有紧跟begin,而范围也没有缩小。而这不可能:假设middle等于begin(即if真分支不缩小,begin不变),那end一定等于begin或等于begin+1(由middle计算逆推可得),这时直接触发结束条件;假设middle等于end-1(即if假分支不缩小,end不变),同理可得begin一定等于middle,同样会直接退出。因此算法范围一定缩小,或者直接退出。

现在根据这个数组区间算法,我们直接给出对于二叉树的搜索算法:

  1. int upper_bound(tree *t, int v) {
  2.     while (1) { /* 不同于数组,我们无法在循环条件中保证一定有一个t,除非设置一个parent,见下 */
  3.         if (v >= t->v) { /* upper-bound之附加条件。见数组版upper-bound */
  4.             if (t->right != NULL) /* 保证至少范围内有一个元素 */
  5.                t = t->right;
  6.             else
  7.                return t; /* 否则,返回t本身 */
  8.         }
  9.         else {
  10.            if (t->left != NULL)
  11.              t = t->left;
  12.            else
  13.              return t;
  14.         }
  15.     }
  16. }
复制代码
请注意这个算法并不是数组版本的直接翻译(如果是这样,我们也没必要引入数组版本了)。而是为了让区间至少有一个元素,我们做了很多额外判断。但是所有其他对数组版本的分析这里都适用,我就不再重复一遍了。

注意到,如果t为NULL时,t的父亲一定是满足条件的(t一定有父亲,甚至t是NULL也是这样,而t为NULL代表空集,如果t有父亲,一定是那个满足条件的元素),伴随这个认知,我们每次记录t的父亲,可以避免复杂的判断。


  1. int upper_bound(tree *t, int v) {
  2.     tree *answer = t;
  3.     while (t) {
  4.         answer = t;
  5.         if (v >= t->v)
  6.             t = t->right
  7.         else
  8.             t = t->left;
  9.     }
  10.     return answer;
  11. }
复制代码
上述两个算法依然有v不存在时的特殊情况。如果v不存在,则会返回v应该在的那个地方的左边节点(因为跳出循环的条件是t为空,这意味着我们多往左边查找了一个元素,而这个元素会被返回)。我们同样可以通过判断来排除这些情况。

这样,我们就根据四规律,设计了三个版本的upper-bound算法。我们很轻松地能证明这些算法是正确的。证明正确的过程,就是解释的过程。因此只需要按照上面的逻辑正推一遍,给出设计时的思路,这本身就是对算法的解释。以上,很多证明都是由定义可得,如果忽略,就是我最开始发言的部分。这就是我说简单的含义。哎,非逼着我打这么多字。

顺便说一下,以上所有代码纯粹手写,仅做说明用途,没有经过任何测试,请测试后再使用。

最后提一下,四个规律很容易可以写成assert嵌入到代码里面,这可以更强地保证代码的正确性,这也是循环不变式(上面所有推导过程的核心思路)的实际应用之一——这总用不着我再举例了吧= =

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-08 18:11 |显示全部楼层
回复 75# starwing83

starwing83 发表于 2012-08-08 10:13
你看,几乎所有推论都是由定义得的。如果这还不叫简单,我不知道还有什么叫简单。现在我们用得到的四条规律实现一个算法(算法实现),当实现以后,我们说明实现的算法是满足这四条规律的(!!),那么这四条规律的证明过程(如你所见,非常简单)就是对算法正确性的证明。

定义/规律(那3还是4条东西)是简单的;如果算法满足了那几条规律,那证明算法正确性也是简单的 —— 这就是你想说的?同样是废话。
interface要是没有这样的作用,谁会去用?

问题是如何说明算法满足了规律,如何说明实现满足了接口?这不可能是非常非常简单的事。
starwing83 发表于 2012-08-08 10:13
哎,非逼着我打这么多字。

体会到了么?


并且,作为指导方针的interface我也在用,只是另外一套。
我不喜欢套用他人的东西 —— 这点你应该了解我的脾性 —— 至少,翻看答案之前得先自己给出一个解,否则寝食难安。
既然我给出的解与"标准"答案基本相同 —— 要说区别,也只是functional与imperative的区别 —— 我不觉得有改进的必要。

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-08-09 00:50 |显示全部楼层
回复 76# OwnWaterloo


    很明显用标准的算法分析(循环不变式,算法导论详述的)会更简单一点,至少比野路子清晰,以前玩acm都是这套理论…

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 01:06 |显示全部楼层
starwing83 发表于 2012-08-09 00:50
很明显用标准的算法分析(循环不变式,算法导论详述的)会更简单一点,至少比野路子清晰,以前玩acm都是这套理论…


标准那到是。但"明显"、"简单"、"清晰"却明显 —— 我也来随口说说看,貌似不会上瘾啊? —— 是在自说自话。
递归也是野路子了,我该说什么好。。。

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-08-09 01:13 |显示全部楼层
回复 78# OwnWaterloo


    递归不是野路子,可是拿实现手段做算法分析…这个…

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 01:14 |显示全部楼层
回复 79# starwing83

你家的算法分析是只给个大纲的?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP