《算法（第4版）》学习总结
algrithm4.jpg
我刚刚用10天时间阅读了《算法》，内心止不住地赞叹，技术书籍也可以写得如此引人入胜，不愧是经典！本文是阅读过程的总结和一些感悟，不求面面俱到，只记录自己有所领悟的地方，希望能给要读这本书的朋友带来一些帮助。
1、从数据的角度理解Java类
int是Java的基本数据类型，它有两个基本特性：
- 它的值是一个固定的整数集合，即-2147483648和2147483647之间的整数
- 对它可以执行5种操作，即+、-、*、/、%
作者指出，这两个特性是所有的数据类型的根本特征，即有一定的值域并且在此值域上可以执行一定的操作。
由此，从数据的角度看，当我们定义一个类时，我们要不是定义了一个静态方法库（类中只有静态方法），要不就是定义了一个抽象的数据类型。
举例来说，我们可以定义如下的Point类
public class Point {
private float x,y;
public Point(float x,float y){
this.x=x;
this.y=y;
}
public float getX() {
return x;
}
public void setX(float x) {
this.x = x;
}
public float getY() {
return y;
}
public void setY(float y) {
this.y = y;
}
public double distance(Point p){
return Math.sqrt((p.getX()-x)*(p.getX()-x)+(p.getY()-y)*(p.getY()-y));
}
}
此时，我们利用基本的数据类型float构建了一个抽象的数据类型Point，它的值域就是{（x,y）|x,y均为float值}，每当我们创建了一个Point类的对象point，我们实际上是获得了该抽象数据类型的一个具体值。可以将它与基本数据类型对比如下：
| 基本数据类型 | 抽象数据类型 |
|---|---|
| int a = 5; | Point point = new Point(1.0,1.0); |
Point数据类型可以执行的操作有setX,getX,setY,getY,distance。
有时候我们定义的抽象数据类型的值域不需要明确地指出，我们更关心能够对这种抽象数据类型进行什么操作，比如我们可以定义一个Stack抽象数据类型，它的任一个对象(即它的一个值)都可以执行两个操作，即pop和push。
为什么我们此时不太关心Stack这种抽象数据类型的值域呢？因为它的值域是无限的。
在Point数据类型中，它的值域由它所包含的两个float数据x和y来确定。在Stack中，它包含的数据实际上是一组数据的集合，这个集合是无限的，所以Stack的值域也是无限的。
像Stack这样的抽象数据类型非常典型，因为它的每一个对象都包含了一组数据的集合，对这个对象的操作实际上就是对它里面的数据集合的操作，作者将这类抽象数据类型称为集合类抽象数据类型。
本书中后面研究的Queue、PriorityQueue、Graph、ST、HashST都是集合类抽象数据类型。这些不同的抽象数据类型的区别在于可以对它们执行的操作不一样。
为了方便高效地实现不同的集合类抽象数据类型的操作，就必须对它们包含的数据的集合进行有效的组织，这就是数据结构的功能。
不同的抽象数据类型需要实现不同的操作，一个合适的数据结构能够让操作的实现非常简单高效。
比如，实现优先级队列这种抽象数据类型，最好的数据结构就是二叉堆；实现一般的队列用链表就很好；实现有序符号表合适的数据结构则是二叉查找树，如果你非要用数组这种数据结构，当然也可以，不过在实现有序符号表相关操作时就会遇到实现上和性能上的困难。
可见，数据结构实际上是集合类抽象数据类型的副产品，是为了方便高效地实现抽象数据类型服务的。
我的思考：由此可以看出，Java作为面向对象的语言，实际上是把数据抽象放在了第一位，然而函数式编程语言却是把过程抽象放在了第一位，这是这两类语言的根本区别。前段时间阅读《计算机程序的构造和解释》一书，第一章就是过程抽象，第二章就是数据抽象。可见过程抽象和数据抽象是编程语言的两大基本功能。Java当然也可以进行过程抽象，只是由于它在设计时优先考虑的是数据抽象，对过程抽象的支持不免就弱了一些，以前可以用匿名内部类，现在可以用Lambda，实际上是增强了对过程抽象的支持。
第一章实际上是全书提纲挈领的一章，需要反复阅读体会，这样会给后面的阅读带来很多的帮助。
2、一个Java对象占多大的内存？
分析一个对象所占内存的大小，基本思路是将复杂的对象简化为基本数据类型，而基本数据类型所占的内存是Java语言预先就定义好的。比如一个int值占4个字节的内存。
所以，要知道一个对象所使用的内存量，需要将所有实例变量使用的内存和对象本身的开销（一般是16个字节）相加。
什么是对象本身的开销？
简单说就是JVM维护的一组关于一个对象的信息，包括该对象属于哪个类、指向该对象的引用信息，该对象的同步信息。
在JVM中，所有的对象引用实质上都是一个内存地址，在64位的机器上，一个内存地址占8个字节，在32位的机器上，一个内存地址占4个字节。
另外，还需要考虑到字节填充，在64位的机器上，内存的使用一般会被填充为8字节的倍数。比如一个Integer对象，它占用的内存包括对象本身的开销16字节，保存的int值4个字节，加起来是20个字节，因为有内存填充存在，JVM实际上会为该对象分配24个字节（其中4个字节是填充字节）。
如果是内部类的对象，相比普通的对象还需要额外的8字节（用于一个指向外部类的引用）
在Java中，一个数组实际上也是一个对象，一个基本数据类型的数组一般需要24字节的头信息（16字节的对象开销，4字节用于保存长度以及4个填充字节）再加上保存值所需的内存。
一个String对象本身总共会使用40个字节的内存，分别是：
- 16字节的对象开销
- 一个指向字符数组的引用占8字节
- 三个int实例变量共需12字节，一个int值描述的是字符数组中的偏移量；一个int值是一个计数器，用来表示字符串的长度，一个int值用来缓存该字符串的散列值
上面三者加起来共是36字节，由于字节填充，会产生4个填充字节，所以是40字节。
一个长度位N的字符串对象除了需要上面的40个字节表示对象本身外，还需要一个长度位N的字符数组，这个数组占用的内存空间是24+2N字节（24指的是数组对象本身的开销，2N表示的是N个字符的内存开销）。所以字符串对象总共需要的内存开销为64+2N字节。
3、排序、查找、图、字符串
本书的2、3、4、5章分别围绕着一个主题进行，每个主题都是由浅入深，层层递进，读来非常舒服。
第2章讲排序
对集合类数据进行的操作中，最常见就是排序操作，它也是许多其他操作的基础，所谓排序，就是将一组对象按照某种逻辑顺序重新排列的过程。
本书中先介绍了两种最基本的排序：选择排序和插入排序，希尔排序是作为插入排序的变型介绍的。
我个人感觉，学习这一章最好的方法是结合visualgo网站的动态演示来学习，非常直观，大大降低了学习难度。
紧接着，作者讲了归并排序和快速排序。这两种算法中都用到了递归，二者的不同之处在于，归并排序是先递归，再归并，而快速排序是先切分，再递归。我认为这部分是本书最出彩的地方，作者分别用了一个小例子，用丰富的图示一步一步地说明了两种算法的运行过程。让人看得大呼过瘾！这些图示的作用比visualgo网站的动态演示还要直观，因为它展示的是函数的递归调用路径，可以让你更深刻地理解递归的本质。
比如，在归并排序中有这样的递归调用代码：
private static void sort(Comparable[] a, int lo, int hi) {
if(hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
作者用一个小例子演示了完整的递归调用路径后，进而告诉我们，sort方法的实质作用是安排多次merge()方法调用的正确顺序，直指问题本质！
快速排序也是一样的精彩！
之后，作者进一步讲解了堆排序，为了讲解堆排序，作者先讲了优先队列。
作者指出，优先队列是一种抽象数据类型，它表示了一组值和对这些值的操作。
我觉得这部分最精彩的地方是它引导你理解数据结构的本质。为了实现优先队列，作者先后选择了无序数组、有序数组、二叉堆三种数据结构，通过比较，进而得出结论，为了更加方便高效地实现优先队列的各种操作，二叉堆是最好的数据结构。
而二叉堆又是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个位置），我们可以通过计算数组的索引在树中上下移动。
我们看到，二叉堆虽然最后也是用的数组存储，但却是与普通数组完全不同的数据结构，这里的关键是对数据的组织，而不是对数据的存储，正是对数据的组织方法不同区分了二叉堆与普通数组。由此，我们可以看到，不同数据结构的本质区别是不同的组织数据的方式。
第3章讲查找
毫无疑问，查找也是我们对数据集合的操作中最常见的一种操作，因此如何实现高效的查找就至关重要。
符号表就是为此建立的一种集合类抽象数据类型，它最主要的目的就是将一个键和一个值联系起来，以便人们能够根据键快速找到相应的值。它最基本的操作有两种：插入和查找。
人们对数据的查找需求可大致分为两类：
一类是有序查找。比如查找一组数据集合中最大值、最小值、第K大的值等等，支持这类查找的符号表叫做有序符号表，使用的数据结构是二叉查找树。
另一类是无序查找，仅仅是根据键查找相对应的值，这类查找需求比较简单，不需要数据集合是有序的，因此人们发明了针对此需求的更加高效的无序符号表，使用的数据结构是散列表。
这一章给我最大的感受就是，让你知道为什么我们需要不同的数据结构。为了实现有序符号表，作者先后使用了链表、有序数组两种数据结构，通过性能分析，发现这两种数据结构实现的有序符号表效率非常低，链表实现的有序符号表插入简单，查找麻烦，有序数组实现的有序符号表插入麻烦、查找简单。二者对比如下：
| 链表实现的有序符号表 | 有序数组实现的有序符号表 |
|---|---|
| 插入简单，查找麻烦 | 插入麻烦、查找简单 |
因此，人们自然希望能找到一种数据结构，能够结合链表和数组的优点，同时又避免它们的缺点，这样的数据结构显然更适合用来实现有序符号表。这样的数据结构就是二叉查找树。
二叉查找树将链表插入的灵活性和有序数组查找的高效性结合了起来！
那为什么又需要2-3树和红黑树呢？
二叉查找树也有自己的缺点，那就是插入元素的特定顺序会影响树的结构，当由于插入元素的顺序造成树的不平衡时，查找的效率也很快下降了！
所以，人们又不得不寻找新的数据结构，这样的数据结构最好是继承二叉查找树的优点，同时它的结构又不受插入元素顺序的影响。这样的数据结构就是2-3树和红黑树，你也可以认为红黑树是2-3树的一种特定实现。
这两种数据结构都是对二叉查找树的改进。可见，人们为了实现高效的插入和查找操作，尝试了链表、有序数组后，开始寻找能高效地支持这两种操作的数据结构---二叉查找树。为了解决二叉查找树的结构受特定元素插入顺序影响的弊端，人们又发明了平衡二叉查找树，典型的就是2-3树和红黑树。
通过这样的学习，你不仅知道了各种数据结构是什么，更主要的是知道了为什么需要它们，也就是知其然更知其所以然。我认为这是本书最有价值的地方！
无序符号表的实现用的数据结构是散列表，散列表的实现有两种方式：拉链式和线性探测式，这部分比较简单。但它给我的启发却是很大的。
那就是，虽然有了有序符号表，可以满足大多数情况下的插入和查找操作，但是当我们的需求更加具体时，比如不需要有序的查找，我们应该努力寻找更加专用高效的数据结构。这也是数据结构的生命力所在。
在Android开发中，有SparseArray这样的数据结构，它就是着眼于Android系统内存有限而专门开发出来的数据结构，这和HashMap针对无序查找是一个道理。
第4章讲图
图自然也是一种抽象数据类型，人们需要它，是因为现实中很多问题都可以归约为图的问题，如航线、道路选择、任务调度，甚至套汇竟然最后都是一个图问题，让我很惊叹！
这部分我觉得比较专，就是说如果你从事的工作与图相关的算法联系不紧密的话，我觉得可以暂时跳过，什么时候需要什么时候读。但是，提前看看作为了解也是不错的，毕竟图的算法都是充满了人类智慧的光芒的！
你会不会看随你，我反正是看了！
第5章讲字符串
这里主要介绍了三种关于字符串的算法，字符串排序、单词查找树和子字符串查找。
实话实说，我觉得这一章没有前面几章看得爽，尤其是子字符串查找算法，讲的让人感觉egg-pain，不过我倾向于认为是翻译的问题（嘿嘿）。不过我查找了两个网址，非常形象生动地向你阐释了Knuth-Morris-Pratt算法和Boyer-moore算法。结合这两个网页学习书上的讲解，绝对让你感觉爽歪歪！两个网址是：
- [Knuth-Morris-Pratt]www.cs.utexas.edu/~moore/best-ideas/string-searching/kpm-example.html
- [Boyer-moore]www.cs.utexas.edu/~moore/best-ideas/string-searching/fstrpos-example.html
拿去不谢！
第6章我没读，但是如果你时间充裕，建议你还是看一看。这一章讨论了与前几章内容有关的若干其他前沿研究领域，包括科学计算、运筹学和计算理论。还有一些其他高级主题。
总体来说，这本书不愧是经典！我觉得是数据结构与算法最好的入门书，没有之一！
