《编程珠玑》—笔记。浏览此文，一窥此书。

第一章：

磁盘排序：对于一个提出的问题，不要未经思考就直接给出答案。要先深入研究问题，搞清楚这个问题的特点，依据这个特点，可能有更好的解决方式。

 

比方：文中：最初的需求仅仅是“我怎样对磁盘文件排序”。

我们首先想到了经典的归并排序。

但，进一步了解到排序的内容是10000000个记录，每条记录都是一个7位整数，且仅仅有1M可用的内存。每条记录不同样。

 

【位示图法，详见我的关于排序的博文】

 

第二章：

三个问题：

1、给定一个包括32位整数的顺序文件，它至多仅仅能包括40亿个这种整数，而且整数的次序是随机的。请查找一个此文件里不存在的32位整数。在有足够内存的情况下，你会怎样解决问题？假设你能够使用若干外部暂时文件但可用主存却仅仅有上百字节，你会怎样解决问题？

 

若内存足够用则可用位图方式。

若内存不够用，可用二分查找的方式。

  

2、将一个具有n个元素的一维向量向左旋转i个位置。比如，如果n=8，i=3，那么向量abcdefgh旋转之后得到向量defghabc。你仅仅能使用1字节的辅助变量。

 

先将向量abcdefgh逆序，得到hgfedcba，再以后i个位置为切割，hgfed和cba分别逆序，得到defghabc

  

3、给定一本英语单词词典，请找出全部的变位词集。比如，由于”pots” “stop” “tops”相互之间都是由还有一个词的各个字母改变序列而构成的，因此这些词相互之间就是变位词。

 

将词典中的每一个单词都进行签名，这样同一变位词类中的单词会具有同样的签名，然后将具有同样签名的单词归拢到一起。

签名：通过计数表示字母反复次数的方式给出。（比如：”mississippi”的签名可能是”i4m1p2s4”）。

然后以签名为键进行排序，把具有同样签名的单词挤压到一行。

 

第三章：数据结构程序

表单字母编程：

比如：

当你登录到一个购物站点，其会弹出例如以下页面：

作为一个程序猿，你应该意识到计算机从数据库中查询你的姓名并取回了相关数据。

可是程序该怎样精确地从你的数据库记录中构建那个定制的Web页面呢？草率的程序猿可能非常想像以下那样開始编敲代码：

更好的方法就是编写一个依赖于以下这种表单字母模式的表单字母生成器：

表示法$i表示记录中的第i个字段，所以$0表示姓，等等。以下的伪码将解释该模式。

（这段伪码假定字母$字符在输入模式中写为$$）

read field from database
loop from start to end of schema
    c= next character in shema
   if c != '$'
       printchar c
   else
       c = next character in schema
       case c of
           '$':     printchar '$'
           '0'-'9': printstring field[c]
           default: error("bad schema")

与编写明显的程序相比，编写生成器和模式也许更加简单些。将数据从控件中分离开来能够使你大大受益：假设字母又一次设计，那么能够在文本编辑器中操作该模式。

 

【我思】

构造很多其它更好的数据结构，把数据从代码中分离出来。 你的程序会更短小、精悍、易于维护、易于扩展。

面向过程编程：把数据从代码中抽离出来

面向对象编程：把数据从代码中抽离出来且把处理这个数据结构的专门代码和此数据结构 绑定到一起，组成一个类。

 

—

数据结构对软件的一个贡献：将大程序缩减为小程序。数据结构还有其它很多正面的影响，包含时间和空间的缩减。添加�可移植性和可维护性。

 

程序猿在对空间缺乏无能为力时，往往会脱离代码的纠缠，回过头去凝神考虑他的数据，这样会找到更好的方法。表示法是编程的精华。  ——Fred Brook 《Mythical Man Month》

 

几个原则：

1、将反复性代码改写到数组中。

使用最简单的数据结构——数组——来表示一段冗长的相类似的代码往往能达到最佳效果。

（比如各种if 整合到数组中）

2、封装复杂的结构

当你须要一个复杂的数据结构时，使用抽象的术语对它进行定义，并将那些操作表示成一个类。

3、让数据去构造程序。

使用适当的数据结构去替换复杂的代码，这能够使数据起到构造某个程序的效果。

（在编写代码之前，好的程序猿通常都会通篇理解构建程序时所环绕的输入数据结构、输出数据结构以及中间数据结构。）

 

 

第四章：编写正确的程序

 

断言在程序维护期间非常关键。

 

保持代码的简单性一般是正确性的关键。

 

关于循环不变式：（还可參照《算法导论》插入排序部分）

比如二分查找：

二分查找的关键概念在于我们总是知道假设t在数组x[0…n-1]中的某处，那么它必然在x的某个范围中（我们致力于缩减这个范围）。我们使用简写形式mustbe(range)表示假设t在数组中，那么它必然在range中。

 

初始化range  to 0…..n-1

Loop

         {invariant: must(range) }

         If  range is empty,

      Break  and report  that t  is not in the array

    计算m (range的中间位置)

用m值来缩减range的范围

若在缩减的过程中发现了t目标值，则break，打印出它的位置。

 

本程序的关键部分就是loop invariant，即用{}括起来的部分。有关程序状态的这个断言被称为不变式（invariant），由于每一次循环迭代的開始和结尾它都是真值（true）。

 

l = 0; u = n-1

loop

    {mustbe(l, u) }

   if l > u

       p = -1; break

    m= (l + u)/2

   case

       x[m] < t : l = m+1

       x[m] == t : p = m; break

       x[m] > t : u = m-1

 

程序验证的基本技术是先精确指定该不变式，并在我们编写每一行代码时密切关注以保持该不变式。在我们将算法草图转成伪码时，这样的技术对我们帮助极大。

 

（当循环涉及到影响不变式的语句时，要检測此不变式是否更改。）

 

二叉查找的优化：返回目标数第一次出现的位置。

l = -1; u = n

while l+1 != u

   //invariant: x[l] < t && x[u] >= t && l < u

    m= (l + u) / 2

   if x[m] < t

       l = m

   else

       u = m

//assert l+1 = u && x[l] < t&& x[u] >= t

p = u

if p >= n || x[p] != t

    p= -1

 

 

第五章：构建脚手架

当不得不调试一个深深嵌入到一个大型程序中的小算法时，我有时会使用诸如单步调试那样的调试工具来调试该大型程序。可是，当我像上面那样使用脚手架调试一个算法时，使用printf语句通常实现要更快一些，比起复杂调试工具来说也要更加有效一些。

 

我们使用断言来陈述我们相信某个逻辑表达式是正确的。

 

（这一章就是讲如何写一段小代码来完毕自己主动化測试。 我认为没什么意思，就略了。）

 

第六章：性能透视

程序的加速是通过在若干不同的层次上努力得到的。

算法和数据结构。

算法优化。

数据结构重组。

代码优化。

硬件。

 

（这一章也没有什么有意义的内容。）

 

第七章：封底计算（学会估算，有点意思~）

七二法则：

假定你投入了一笔钱，时间是y年，利率每年是r% 假设r*y = 72，那么大致说来你投入的钱会翻番的。

[比如：]假设你投资1000美元，时间是12年，利息是6%，那么届时你将得到2012美元；而花9年的时间，利息为8%时，投资1000美元，将得到1999美元。

 

一年有3.155*10⁷ 秒。简便的记法是：PI秒是一纳世纪。

 

为补偿我们的无知，在估算规模、成本以及进度时，我们应该保留2或4的系数，以弥补我们在某个方面的缺漏。

 

利特尔法则：

系统中物体的平均数量就是系统中物体离开系统的平均比率和每一个物体在系统中所花费的平均时间的乘积。（假设物体进入和离开系统存在一个整体上的流量平衡的话，出去率也就是进入率。）

简单概况：“队列中的平均物体数量是进入率和平均滞留时间之乘积。”

【比如】

我在地下室中存有150个盛酒容器，每年我都要喝完（和买回）25个容器的酒。请问每一个容器我要保存多少年？

利特尔法则告诉我们用150个容器除以25个容器/年即得到6年。

 

计算机上的应用：

[能够使用利特尔法则定律和流量平衡证明用于多用户系统的响应时间准则]

如果平均思考时间为z的n个用户连接到了一个随意的系统中，其响应时间为r。每一个用户都在思考和等待响应之间循环，所以元系统（由用户和计算机系统组成）中的总计作业数都固定在n上。

这个元系统，其平均负载为n，平均响应时间为z+r，吞吐量为x(按每一个时间单位的作业数度量)。利特尔法则表明n = x*(z+r)，解析一下得到r = n/x – z

 

当你使用封底计算时，一定要回顾一下爱因斯坦的名言：

不论什么事都应该做到尽可能的简单，除非没有更简单的了。

 

 

第八章：算法设计技术

问题：

输入：一个具有n个浮点数字的向量x；

输出：是在输入的不论什么相邻子向量中找出的最大和。

 

O(n²)的解法：

Maxsofar = 0 ;

for i = [ 0, n )   //以i为首的 全部可能序列的sum情况

sum = 0;

for  j = [ i, n )

             sum += x[j]

    maxsofar = max(maxsofar, sum) ; //以i为首的 全部可能序列的sum 的最大值

 

还有一个备选的二次算法是通过訪问在外部循环运行之前就已构建的数据结构的方式在内部循环中计算总和。（把全部的组合计算的结果存储在表中供以后查询。）

 

cumarr[-1] = 0

for i = [0, n)

   cumarr[i] = cumarr[i-1] + x[i]

maxsofar = 0

for i = [0, n)

   for j = [i, n)

       sum = cumarr[j] – cumarr[i -1]

       maxsofar = max(maxsofar, sum) ;

 

//cumarr的第i个元素包括x[0…i]中的各个值的累加和，所以x[i…j]中各个值的总和能够通过计算cumarr[j] –cumarr[i-1]得到。

 

分治算法：

要解决规模为n的问题，可递归解决两个规模近似为n/2的子问题，然后将它们的答案进行合并以得到整个问题的答案。

 

对于此问题，初始问题要处理大小为n的向量，所以将它划分为两个子问题的最自然的方法就是创建两个大小相当的子向量a、b。然后我们递归找出a和b中元素和最大的子向量，我们称之为m_a和m_b

在整个向量中最大总和的子向量要么整个在a中，要么整个在b中，或跨越a和b之间的边界。我们将跨越边界的最大值称为m_c。

这样我们的分治算法将递归计算m_a或m_b，并通过其它的方法计算m_c，然后返回三个中最大的那一个。

 

float maxsum3(l, u)

   if (l > u)  //0个元素

       return 0 ;

   if (l == u) //1个元素

       return max(0, x[l]) ;

 

    m= (l + u)/2

   //找穿越左右的左半部分的最大和

   lmax = sum = 0

   for (i = m; i >= l; i–)   //全部以中间m为终点的数链和 最大的

       sum += x[i]

       lmax = max(lmax, sum) ;

 

   //找穿越左右的右半部分的最大和

   rmax = sum = 0

   for i = (m, u]       //全部以中间m为起点的数链和 最大的

       sum += x[i]

       rmax = max(rmax, sum)

 

   return max(lmax+rmax, maxsum3(l, m), maxsum3(m+1, u))

 

扫描算法

它从最左端開始，一直扫描到最右端(x[n-1])，记下所碰到过的最大总和子向量。最大值最初是0。前i个元素中，最大总和子数组要么在i-1个元素中，要么截止到位置i。

 

maxsofar = 0

maxendinghere = 0

for i = [0, n)

   maxendinghere = max(maxendinghere + x[i], 0) 

   maxsofar = max(maxsofar, maxendinghere)     //记录下到i的最大子数组和

 

//在该循环的第一个赋值语句前，maxendinghere包括了截止于位置i-1的最大子向量的值；赋值语句改动它以包括截止于位置i的最大子向量的值。

 

几个重要的算法技术：

保存状态，避免又一次计算。 

O(n²)算法和扫描算法，使用了简单的动态编程形式。通过使用一些空间来保存各个结果，我们就能够避免因又一次计算而浪费时间。

 

将信息预处理到数据结构中

比如上面O(n²)算法中的cumarr结构同意对子向量中的总和进行高速计算。

 

分治算法

 

扫描算法：

有关数组的问题常常能够通过询问“我怎样能够将x[0…i-1]的解决方式扩展为x[0..i]的解决方式？”的方式得到解决。

 

累积：

比如上面O(n²)算法使用了累积表，在累积表中，第i个元素包括x中前i个值的总和。

在处理范围时，这一类非经常见。

  

第九章：代码优化

绘制程序轮廓，确定每一个函数须要花费的时间。

 

研究内存分配程序。调用malloc函数，代价较大。

且调用malloc分配结点，每一个结点要多消耗一些字节。

所以我们能够自己申请一段空间，自己管理内存分配。（比如伙伴算法），这样，分配的结点都在这段空间中，有利于利用缓存。且节省空间。

 

 

应用缓存原理：

訪问最频繁的数据訪问起来也应该最廉价。

 

若我们经常调用malloc函数，将最经常使用类型的空暇记录捕获在一个链表中。以后在处理常见的请求时，就能够高速訪问那个链表而不需调用通用的内存分配程序。这可大幅提高效率。

 

·假设某个程序将时间主要花费在输入输出之上，企图加速该程序中的计算将是毫无价值的。在现代的体系结构中，有这么多的周期花在訪问内存上时，企图降低计算时间相同是毫无用处的。

 

将循环展开

在现代的机器中将循环展开有助于避免流水线堵塞，降低分支，添加�指令级的并行。

 

====

 

第十章：压缩空间

表示稀疏矩阵：

使用一个数组表示全部的列，使用链表表示给定列中的活动元素。

这样，比用二维数组表示节省非常多空间。

 

还要注意，即使数组接触的数据比链表要多，它们也要更快，这是由于它们的顺序内存訪问和系统快速缓存之间交互作用时效率更高。

 

对于很多跨网络的程序来说，“保存，不进行又一次传输”，有时我们能够通过本地缓存方式降低须要传输的数据量。

 

第11章：排序

关于排序，我的博客中讲的更详尽。

 

第12章：抽样问题

不认为有什么实际用处。略。

 

第13章：查找

假设事先知道集合的大小，那么数组这样的结构来比較适合实现集合。由于数组是有序的，所以能用二分查找建立一个执行时间为O(logn)的成员函数。

 

简单的二分查找树避免了STL所使用的复杂的平衡方法，因此，它会略微快一些，同一时候使用的空间也更少一些。

最重要的是它一下子就分配全部的结点。（自己管理分配）这就大大减少了树的空间需求，执行时间减少了。

（在二分查找树中使用定制的内存分配，将空间减小了3倍，时间降低了2倍。）

 

 

第14章：堆

关于查找和堆，我的博客中讲的更详尽。

 

 

 【后话】

《编程珠玑》名气非常大，可是其内容比較散乱，且有些章节讲述方式比較乏味，我从书中提取了我觉得是基本的干货，没时间读此书的朋友能够浏览一下 以看大概。

 （这书的风格不适合我，我个人还是喜欢中规中矩的解说比較系统的书^_^）