编程的核心是数据结构，而不是算法

zhiqiang二月 28, 2008 计算机科学

Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学:

你无法断定程序会在什么地方耗费运行时间。瓶颈经常出现在想不到的地方，所以别急于胡乱找个地方改代码，除非你已经证实那儿就是瓶颈所在。
估量。在你没对代码进行估量，特别是没找到最耗时的那部分之前，别去优化速度。
花哨的算法在 n 很小时通常很慢，而 n 通常很小。花哨算法的常数复杂度很大。除非你确定 n 总是很大，否则不要用花哨算法（即使 n 很大，也优先考虑原则 2 ）。
花哨的算法比简单算法更容易出 bug 、更难实现。尽量使用简单的算法配合简单的数据结构。
数据压倒一切。如果已经选择了正确的数据结构并且把一切都组织得井井有条，正确的算法也就不言自明。编程的核心是数据结构，而不是算法。
没有原则 6 。

Ken Thompson —— Unix 最初版本的设计者和实现者，禅宗偈语般地对 Pike 的原则4 作了强调：

拿不准就穷举

via: newsmth-algorithm

关于unix, 数据结构, 算法 »

TCS课堂笔记：数据库存储问题理论计算机(I)课上讲的一个问题，很有意思。已经一个n，m和$$\{1,2,\cdots, m\}$$里n个数，设计一种保存这n个元素的表的数据结构形式，使得对$$\{1,2,\cdots...
一个简单图的三染色算法问题注: 这个问题来自China Theory Week 2008的Open Problems Session。我们知道在数学里证明一个东西的存在性的时候，有时候只证明了“存在性”，而且在证明过程...
魔方里的数学今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方，先给每人发了一个。我喜欢这样的教学...
素数筛法的复杂度 Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。所谓素数筛法就是那个求小于n的...
Perfect Shuffle的算法珍爱生命，远离政治。我们继续讨论算法。 2008/04/01补充：此算法有重大缺陷。详情请见留言部分。一年前，我们讨论过一个算法问题，perfect shuffle，...
有序矩阵的中位数算法给定$$n\times n$$的实数矩阵，每行和每列都是递增的，求这$$n^2$$个数的中位数。使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数...
理论计算机初步：算法和计算模型下面是wikipedia上算法的定义：算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算...
算法百科全书 - Encyclopedia of Algorithms Xie Xie推荐了一本今年出版的一本新书，Encyclopedia of Algorithms，全书1200页，涵盖各类有名问题的算法，概率算法，近似算法，量子算法等。翻了一下，...
一个算法面试题 & 面试题库一个面试题，号称是微软的输入$$a_1, a_2, ..., a_n, b_1, b_2, ..., b_n$$，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为$$a_1, b_1, ..., a_n, b_n$$。刚一...
求平方根倒数的算法下面这个求$$1/\sqrt{x}$$的函数号称比直接调用sqrt库函数快4倍，来自游戏Quake III的源代码。 float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*)&x...

12条留言 -> 跳到留言表格

At 2008.02.28 08:43, 伊甸 said:

6.没有原则 6 。
我喜欢这条

[Reply]
At 2008.02.28 10:49, Ryan said:

算法本来就是为了大规模处理某个问题而引入的，在实际的工程中，字符串匹配用蛮力匹配法最好，只要这个地方不成瓶颈就行，以一个务实的态度来看待这个问题:)

[Reply]
At 2008.02.28 13:02, 9npc said:

我同感啊。還是務實點好啊。

[Reply]
At 2008.02.28 16:06, maduoyuan said:

拿不准就穷举
稳定最重要，如果老是让人帮助计算机干活，那就太可怕了。人会成为机器的奴隶。

[Reply]
- At 2008.03.01 11:27, PSKing said:
  
  哈哈，说得很到位啊~！！
  不学算法前，头脑清晰，费力气学完之后，还得按算法的套路来凑，很累啊！
  
  [Reply]
At 2008.02.29 00:06, guang said:

比较有道理，但主要是从实用的角度来说。

优化还是很重要，当然，就像他说的，要找准地方。看看linux操作系统内核，很多地方都很仔细地斟酌了。如果不优化，可能就慢百分之几十。
很多个个环节累加嵌套，这些粗糙的算法就会导致系统慢很多倍。

那些出色的软件，其实都已经经过了非常精心的优化的。当然，性能和稳定性之间的权衡，需要仔细地考虑。

[Reply]
At 2008.02.29 09:37, M said:

转载行否？

[Reply]
At 2008.03.16 10:07, jack said:

写程序这么多年。深刻的感觉数据结构非常的重要，但算法也是非常重要的。还是回学校好。可以专门研究这些内容。在公司里也只能凑货了。

[Reply]
At 2008.09.19 22:41, cuckoo said:

Not agree!

[Reply]
At 2009.01.19 13:05, 胡椒 said:

个人认为，算法不只是为了效率，更是为了正确性。算法是思想，数据结构是算法表现形式的一个方面，我觉得不是一个层面的东西。

[Reply]
At 2009.08.17 17:18, on the road said:

数据结构是静态的，没有算法，数据结构仍是死的。实际上，不能简单的说哪个更重要。当然，定义清晰的数据结构，可以在此基础上写出更好的算法。

[Reply]
At 2009.10.08 14:17, lxj said:

个人认为,数据结构和算法的关系有点像程序和进程:算法是数据结构的动态表现形式;算法是作用于数据结构;算法是基于定义好的数据结构来设计的.

[Reply]