编程珠玑第八章探讨

这一章节给出的问题让人从直觉上判断就是动态规划。不过,本章的分治算法也非常的巧妙,他们的优势都是避免了一些重复计算。动态规划本质也就是对于穷举法的优化。作者在指出这些算法时,由简单到困难的描述了复杂的算法有时能让效率大幅提高。对于O(n^2)的暴力来说,O(nlogn)的分治算法的确印证了这一点。但是O(n)的动态规划却不算复杂,相反,比起暴力他还来的简单些。而除了这道特定的题目以外,其他凡是用到DP的地方都能够反映出动态规划的简洁美,不失为一种优美且高效精巧的解决方案。

Read More

再谈计算机的无上心法

以前说过这个话题,现在看看当时真是肤浅了,首先这个问题挺空的,而且只有当时所诉说的技能很难称之为计算机的无上心法。单说代码实现的无上心法都差强人意,这里面需要的能力不仅仅是抽象,还包括设计。而设计恰恰又是很容易被忽略的,怎样定义一个好的设计我觉得这是因需求和领域而异的。参考艺术界,不同时代所流行的元素和主义在变化,比如最近备受推崇的极简主义。

Read More

编程珠玑第七章探讨

本书的粗略估计看起来肤浅实则非常重要,有些问题不是估着玩的,比如桥梁设计时。本书举出的估计内存的例子,结构体是有对齐的,这样简单的估计是会失准的。还有类似「舍9法」「72法则」「Little定律」这些小技巧,在「安全系数」这一节中,我想起了以前我的做法:比如写线段树的时候,因为写的是静态存储结构的,所以我用结点数乘以四来开辟数组空间,而不是用一个恰好精确的值。

Read More

编程珠玑第六章探讨

这一章的内容刚好让我联想到以前参加过的超算大赛,优化是一个需要从理论层面直到硬件层面多个角度同时考虑的系统工程。作者也提到了设计层面的问题,有时候一个好的设计恰恰能避免很多问题,譬如说遇到一个问题,你看了一眼就开始写DFS,其实那个问题有规律可循,最终可以得到一条优雅的通项公式。

Read More

编程珠玑第五章探讨

本章着重谈论一些小事,测试、调试、计时。说是小事其实也是大事,想想自己曾经为调试一个程序而彻夜难眠的经历吧。这里面又有断言大法的叙述,「在测试时使用断言,而在产品发布时把断言关闭的程序员,就像是岸上操练时穿着救生衣,而下海时将救生衣脱下的水手」。在计时部分,作者展现了老练的洞察力,不过缓存溢出这种错误现在可能少见多了。

Read More

编程珠玑第四章探讨

首先,本章中再次提及了TAOCP,可以说已经是一章提一次的节奏了,作者这么热衷于提到本书还是有一定道理的,详尽的数学证明让我们有值得一读的必要。第四章的主题是如何证明自己的程序是正确的,这是一个比较困难的问题,尤其是逻辑复杂的代码,对于不同的程序周期作者都针对性的提出了不同的方法和原理。比如二分搜索的停机证明,然后对于函数,作者介绍了重要的「契约编程」。其中还谈到了心理问题:「困难」的部分第一次就可以正确运行,而那些「容易」的部分往往会出毛病。所以呢,作者也鼓励使用验证技术开发。觉得本章最重要的应当就是对循环不变式的理解。

Read More

编程珠玑第三章探讨

本章陈述了唯物辩证法的重要性,充分体现了经济基础(数据)决定上层建筑(程序结构)。而且也从侧面展示了语言的重要性,书中一位程序员因为语言的问题,不得不使用了350个变量而不是数组。有两个方法让我很在意:一个是打表大法,我们不必要用程序去产生所有数据,某些数据完全可以提前做好,能够节约大笔开发经费(代码量,时间),这就是打表。第二个就是说我们不要重复造轮子,程序员应当善于使用已有的工具。作者给出了本章标题的真正含义:

Read More

编程珠玑第二章探讨

这一章给出了三个小问题,都非常有趣且实用,分别用来阐述二分法递归与抽象离散化思想。第一个问题可以认为是二分思想的巧妙运用,众所周知通常二分前数据应当是有序的,比如C++中的set或map容器的工作原理,都是维护一棵平衡树;大量常见的数据结构如:平衡二叉树、线段树、二叉堆、堆排序都合理发挥了二分法的威力。第二个问题紧扣主题,有哪些基本操作可以用来解决问题,「看起来很困难的问题也可以有一个简单的、意想不到的答案」。我觉得第二题给出的三个解决方案都很重要,第一个算法是看透了暴力算法的本质,最大限度减少了使用额外空间辅助移动带来的浪费;第二个算法的递归思想很通用也很重要;第三个最为精妙的算法向我们展示了抽象思维的可贵。第三题是一道不错的离散化题目,书中说排序也好,打标识也好都是离散化的体现。所以作者也说:

Read More

编程珠玑第一章探讨

第一章陈述了一个算是在特定领域很好用的方法,中学时上编程课老师给出了这种方法,题目是一串不会重复的数字,最大的数字不会超过某个值,要求排序输出。其实根本不需要真去做排序,当时用Pascal语言的boolean数组很容易就解决了这个问题。也就是跟本章提到的位向量异曲同工。显然如果除了算法与数据结构外其他条件都一样的情况下,线性的算法要明显优于O(NlogN)的基于比较的排序算法。作者给出了问题本质和使用范围:

Read More