编程珠玑笔记(1)–开篇

  • 作者在书中经过与友人的讨论后对问题的准确描述
    • 输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。
      输出:按升序排列的输入整数的列表。
      约束:最多有(大约)1MB的内存空间可用,有充足的磁盘存储空间可用。运行时间最多几分钟,运行时间为10秒就不需要进一步优化了。
  • 实现算法:
  • /* prase 1: initialize set to empty */
      for i = [0,n)
        bit[i] = 0
    /* prase 2: insert present elements into the set */
      for each i in the input file
        bit[i] = 1
    /* prase 3: write sorted output */
      for i = [0,n)
          if bit[i] == 1
             write i on the output file
    
  • 原理总结
    • 对小问题的仔细分析有时可以得到明显的实际好处。

      正确的问题。 明确了问题,这场战役就成功了90%。

      位图数据结构。 该数据结构描述了一个有限定义域内的稠密集合,其中的每一个元素最多出现一次并且没有其他任何数据与该元素相关联。即使这些条件没有完全满足(例如存在重复元素或者额外数据),也可以用有限定义域内的键作为一个表项更复杂的表格的索引。

      多趟算法。 这些算法多趟读入其输入数据,每次完成一步。

      时间-空间折中与双赢。 编程文献和理论中充斥着时间-空间的折中:通过使用更多的时间,可以减少程序所需的空间。但我的经验常常是这样的:减少程序的空间需求也会减少其运行时间。空间上高效的位图结构显著地减少了排序的运行时间。空间需求的减少之所以会导致运行时间的减少,有两个原因:需要处理的数据变少了,意味着处理这些数据所需的时间也变少了;同时将这些数据保存在内存中而不是磁盘上,进一步避免了磁盘访问的时间。当然,只有在原始的设计远非最佳方案时,才有可能时空双赢。

      简单的设计。 “设计者确定其设计已经达到了完美的标准不是不能再增加任何东西,而是不能再减少任何东西。”简单的程序通常比具有相同功能的复杂程序更可靠、更安全、更健壮、更高效,而且更易于实现和维护。

  • 使用位逻辑运算实现位向量(习题2)
  • #define BITSPERWORD 32   /* use integer which has 32 bits as vector*/
    #define SHIFT 5
    #define MASK 0x1f   /* the last 5 bits are 1*/
    #define N 10000000
    int a[1+N/BITSPERWORD];
    
    void set(int i){ a[i>>SHIFT] |= (1<<(i & MASK));}
    void clr(int i){ a[i>>SHIFT] &= ~(1<<(i & MASK));}
    int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK));}
    
      上述代码中,a[i>>SHIFT]是第i位在a中对应的整数元素(i右移5位即i除以32);i&MASK取出i的低5位,这5位决定了i在a[i>>SHIFT]中对应的位数。理解这两个量是领悟上述代码的关键。
  • 使用更多空间换取更少的运行时间存在一个问题:初始化空间本身需要消耗大量的时间。设计一种技术,在第一次访问向量的项时将其初始化为0。(习题9)
    • 借助于两个额外的n元向量from、to和一个整数top,我们就可以使用标识来初始化向量data[0..n-1]。如果元素data[i]已经初始化,那么from[i]

      变量top初始为0,下面的代码实现对数组元素的首次访问:

      from[i] = top
      to[top] = i
      data[i] = 0
      top ++
      

      可以看出,top是对当前已初始化的元素的计数;from中记录着data中对应元素的初始化顺序,同时也是对应元素存储在to中的信息的下标索引;如果to中对应元素的信息与元素在data中的下标信息匹配(to[from[i]]==i),则说明已经完成初始化,否则要用上述代码完成初始化。(本习题和答案来自Aho、Hopcroft和Ullman编写的Design and Analysis of Computer Algorithms中的习题2.12。)

      这种数据结构速度并不一定快,而且会额外占用一定存储空间,所以仅在空间很廉价、时间很宝贵且向量很稀疏的情况下才考虑使用。否则,每次访问数据元素都要额外检查是否已被初始化,反而减慢运行速度,适得其反。

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注