免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2012-08-09 14:18 |显示全部楼层
回复 89# OwnWaterloo


    也许是我没用你理解的方式说,问题是你完全忽视掉了重点。

重点是什么?重点是,你考虑的是每一步怎么样,你得分析每一步会出现什么情况,于是得画图,得画出每一步的图。而循环不变式不是这样。

循环不变式是呵呵说的那样,或者更精确的说,是呵呵说的反面——只要保证一次迭代是正确的,那么所有的都是正确的。因此我不需要分析第一步第二步第三步乃至于边界条件,我只需要说明:1. 算法在第1步是正确的,2. 如果算法在第N步是正确的(进入循环条件),那么在满足某些条件后,算法在N+1步也是正确的(循环不变式)。3.算法一定会中止。那么算法就一定是正确的。我为什么在代码里面写注释?你完全没有明白这和你的画图和你所谓的“显而易见“有什么区别——你的解释是O(n)的,你必须解释每一步,每一种分支的末尾的临界情况,我只需要解释O(1),解释一个循环中的情况,加上对循环不变式的解释,这不是数量级的不同么?

很多算法的证明是详细地说明所有的边界情况,然后说明正确性。循环不变式的方法是证明算法在任意时刻都是正确的,自然包含了边界情况,以一对万物,这难道不是数量级的不同?

所以,最终的问题不是functional还是啥,跟这个完全没关系。循环不变式跟势能分析跟复杂度分析一样,是一种算法分析手段,它本身的目的,就是为了简化解释,而且他也的确简化了解释,我就是要说明这个。这是自然分析和算法分析的区别,而跟函数式啥的没什么关系。

论坛徽章:
0
发表于 2012-08-09 15:20 |显示全部楼层
算法果然很难理解。。。。

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

>> 由于始终保证 right-left>=0,且 只要right-left>0,则每次迭代会使 right-left 减小,且right-left==0时结束。
对啊,但是要说出来而不只是闷在心里啊。每一步的逻辑推导都必须展现出来,而不只是在脑海里跳过就完了。
如果说算法导论有省略什么的, 1) 也许被省略的部分在之前已经提过了 2) 也许被省略的部分不是这个章节的重点。
但这个楼的重点就是二分,将这些推理步骤省略了是闹哪样。。。

还有,这是对数组的,对树没有 mid = (right-left)/2 一说。


>> 一开始答案在[left,right)里,每次排除掉的一定不是答案,因而结果一定还在[left,right)里。如果停了 ... 显然肯定是答案。
如果加粗部分是正确的,整个推理就连上了。可是这部分被省略了。。。

不是有各种关于二分查找的传闻吗?算法提出后首个无bug的实现是在若干年之后,现今只有10%的程序员能在短时间内写出无bug的二分查找。
【可能是《编程之美》、《代码珠玑》之类的书里有提,不记得了】
我觉得原因之一就是因为这算法太明显太明显了,于是轻敌了,于是细节就被忽略了。这我在顶楼就吐槽过了。

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

重点是什么?重点是,你考虑的是每一步怎么样,你得分析每一步会出现什么情况,于是得画图,得画出每一步的图。而循环不变式不是这样。

循环不变式是呵呵说的那样,或者更精确的说,是呵呵说的反面——只要保证一次迭代是正确的,那么所有的都是正确的。因此我不需要分析第一步第二步第三步乃至于边界条件,我只需要说明:1. 算法在第1步是正确的,2. 如果算法在第N步是正确的(进入循环条件),那么在满足某些条件后,算法在N+1步也是正确的(循环不变式)。3.算法一定会中止。那么算法就一定是正确的。我为什么在代码里面写注释?你完全没有明白这和你的画图和你所谓的“显而易见“有什么区别——你的解释是O(n)的,你必须解释每一步,每一种分支的末尾的临界情况,我只需要解释O(1),解释一个循环中的情况,加上对循环不变式的解释,这不是数量级的不同么?

解释是O(n)的?你家递归是从f(n)一直解释到f(0)的?你开什么玩笑!
争论丧失风度我觉得没什么,但争论到丧失逻辑了我真不想理你了。

画图与显而易见的区别就是画图能直观上显示k与区间的关系,以及如何正确选择下一区间 —— 这是二分最容易错的地方。


starwing83 发表于 2012-08-09 14:18
很多算法的证明是详细地说明所有的边界情况,然后说明正确性。循环不变式的方法是证明算法在任意时刻都是正确的,自然包含了边界情况,以一对万物,这难道不是数量级的不同?

你又开始瞎扯了。这是在欺负我不懂?你真以为我不懂这货?连算法导论都没看过?
这和你前面的发言对得上吗? 不要把逻辑都丢了啊。。。


starwing83 发表于 2012-08-09 14:18
所以,最终的问题不是functional还是啥,跟这个完全没关系。循环不变式跟势能分析跟复杂度分析一样,是一种算法分析手段,它本身的目的,就是为了简化解释,而且他也的确简化了解释,我就是要说明这个。这是自然分析和算法分析的区别,而跟函数式啥的没什么关系。


递归不是简化解释的手段、递归不是简化解释的手段、递归不是。。。 默念10次,我还是不信你的话诶?

当然有关系。因为functional更倾向于用递归描述,而imperative更倾向用循环描述。
对此问题两者差不多,按sicp的说法,两者的shape是一样的,一个是linear recursive process另一个是linear iterative process。
对非linear的,递归还是能描述。

论坛徽章:
0
发表于 2012-08-09 18:23 |显示全部楼层
回复 94# OwnWaterloo


    我去 .. 你们一个在码代码 一个在证明 这也能争出方法优劣?

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

O(n)你是在说"可见区间总是在这5种形态之内转换。"这一段?

1. 这也不是O(n)的
无论树的节点是多少,都是在这几种形态之间转换,你说这段描述是O(1)还是O(n)?

2. 如果你觉得这段没必要,可以砍掉。
"最后, 无论是 lower_r 还是 upper_r , 每次折半并排除掉的都不是空区间:" 这与你的证明方法是类似的。

3. 对树
如果只是数组,我觉得上面的每次排除掉的不是空区间,就够了。因为数组的形状很容易想象。
但对树,我不知道这一步(形态的转换)是否必要。即使它不必要,也可以给一个直观印象。 就像网络上很多算法的动态化表示。
只是这是纯文本,我已经尽力了。


排除一开始的吐槽,对两路与stl的简介等等。与你提供相同信息量的部分就只有定义lower的含义,以及如何用lower本身去实现这个含义。
这种思想够简单吗? 够通用吗? 但值得我开个楼去说吗?

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

喂,码代码与证明都是我在做好吗?

就像前面回复你的,那些逻辑断链如果补上了,绝对不可能是非常非常简单的事情 —— 一开始就是在吐槽这个。

后来似乎他不是为了证明这个算法本身,而是提出一个证明算法的元算法/思想。虽然这已经跑题了,但没关系,我不在乎这些。
我在乎的是,递归这种元思想不比循环不变式差啊? 缺的就只是一个响亮的名字而已。
非得用循环不变式? 只有他才看过算法导论? 不是吧?
我也看过啊,我也知道这玩意啊,只是不记得这个术语出自哪里而已。 不信看65楼。

于是我真不知道他到底在纠结什么。。。

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2012-08-09 19:14 |显示全部楼层
回复 94# OwnWaterloo


    好吧,说不过你……我其实主要想表达你那一堆东西忘了说明不变在循环算法中的影响神马的…既然都说了我就不争了…(反正也争不过)

歪个楼,刚才维基百科看了看,发现这吖的吧OO和函数式,命令式,逻辑式并列为四大编程style…你有啥感触……

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

光有不变式对说明算法正确性不够,得说明这个不变式如何被满足。
如果省略,只说如果不变式被满足的情况下算法一定正确;那递归天然就隐含类似不变式的思想了。


这吖是指wikipedia?这种划分很早就出现了好吧。。。
这个世界已经被OO污染了。。。 逻辑式没用过,其他三种我认为OO是一种组织代码的方式而已。

OO本身不是毫无可取之处。我烦的是那些只会追求OO的形的家伙,而且这样的家伙也太多太多了,审丑疲劳了都。。。
而且我也越来越怀疑这不是OO的错。即是说,不仅仅OO才会出现这种被它的追随者败坏了名声的事。 functional一样会, 只是functional的追随者不多而已。

比如:
http://c2.com/cgi/wiki?ExpressionProblem

In FunctionalProgramming, you would describe a data type such as:
type Shape = Square of side
            | Circle of radius

Then you would define a single area function:
define area = fun x -> case x of
    Square of side => (side * side)
  | Circle of radius => (3.14 *  radius * radius)


In ObjectOrientedProgramming, you would describe the data type such as:
class Shape <: Object
   virtual fun area : () -> double

class Square <: Shape
   side : double
   area() =  side * side

class Circle <: Shape
   radius : double
   area() = 3.14 * radius * radius


为毛前者要归类在Functional里啊? 如果type set有扩展的可能性, 我不会这么写啊, 可能会用type class之类的。
为毛后者又要归类在OO里啊? 如果type set没有扩展的可能性(性别、比如), 我也可能会用tagged union(variation)之类的东西啊。
而且这种说法不仅仅只是这个页面而已,expression problem有关的诸多论文都是这样起头的。
究竟是我脑袋被门卡了还是他们的脑袋全都被门卡了?

类似的,前不久就在CU有人引用一篇文章,说switch是imperative的,OO应该避免。 是否应该避免也是看问题的,要避免都得避免,关OO啥事啊。
我就不明白了, 到底是我对OO的定义不对, 还是其他人对OO的定义不对。
tagged union那种东西就应该依据定义、无须解释地算在functional里面? 那switch为啥又被算到imperative头上了?


唯一能想到的解释就是:莫非是程序员也依然是笨蛋居多? ╮(╯_╰)╭

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

光对OO吐槽去了,有点忘记说了。

我描述的不是循环而是递归算法 —— 真是这样,没开玩笑 —— 只是写代码的时候顺手把尾调用展开了而已。。。 否则绝对会被吐槽的啊。
尤其是这楼本来就有潜在受众,写成尾递归然后说这能够被优化为循环,肯定会被yulihua49当成小白的啊。那时候再解释就无力了啊。。。


再补充一点学haskell的真实经历。
了解了data(或者functional那群家伙常挂嘴边的algebraic datatype)其实就是enum+struct+union后,第一反应就是

  1. data Shape a = Circle a | Square a ...
  2. data Exp = I Int | S String ...
复制代码
这样的代码是对修改封闭的。 如果Shape, Exp是扩展的,肯定不能用这个。

于是真不能理解为什么这会被归类到functional programming里去。。。
algebraic datatype确实是只有许多被归类为functional programming的语言才提供了的。
但不是仅有algebraic datatype一种东西可以用啊, 也不是说functional programming language普遍提供的特性就应该被归类到functional programming这种paradigm啊。。。
这让那些ansi c oo —— 不是批评、但也肯定不是夸奖 —— 的人情何以堪。。。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP