首页投稿（暂停使用，暂停投稿）

Algorithms (4th-Edition) Reading

2016-09-02  本文已影响398人  虾米小华

本章开始阅读时间: 2016年8月25日
本章结束阅读时间: 2016年8月31日

注：本人阅读的是英文原版书籍。

本章摘要：第一章用了200+页，但并没有急于进入算法部分。由于全书是通过Java语言来描述算法，所以这一章主要是以Java为例来讲解基本的编程知识，不熟悉Java的同学完全可以将本章作为Java的入门学习材料。读完第一章我的感受是：这本书完全是面向编程和算法初学者，但又不失一定的深度。作者充分考虑了初学者的感受，用了大量的图表帮助读者理解算法的行为，文字描述也非常用心。这本书的配套网站上也有对每章主要内容的概述，读完每一节再利用网站的内容进行复习，效果非常好。

1 Fundamentals

1.1 Basic Programming Models

p.23上列举了几个静态方法的实现，其中素性测试、牛顿法求平方根挺有用，应该理解并记下来。

方法（函数）的一些性质：

递归的三要素：

外部库

p.32上列举的StdRandom库里的几个静态方法很有学习价值，比如洗牌算法shuffle()。我想到的是它可以用在遗传算法种群初始化上~

Binary search

不多说了，经典的不能再经典的算法：

public class BinarySearch {
    public static int rank(int key, int[] a) {
        int start = 0;
        int end = a.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (key < a[mid]) {
                end = mid - 1;
            } else if (key > a[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

在测试p47的BinarySearch时，由于我使用的是IntelliJ IDEA，无法像在命令行里那样通过<重定向输入流，试了在Run/Debug Configurations里设置Program arguments，比如这个语句tinyW.txt < tinyT.txt，tinyW可以读入，tinyT.txt就无法读入。在SegmentFault找到了答案。可行的做法是要手动在获得输入前重定向一下标准输入：

try {
    FileInputStream input = new FileInputStream("algs4-data/tinyT.txt");
    System.setIn(input);
} catch (FileNotFoundException e) {
    e.printStackTrace();
}

需要引入的库：

import java.io.FileInputStream;
import java.io.FileNotFoundException;

常见问题

1.2 Data Abstraction

静态方法和非静态方法的不同

使用对象

抽象数据类型的例子

实现抽象数据类型

数据类型的设计

暂时先跳过。

常见问题

Counter[] a = new Counter[2];
a[0] = new Counter("test");

1.3 Bags, Queues, and Stacks

一些基本概念

泛型(generics) 是一种参数化的数据类型，而不具体指明是哪种。这样可以简化类的实现（否则对每个数据类型都要实现一遍，就很麻烦）。

与泛型联系的概念是基本数据类型的自动封装(autoboxing)和解封装。

Iterable collections 不知道怎么翻译...迭代集？意思就是用迭代器遍历存放对象的数据结构，这是Java语言一种很方便的设计，因为我们在遍历时无需知道对象的具体结构了。很多高级编程语言也支持这种特性。

Bags

FIFO queues

基本的数据结构——先入先出队列。p.126举了一个连续读入整数存入整数数组的例子，就是利用了队列：先从输入流把数据存入队列，于是就可以根据队列大小申请数组大小；再让所有整数出队，并存入数组中。

不过个人感觉这样读入是不是效率低了些...因为有入队和出队的开销。但是好处似乎也是有的，就是不用事先知道有多少整数，而是通过建立队列知道数组要开多大；而如果直接用数组就无法准确知道预分配的大小。

Pushdown stacks

就是我们通常所说的栈。这里指的是“从上往下”压栈的方式，实际中还有“从下往上”压栈的方式。对应的就是大端存储和小端存储？

算术表达式的模拟

p.128讲了如何用栈实现对算术表达式的解析。其实就是用栈模拟递归的一种形式。一个非常简单的算法是Dijkstra前辈于1960年提出来的。基本思想是维护两个栈，一个用来存放运算对象(operand stack)，一个用来存放运算符(operator stack)。从左到右遍历算术表达式，并执行如下操作：

最终operator stack空，operand stack中只有一个运算对象，它就是整个算术表达式的结果。

需要加载的库：

import edu.princeton.cs.algs4.*;
import java.io.FileInputStream;
import java.io.FileNotFoundException;

代码：

public static void expressionEvaluate(String[] args) {
    Stack<String> ops = new Stack<String>();
    Stack<Double> vals = new Stack<Double>();
    // 重定向输入流：从文件输入
    try {
        FileInputStream input = new FileInputStream("tempString.txt");
        System.setIn(input);
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }

    while (!StdIn.isEmpty()) {
        String s = StdIn.readString();
        if (s.equals("("))         {}
        else if (s.equals("+"))    ops.push(s);
        else if (s.equals("-"))    ops.push(s);
        else if (s.equals("*"))    ops.push(s);
        else if (s.equals("/"))    ops.push(s);
        else if (s.equals("sqrt")) ops.push(s);
        else if (s.equals(")")) {
            String op = ops.pop();
            double v = vals.pop();
            if (op.equals("+"))         v = vals.pop() + v;
            else if (op.equals("-"))    v = vals.pop() - v;
            else if (op.equals("*"))    v = vals.pop() * v;
            else if (op.equals("/"))    v = vals.pop() / v;
            else if (op.equals("sqrt")) v = Math.sqrt(v);
            vals.push(v);
        }
        else vals.push(Double.parseDouble(s));
    }
    StdOut.println(vals.pop());
}

上面的处理假定表达式有完整的括号（最外层也有）。其中tempString.txt中即存放所要解析的算术表达式，如( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )，对应输出为101.0；再如( ( 1 + sqrt ( 5.0 ) ) / 2.0 )，对应输出为1.618033988749895。

这个算法的复杂度是O(n)。

Implementing collections

本节讲的是在实现Bag, Stack和Queue之前，先实现一些基本的框架。这个"collections"大概就是对数据结构的一种统称吧，即存储同类对象的逻辑结构。

Fixed-capacity stack

一个非常简单的栈模型，只能存储String，要求用户定义容量，不支持迭代器。

文中说道：

The primary choice in developing an API implementation is to choose a representation for the data.

一个显然的选择是用String数组。用一个数组a[]存放实例变量，用一个整数N统计栈中元素的个数。须满足的特性：

实现：

public class FixedCapacityStackOfStrings {
    private String[] a;
    private int N;

    public FixedCapacityStackOfStrings(int cap) {
        a = new String[cap];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void push(String item) {
        a[N++] = item;
    }

    public String pop() {
        return a[--N];
    }
}

上面的实现就是最简单的栈模型，但是这个实现只是玩具程序，有很多缺点，后面会在这个基础上设计更实用的数据结构。

泛型

在FixedCapacityStackOfStrings的实现中，第一个要改进的地方就是适应所有的对象，而不仅仅是String，即使用泛型。方法是将代码中所有的String改为Item，另外在类名后面加一个后缀<Item>，于是将实现改为如下：

public class FixedCapacityStack<Item> {
    private Item[] a;
    private int N;

    public FixedCapacityStack(int cap) {
        a = (Item[]) new Object[cap];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void push(Item item) {
        a[N++] = item;
    }

    public Item pop() {
        return a[--N];
    }
}

使用了Java中的关键词Item来表示泛型，是用来代表类型的参数。注意创建泛型数组的方式，有一个疑问：为什么不写成a = new Item[cap]来创建数组？书中说这是由于历史和技术的原因导致Java不允许这种方式。所以就有了这种写法：a = (Item[]) new Object[cap]。确实即使是这么写编译器也会警告，只不过我们可以安全地忽略它。我可以把它理解成强制类型转换嘛...而且是强制类型转换成泛型数组...

Array resizing

第二个要改进的地方就是尽量避免用户自己指定内存空间的大小（如果用户申请了很小的内存空间，则可能导致数组越界；而如果申请了很大的内存空间，则可能造成浪费），而是自适应地调整。

实现的思路很简单：当push元素时，将原数组的内容拷贝到一个空间更大的数组；当pop元素时，则将原数组的内容拷贝到一个空间更小的数组。这让我想到了C++里vector的实现，它的动态数组机制也是这样的方式。

首先，把数组的长度扩大为max。其实是将原数组的内容拷贝到另一个长度为max的数组：

private void resize(int max) {
    // N <= max
    Item[] temp = (Item[]) new Object[max];
    for (int i = 0; i < N; i++) {
        temp[i] = a[i];
    }
    a = temp;
}

注意最后一句的引用赋值，a指向了新的内存空间，原来的内存空间并没有处理，Java的垃圾回收机制会完成这一工作。

然后，当push元素时，检查数组是否已满，即判断已经放入的元素数量有没有达到数组的长度，如果是，就把所有元素拷贝到一个长度为原来两倍的数组中，即执行resize(2*a.length)，之后再放入新的元素：

public void push(Item item) {
    if (N == a.length) {
        resize(2*a.length);
    }
    a[N++] = item;
}

类似地，当pop元素时，先去掉栈顶元素(--N)。再检查数组是否盈余过多，是否「盈余过多」的标准不唯一，通常的做法是看已有元素数量是否小于数组长度的1/4，如果是，则表示盈余过多，就将数组长度减半，即resize(a.length/2)：

public Item pop() {
    Item item = a[--N];
    a[N] = null;  // Avoid loitering
    if (N > 0 && N == a.length/4) {
        resize(a.length/2);
    }
    return item;
}
Loitering

这个单词是「闲逛，游手好闲」的意思，这是一种隐式的内存泄漏问题，就是指在上面的pop()函数中，我们用a[--N]模拟「弹出栈顶元素」这一动作，但是实际上数据还是保存在内存里的，而它也不会再被访问，Java的垃圾回收机制也无法处理这种现象，因此这个数据就成为了「孤儿」，即Loitering现象。要避免这种情况，只要把对应的元素置为null即可。其实，申请泛型数组的内存时，也是初始化为null的。

Iteration (迭代)

回顾使用String类的迭代器进行遍历的操作：

Stack<String> collection = new Stack<String>();
...
Iterator<String> it = collection.iterator();
while (i.hasNext()) {
    String s = i.next();
    ...
}

或者用foreach操作：

for (String s : collection)
    ...

类似地，为了让我们自己定义的类可迭代，须要完成以下两个工作：

为了让一个类是iterable的，首先须要在声明这个类时加上语句implements Iterable<Item>。然后，实现iterator()方法，我们将马上要实现的迭代器命名为ReverseArrayIterator（栈是反向遍历）：

public Iterator<Item> iterator() {
    return new ReverseArrayIterator();
}

Java提供了实现迭代器的接口，定义如下（java.util.Iterator）：

public interface Iterator<Item> {
    boolean hasNext();
    Item next();
    void remove();
}

通常，remove()方法可以不用实现。于是，按照上面的接口，我们的迭代器ReverseArrayIterator实现如下（直接写在大类中，声明为private，这是类的嵌套写法）：

// 需要: import java.util.iterator;
private class ReverseArrayIterator implements Iterator<Item> {
    private int i = N;

    public boolean hasNext() {
        return i > 0;
    }

    public Item next() {
        return a[--i];    // 从栈顶往栈底遍历
    }

    public void remove() {}
}

通常为了保证迭代器的健壮性，还需要针对两个情形抛出异常(throw exception)：一是当用户调用remove()方法时，抛出UnsupportedOperationException，二是当i为0时，用户仍然试图调用next()方法，这时抛出NoSuchElementException。这里就省略了~

到这里，迭代器的实现就完成了。小结一下，改进的地方有：

完整的ResizingArrayStack实现：

public class ResizingArrayStack<Item> implements Iterable<Item> {
    private Item[] a = (Item[]) new Object[1];  // 初始化数组大小为1
    private int N = 0;

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private void resize(int max) {
        // N <= max
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }

    public void push(Item item) {
        if (N == a.length) {
            resize(2*a.length);
        }
        a[N++] = item;
    }

    public Item pop() {
        Item item = a[--N];
        a[N] = null;  // Avoid loitering
        if (N > 0 && N == a.length/4) {
            resize(a.length/2);
        }
        return item;
    }

    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }

    private class ReverseArrayIterator implements Iterator<Item> {
        private int i = N;

        public boolean hasNext() {
            return i > 0;
        }

        public Item next() {
            return a[--i];    // 从栈顶往栈底遍历
        }

        public void remove() {}
    }
}

这个基本模型的实现可谓「麻雀虽小，五脏俱全」。

Linked lists

Linked list这个最基本且重要的数据结构就不多说了，再复习一下定义：

A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list.

其抽象类为：

private class Node {
    Item item;
    Node next;
}
构建一个链表

以创建字符串节点为例，首先创建节点实体：

Node first = new Node();
Node second = new Node();
Node third = new Node();
first.item = "to";
second.item = "be";
third.item = "or";

建立连接关系：

first.next = second;
second.next = third;
链表的基本操作
链表的遍历
for (Node x = first; x != null; x = x.next) {
    ...
}
用链表实现栈（链式栈）

栈顶位于链表的头部，栈的push通过在头部插入节点完成，栈的pop通过删除头节点完成。

之间用数组实现栈存在效率问题，主要是resize()函数导致的，因为涉及到对整个栈内存的拷贝。而如果用链表实现栈，就不存在这个问题了，对栈的操作与栈的大小是无关的。最优设计原则即：

The algorithms and data structure go hand in hand.

完整的Stack类实现：

public class Stack<Item> implements Iterable<Item> {
    private Node first;
    private int N;

    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;  // 或者: N == 0
    }

    public int size() {
        return N;
    }

    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    public Item pop() {
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    public Iterator<Item> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext() {
            return current != null;
        }

        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

友情提醒：别忘了import java.util.Iterator;

用链表实现队列（链式队列）

在链式栈的实现上稍加修改，就可以实现队列。链表的头、尾分别代表队列的头和尾，维护两个指针指向链表的头和尾，入队操作通过在链表尾部插入节点实现，出队操作通过删除链表头节点来实现。这也符合最优设计。

完整的Queue类实现：

public class Queue<Item> implements Iterable<Item> {
    private Node first;
    private Node last;
    private int N;

    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;  // 或者: N == 0
    }

    public int size() {
        return N;
    }

    public void enqueue(Item item)  {
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else oldLast.next = last;
        N++;
    }

    public Item dequeue() {
        Node oldFirst = first;
        first = first.next;
        if (isEmpty()) last = null;
        N--;
        return oldFirst.item;
    }

    public Iterator<Item> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext() {
            return current != null;
        }

        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}
用链表实现包(bag)

Bag的实现其实比Stack和Queue都简单，只要把Stack的push()改为add()，另外去掉pop()方法即可。

完整的Bag实现：

public class Bag<Item> implements Iterable<Item> {
    private Node first;
    private int N;

    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;
    }

    public void add(Item item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }

    public Iterator<Item> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext() {
            return current != null;
        }

        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

Bag, Stack和Queue类的迭代器实现部分都一样。

常见问题

1.4 Analysis of Algorithms

由于有基础，算法分析这一节可以快速阅读，里面的实验就省略了，都能理解（感觉这节还真是啰嗦啊~）。

书上p.185有一些级数的阶的近似，最好能够熟悉。

2-sum快速算法

idea: 如果a[i]是一对2-sum中的一个，那么另一个一定是-a[i]。

算法复杂度是O(n log n)。

代码(要import java.util.Arrays;)：

public class TwoSumFast {
    public static int count(int[] a) {
        Arrays.sort(a);
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (BinarySearch.rank(-a[i], a) > i) {
                cnt++;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        int[] a = In.readInts(args[0]);
        StdOut.println(count(a));
    }
}

3-sum快速算法

类似2-sum，idea: 如果a[i], a[j]是一个3-sum中的两个数，那么第三个数一定是-(a[i]+a[j])。

算法类似2-sum，这里不再描述。复杂度是O(n^2 log n)

代码：

public class ThreeSumFast {
    public static int count(int[] a) {
        Arrays.sort(a);
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (BinarySearch.rank(-(a[i]+a[j]), a) > j) {
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        int[] a = In.readInts(args[0]);
        StdOut.println(count(a));
    }
}

后面关于Memory分析的部分实在是没有阅读欲望，比较枯燥，有些部分就直接跳过了，以后有需要再回来补上。

1.5 Case Study: Union-Find

吐槽：第一章直接拿并查集来作为case study，与本章讲解的内容似乎并没有什么逻辑关系...难道不应该放在图论部分吗？

又想到了曾经看过的一篇文章，我至今认为它是对并查集最易懂且最有趣的讲解。文章的作者已无从考究，这是一篇转载: http://www.cnblogs.com/ACShiryu/archive/2011/11/24/unionset.html

Quick-union

这是最基本的并查集算法。

public class UF {
    private int[] id;
    private int count;

    public UF(int N) {
        // 初始化连通分量
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }

    public int count() {
        return count;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int find(int p) {
        while (id[p] != p) p = id[p];
        return p;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return;

        id[pRoot] = qRoot;

        count--;
    }
}

quick-union算法中的connected(), find(), union()的平均时间复杂度是O(log n)。

Weighted quick-union

上面的算法有个缺陷：由于执行union()操作时是任意连接两个连通分量的，连通分量的连接受输入数据影响比较大，可能会造成很不均衡的状态。一个改进的思路是，用一个数组记录并跟踪每个连通分量（树）的节点数，每次连接两个树时，把节点数较少的树连到节点数较多的树上。

public class WeightedQuickUnionUF {
    private int[] id;
    private int[] sz;
    private int count;

    public WeightedQuickUnionUF(int N) {
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
        sz = new int[N];
        for (int i = 0; i < N; i++) sz[i] = 1;
    }

    public int count() {
        return count;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int find(int p) {
        while (p != id[p]) p = id[p];
        return p;
    }

    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if (i == j) return;

        if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
        else               { id[j] = i; sz[i] += sz[j]; }
        count--;
    }
}

这样，如果有N个节点，最坏情况下，最后构造的森林中所有节点的深度也不会超过log n。从而的算法的connected(), find(), union()的最坏时间复杂度就被降到了O(log n)。

在实际中，真正实用的算法是weighted quick-union，其时间复杂度是O(m log n)，其中m是连接数（边数），n是节点数。

路径压缩

观察上面的代码，可以看出，weighted quick-union的效率瓶颈就在于find()函数，怎样可以更快地查找呢？一个idea就是：修改find()函数，想办法将搜索根节点过程中遇到的节点直接连到根上。这就是所谓的路径压缩(path compression)。路径压缩的实现非常容易，只要稍稍修改一下find()函数即可：用一个变量保存根节点，再走一遍刚才的搜索路径，将路径上所有节点的id[]值为根节点即可：

public int find(int p) {
    int r;  // 根节点
    int cur = p;
    while (cur != id[cur]) {
        cur = id[cur];
    }
    r = cur;
    // 路径压缩
    cur = p;
    int tmp;
    while (cur != r) {
        tmp = id[cur];
        id[cur] = r;
        cur = tmp;
    }

    return r;
}

虽然看起来是增加了一个循环，但是却能将搜索的效率大大提升，能使搜索的效率接近常数级（平摊复杂度并不是严格的常数级），尤其在数据规模很大的时候。带路径压缩的weighted quick-union的算法分析十分复杂，理论分析已经证明了它是union-find问题的最优算法。

方法论

在这一节的最后总结了解决问题的一些基本步骤，还是挺好的：

上一篇 下一篇

猜你喜欢

热点阅读