读的过程真是一种享受。看到好的代码,好的思想,总会忍不住默记几遍。
看到觉得有点意味的地方最好多想想来龙去脉,想想为什么,因为紧接着的会是令人惊喜的解说。 多写写书上的代码,感觉不错(写完以后感觉忘了很久的算法又重新回来了)。 每章的“原理”部分是高度性的概括,"习题"是很好的,促使你去思考,做习题是很有必要的,不想“浪费”时间去“做习题”了的结果可能是以后会用更多的时间才能想清这些问题,还有不要只想着看答案,你会很失望,因为有些题目是没有答案的 :) ps:有很多面试题来自其中的习题
对一些算法有了更好的理解,也许是看第二遍的原因,也许是从不同的角度看会有不同的效果(
所以好书要多读,每重读一次会有新的收获)。比如:在动态规划算法里,程序可以用递归算法和用表格化方法实现。递归算法的缺点是:有部分值会被重算,解决方法是用一个数组把已经计算过的值存起来,这样就不会重复计算了。表格化的算法是:没有递归算法好理解,解决办法是:在代码开头加个注释,注释就是那几条递归规则,大不了再加上说明“此代码用的是动态规划”。 ps:linux里diff的基本算法就是动态规划吧,感觉和最长公共子串类似,自己实现了一个(
diff.pl)(更新:今天在网上看到了关于diff用动态规划实现的信息:
Dynamic programming Creative Exercises 2 Unix diff, 其源码为
diff.java ,比我的好了N多倍,打印结果的那段代码的思想相当好!代码简洁清淅。另外,我开始觉得用表格化的方法实现动态规划更帅了。 --2011.7.22 )。
读这本书收获很多,列举几个吧:
1. 书里的“
程序验证” 技术很靠谱,让程序看起来清晰易懂,还能从一定程度保证正确性。
2. “哨兵”(
Sentinel value )被几次用到了,感觉还不错,代码看起来更简单了,还能带来一点小小效率。
3. 时空折中与双赢。在原始设计的算法并非最佳方案时,通过改善算法是可以达到双赢的。
4. 用只分配一个较大内存块的方案来替换通用内存分配,这样就消除了很多 开销较大的调用,而且也使用空间的利用更加有效。
5. 数学模型的建立是很重要的。把数a想成用集合[a,a + 1)表示是第9章中二分查找代码调优的核心思想。数组旋转那个算法也实在是太nb了。
6. 一个写得很好的代码,在几个地方看到过,总会忘,这次记下:
链表里有一个哨兵元素,初始时: head = sentinel = new Node(value, 0);
向链表插入元素:
insert(v)
for(p = &head; (*p)->val < t; p = &((*p)->next))
;
if (*p)->val == v
return
*p = new node(v, *p)
下面是我写的:
insert(v)
p = head;
while(p->val < t)
p = p->next
if(p-> val == v)
return
q = node(t,p)
if(p == head)
head = q;
另外,注意到一本书<
算法设计与分析基础> ,用不同的方式讲算法,把算法按其通用程度提出了4个最基本的算法思想:Brute force , Divide & conquer , Decrease & conquer, Transform & conquer。
最后摘录一下 第1版跋 里给的几个建议:
1. 解决正确的问题。 首先彻底理解问题
2. 探索所有可能的解决方案
3. 观察数据
4. 使用粗略估算
5. 得用对称性
6. 利用组件做设计
7. 建立原型
8. 必要时进行权衡
9. 保持简单
10.追求优美
posted on 2011-07-07 20:47
hex108 阅读(470)
评论(0) 编辑 收藏 引用 所属分类:
Read the book