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

作者: , 共 481 字

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

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

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

拿不准就穷举

Q. E. D.

类似文章:
理论计算机 (I) 课上讲的一个问题,很有意思。
编程 » Java, Matlab
Matlab 2008b 才开始引入 containers.Map ,这是 Matlab 唯一的数据结构 ( 这里的数据结构是指自带一定逻辑性的数据结构,不包括普通数据类型 )。如果要有其它,比如 Queue、Set 等数据结构,只能自己编写一个。File Exchange 上有不少人做过这个工作,我也写过 Queue、List、Vector 的 Matlab 对象 。不过 Matlad 的面向对象编程效率极低,这种方法只能用于不太注重效率的场合。解决这个问题的另外一个方法是使用 Java 对象。
前面 已经提到了显示中大多数难解问题问题最后都被证明是 NP- 完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在 这篇文章 提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本 On the graph isomorphism problem
编程 » Baidu, Google, IT评论
Google 更懂中文我拿不出什么确切的证据(虽然我已经这样认为),但下面的数据是否能说明 Google 确实更懂 阅微堂 呢?