Chinaunix

标题: 啊！？ “编程的核心是数据结构,而不是算法”《UNIX编程哲学》里竟然有这句话啊！ [打印本页]

作者: iw1210 时间: 2013-01-18 10:42
标题: 啊！？ “编程的核心是数据结构,而不是算法”《UNIX编程哲学》里竟然有这句话啊！
《UNIX编程哲学》

原则 5:数据压倒一切。如果已经选择了正确的数据结构并且把一切都组织得井井
有条,正确的算法也就不言自明。编程的核心是数据结构,而不是算法 6。

作者: hellioncu 时间: 2013-01-18 10:44
是前提

作者: iw1210 时间: 2013-01-18 10:48

hellioncu 发表于 2013-01-18 10:44
是前提

什么前提？

作者: hellioncu 时间: 2013-01-18 10:51

iw1210 发表于 2013-01-18 10:48
什么前提？

数据组织好是算法的前提，但不是把数据组织好了就一定是好的算法

作者: pmerofc 时间: 2013-01-18 10:54
提示: 作者被禁止或删除内容自动屏蔽

作者: iw1210 时间: 2013-01-18 10:54

hellioncu 发表于 2013-01-18 10:51
数据组织好是算法的前提，但不是把数据组织好了就一定是好的算法

数据结构不好，可以用算法补救？

作者: star_in_sky 时间: 2013-01-18 10:59
正确的数据结构是正确算法的前提条件。

举个极端点的例子：

你用二叉树的数据结构把10个随机数存储起来，然后你用冒泡排序算法来对这10个数进行排序。

这种情况下，你很难正确实现冒泡排序算法。

作者: goldenfort 时间: 2013-01-18 11:02
回复 1# iw1210

这是说常规的，保证能搞出来的算法，如果搞个下围棋的程序，定了数据结构，算法就能很清楚了吗？

对这种算法，是要先搞清楚算法，再搞数据结构

作者: pmerofc 时间: 2013-01-18 11:04
提示: 作者被禁止或删除内容自动屏蔽

作者: windoze 时间: 2013-01-18 11:05
程序的用途就是处理数据，数据当然是最重要的。
数据的描述方式就是数据结构，选择正确的描述方式才是好程序和好算法的前提。

作者: star_in_sky 时间: 2013-01-18 11:17
本帖最后由 star_in_sky 于 2013-01-18 11:25 编辑

回复 9# pmerofc

呵呵，在链表（尽管链表已经排过序了）中使用二分法，确实比较雷人（不过不排除实际情况中，这也是一个无奈的选择吧），虽然不能算错误，但至少是不好的。

不管怎么样，这个例子也是一个鲜活的“反面典型”，相信LZ看了这个例子之后，就会更加明白：正确的数据结构是正确的算法的前提。

其实，反面例子的说服力更强

作者: shan_ghost 时间: 2013-01-18 11:30

pmerofc 发表于 2013-01-18 11:04
给你个真实的例子
http://www.cnblogs.com/pmer/archive/2012/12/08/280 ...

喷了………………………………………………………………………………………………………………

作者: shan_ghost 时间: 2013-01-18 11:35

star_in_sky 发表于 2013-01-18 11:17
虽然不能算错误，但至少是不好的。

这就是错误好不好……

在数组上二分搜索，复杂度是O(logN)；在链表上直接挨个搜索，复杂度是O(N)；在链表上二分搜索，复杂度是O(N*logN)，复杂度直接上了半个级别啊喂～～

作者: star_in_sky 时间: 2013-01-18 11:38
回复 13# shan_ghost

呵呵，不能通过数组ID直接定位元素。

“错误”更加准确

作者: liuiang 时间: 2013-01-18 11:43
这个问题之前论证过的，问题核心在于：如果比较的开销远远大于遍历的开销，那么，基于链表进行二分法不一定就是错误的选择。算法是死的，人是活的。

不过乔的例子则是错误。

作者: shan_ghost 时间: 2013-01-18 11:46
回复 14# star_in_sky

以前没注意看……刚才去看了代码……

关于这个N、log(N)、N(log N)的复杂度，我举个直观的栗子吧：

假设这个N是1024，假设CPU做每次操作（找到元素+比较）要1秒，那么逐个比较最坏就要1024秒；而数组上的二分查找最坏只需10秒（2^10=1024）；链表上的二分查找呢，最坏需要10*1024=10240秒。

而且，这三个数字的差距，随着N的增加还会继续增加……

从10秒到一千多秒到一万多秒——现在，明白复杂度上半个台阶是多么不可容忍之事了吧。

作者: shan_ghost 时间: 2013-01-18 11:48

liuiang 发表于 2013-01-18 11:43
这个问题之前论证过的，问题核心在于：如果比较的开销远远大于遍历的开销，那么，基于链表进行二分法不一定 ...

嗯，同意这个说法。

凑十个字……

作者: shan_ghost 时间: 2013-01-18 11:52
本帖最后由 shan_ghost 于 2013-01-18 11:53 编辑

liuiang 发表于 2013-01-18 11:43
这个问题之前论证过的，问题核心在于：如果比较的开销远远大于遍历的开销，那么，基于链表进行二分法不一定 ...

不过，一般来说，正确的解决方案应该是调整数据结构而不是写这种诡异的算法吧。

甚至，必须用链表存储的话；还可以学数据库，另外建一个数组来索引链表中的每个node；查找可以直接在数组上进行——数据结构是死的，人是活的。

作者: liuiang 时间: 2013-01-18 11:58
回复 18# shan_ghost

那是当然，这种应用基本上很少有。

作者: liuiang 时间: 2013-01-18 12:00
回复 18# shan_ghost

这只是针对专家经常一棍子打死这个一棍子打死那个，而提出来的反例，实际应用场景几乎为0.

作者: cokeboL 时间: 2013-01-18 12:09
就像肉体和灵魂，说谁重要这种话没意义，踏踏实实看那些实际的代码要舒服得多，等你学会了，自然就懂了

作者: freshxman 时间: 2013-01-18 12:56
提示: 作者被禁止或删除内容自动屏蔽

作者: starwing83 时间: 2013-01-18 13:28
回复 9# pmerofc

其实不存在错误的数据结构或者算法，问题是是否适合。

话说，链表做二分，如果思考深一些，倒的确是很精妙的算法呢。（当然不是小乔这种）

曾经@OwnWaterloo向我抱怨过Qt的Map实现居然不是二叉树，而是跳跃表。我想Qt选择跳跃表肯定有自己的考虑吧。跳跃表本身的基本上思想其实就是对链表进行二分搜索的。但是人家显然想得更深：在跳跃表中，会按照一定的间隔（1,2,4,8,16等等）建立所谓的“跳表”，本质上就是缓存了链表二分搜索的结果，从而在常数和复杂度方面都达到了一个很优的结果，实现也比红黑树简单。这就是一个例子。

关键还是在人，是照本宣科还是真心想找合适算法。没有什么东西是不可能的，除非你根本不思考。

作者: ilcyeah 时间: 2013-01-18 13:32
这句话我赞同，结构确实决定算法

作者: shan_ghost 时间: 2013-01-18 13:44

starwing83 发表于 2013-01-18 13:28

从这个角度看的话……其实各种树都可以看作是“绑定了索引数组”的链表……

所以关键是绑定索引数组这一步，而不是对链表查找这一步。

或者说，算法和数据结构是两条腿，要走路得两条腿都动一动，不能只迈一条腿。

作者: pmerofc 时间: 2013-01-18 14:38
提示: 作者被禁止或删除内容自动屏蔽

作者: pmerofc 时间: 2013-01-18 14:54
提示: 作者被禁止或删除内容自动屏蔽

作者: fender0107401 时间: 2013-01-18 15:10
数据结构定了以后，才能去定算法。

数据结构定了以后，算法也基本上就出来了。

当然，设计数据结构时，脑子里面要想着相关算法的就算复杂性以及实现的难以程度。

作者: pmerofc 时间: 2013-01-18 15:34
提示: 作者被禁止或删除内容自动屏蔽

作者: fender0107401 时间: 2013-01-18 15:50

pmerofc 发表于 2013-01-18 15:34
同意
从另一方面说
当算法复杂无比或别扭异常的时候

我感觉设计数据结构就是为了降低计算复杂性。

作者: fender0107401 时间: 2013-01-18 15:50

pmerofc 发表于 2013-01-18 15:34
同意
从另一方面说
当算法复杂无比或别扭异常的时候

或者说主要目的是降低计算复杂性吧。

作者: shan_ghost 时间: 2013-01-18 17:04

fender0107401 发表于 2013-01-18 15:50
我感觉设计数据结构就是为了降低计算复杂性。

同意。如果计算复杂性和设计复杂性不冲突的话……

作者: flyingwalf 时间: 2013-01-24 17:55
有句话叫做“数据善置，算法自成”

作者: iw1210 时间: 2013-01-24 18:53

flyingwalf 发表于 2013-01-24 17:55
有句话叫做“数据善置，算法自成”

有道理～

作者: file3 时间: 2013-02-16 11:01
所有的程序不就是用数据来控制行为方式嘛！这些数据传过来传过去，转成各种各样的方式，格式。其实就是数据来控制行为方式。

作者: freshxman 时间: 2013-02-16 11:12
提示: 作者被禁止或删除内容自动屏蔽

作者: freshxman 时间: 2013-02-16 11:16
提示: 作者被禁止或删除内容自动屏蔽

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)