随笔-19  评论-21  文章-0  trackbacks-0
     读的过程真是一种享受。看到好的代码,好的思想,总会忍不住默记几遍。

     看到觉得有点意味的地方最好多想想来龙去脉,想想为什么,因为紧接着的会是令人惊喜的解说。 多写写书上的代码,感觉不错(写完以后感觉忘了很久的算法又重新回来了)。 每章的“原理”部分是高度性的概括,"习题"是很好的,促使你去思考,做习题是很有必要的,不想“浪费”时间去“做习题”了的结果可能是以后会用更多的时间才能想清这些问题,还有不要只想着看答案,你会很失望,因为有些题目是没有答案的 :)  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
     
*= 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 阅读(469) 评论(0)  编辑 收藏 引用 所属分类: Read the book

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理