漱石斋笔谈

gaotf 的博客

1.为什么要使用泛型设计

泛型程序设计意味着编写的代码可以对多种不同类型的对象重用。例如,你不想为收集StringFile对象分别编写不同的类。实际上,也不需要这样做,因为一个ArrayList类就可以收集任何类的对象。这就是泛型程序设计的一个例子。

List arrayList = new ArrayList();
arrayList.add("aaaa");
arrayList.add(100);

for(int i = 0; i< arrayList.size();i++){
    String item = (String)arrayList.get(i);
    Log.d("泛型测试","item = " + item);
}

毫无疑问,这个程序会在运行时崩溃,为了解决这样的问题(在编译阶段就可以解决),泛型应运而生。我们将第一行声明初始化list的代码更改一下,编译器会在编译阶段就能够帮我们发现类似这样的问题。

List<String> arrayList = new ArrayList<String>();
...
//arrayList.add(100); 在编译阶段,编译器就会报错

2.泛型的特性

泛型只在编译阶段有效,下面是一个经典的泛型的例子。

List<String> stringArrayList = new ArrayList<String>();
List<Integer> integerArrayList = new ArrayList<Integer>();

Class classStringArrayList = stringArrayList.getClass();
Class classIntegerArrayList = integerArrayList.getClass();

if(classStringArrayList.equals(classIntegerArrayList)){
    Log.d("泛型测试","类型相同");
}

输出的结果是类型相同。通过上面的例子可以证明,在编译之后程序会采取去泛型化的措施。也就是说Java中的泛型,只在编译阶段有效。在编译过程中,正确检验泛型结果后,会将泛型的相关信息擦出,并且在对象进入和离开方法的边界处添加类型检查和类型转换的方法。也就是说,泛型信息不会进入到运行时阶段。

3.泛型类

通过泛型可以完成对一组类的操作对外开放相同的接口。最典型的就是各种容器类,如:ListSetMap
泛型类的基本写法为:

class 类名称 <泛型标识:可以随便写任意标识号,标识指定的泛型的类型>{
    private 泛型标识 /*(成员变量类型)*/ var; 
    .....
    }
}

下面我们实现一个简单的泛型类:

//此处T可以随便写为任意标识,常见的如T、E、K、V等形式的参数常用于表示泛型
//在实例化泛型类时,必须指定T的具体类型
public class Generic<T>{ 
    //key这个成员变量的类型为T,T的类型由外部指定  
    private T key;

    public Generic(T key) { //泛型构造方法形参key的类型也为T,T的类型由外部指定
        this.key = key;
    }

    public T getKey(){ //泛型方法getKey的返回值类型为T,T的类型由外部指定
        return key;
    }
}

传入参数时:如果传入泛型类型实参,会根据传入的泛型实参做相应的限制,此时泛型才会起到本应起到的限制作用。

//泛型的类型参数只能是类类型(包括自定义类),不能是简单类型
//传入的实参类型需与泛型的类型参数类型相同,即为Integer.
Generic<Integer> genericInteger = new Generic<Integer>(123456);

//传入的实参类型需与泛型的类型参数类型相同,即为String.
Generic<String> genericString = new Generic<String>("key_vlaue");
Log.d("泛型测试","key is " + genericInteger.getKey());
Log.d("泛型测试","key is " + genericString.getKey());

如果不选择传入泛型类型实参:在泛型类中使用泛型的方法或成员变量定义的类型可以为任何的类型。

Generic generic = new Generic("111111");
Generic generic1 = new Generic(4444);
Generic generic2 = new Generic(55.55);
Generic generic3 = new Generic(false);

Log.d("泛型测试","key is " + generic.getKey());
Log.d("泛型测试","key is " + generic1.getKey());
Log.d("泛型测试","key is " + generic2.getKey());
Log.d("泛型测试","key is " + generic3.getKey());

注意:

  • 泛型的类型参数只能是类类型,不能是简单类型。
  • 不能对确切的泛型类型使用instanceof操作。如下面的操作是非法的,编译时会出错。
if(ex_num instanceof Generic<Number>){ }

4.泛型接口

泛型接口常被用在各种类的生产器中:

//定义一个泛型接口
public interface Generation<T> {
    public T next();
}

当实现泛型接口的类,未传入泛型实参时:

/**
* 未传入泛型实参时,与泛型类的定义相同,在声明类的时候,需将泛型的声明也一起加到类中
* 即:class FruitGenerator<T> implements Generator<T>{
* 如果不声明泛型,如:class FruitGenerator implements Generator<T>,编译器会报错:"Unknown class"
*/
class FruitGenerator<T> implements Generator<T>{
    @Override
    public T next() {
        return null;
    }
}

当实现泛型接口的类,传入泛型实参时:

/**
* 传入泛型实参时:
* 定义一个生产器实现这个接口,虽然我们只创建了一个泛型接口Generator<T>
* 但是我们可以为T传入无数个实参,形成无数种类型的Generator接口。
* 在实现类实现泛型接口时,如已将泛型类型传入实参类型,则所有使用泛型的地方都要替换成传入的实参类型
* 此时不需要在声明类中的泛型声明T
* 即:Generator<T>,public T next();中的的T都要替换成传入的String类型。
*/
public class FruitGenerator implements Generator<String> {

    private String[] fruits = new String[]{"Apple", "Banana", "Pear"};

    @Override
    public String next() {
        Random rand = new Random();
        return fruits[rand.nextInt(3)];
    }
}

5.泛型方法

泛型方法的基本形式:

/**
* 泛型方法的基本介绍
* @param tClass 传入的泛型实参
* @return T 返回值为T类型
* 说明:
*     1)public与返回值中间<T>非常重要,可以理解为声明此方法为泛型方法。
*     2)只有声明了<T>的方法才是泛型方法,泛型类中的使用了泛型的成员方法并不是泛型方法。
*     3)<T>表明该方法将使用泛型类型T,此时才可以在方法中使用泛型类型T。
*     4)与泛型类的定义一样,此处T可以随便写为任意标识,常见的如T、E、K、V等形式的参数常用于表示泛型。
*/
public <T> T genericMethod(Class<T> tClass)throws InstantiationException ,
IllegalAccessException{
        T instance = tClass.newInstance();
        return instance;
}

5.1 泛型方法的基本用法

public class GenericTest {
    //这个类是个泛型类,在上面已经介绍过
    public class Generic<T>{     
        private T key;

        public Generic(T key) {
            this.key = key;
        }

        //我想说的其实是这个,虽然在方法中使用了泛型,但是这并不是一个泛型方法。
        //这只是类中一个普通的成员方法,只不过他的返回值是在声明泛型类已经声明过的泛型。
        //所以在这个方法中才可以继续使用 T 这个泛型。
        public T getKey(){
            return key;
        }

        /**
        * 这个方法显然是有问题的,在编译器会给我们提示这样的错误信息"cannot reslove symbol E"
        * 因为在类的声明中并未声明泛型E,所以在使用E做形参和返回值类型时,编译器会无法识别。
        public E setKey(E key){
            this.key = keu
        }
        */
    }

    /** 
    * 这才是一个真正的泛型方法。
    * 首先在public与返回值之间的<T>必不可少,这表明这是一个泛型方法,并且声明了一个泛型T
    * 这个T可以出现在这个泛型方法的任意位置.
    * 泛型的数量也可以为任意多个 
    *    如:public <T,K> K showKeyName(Generic<T> container){
    *        ...
    *        }
    */
    public <T> T showKeyName(Generic<T> container){
        System.out.println("container key :" + container.getKey());
        //当然这个例子举的不太合适,只是为了说明泛型方法的特性。
        T test = container.getKey();
        return test;
    }

    //这也不是一个泛型方法,这就是一个普通的方法,只是使用了Generic<Number>这个泛型类做形参而已。
    public void showKeyValue1(Generic<Number> obj){
        Log.d("泛型测试","key value is " + obj.getKey());
    }

    //这也不是一个泛型方法,这也是一个普通的方法,只不过使用了泛型通配符?
    //同时这也印证了泛型通配符章节所描述的,?是一种类型实参,可以看做为Number等所有类的父类
    public void showKeyValue2(Generic<?> obj){
        Log.d("泛型测试","key value is " + obj.getKey());
    }

    /**
    * 这个方法是有问题的,编译器会为我们提示错误信息:"UnKnown class 'E' "
    * 虽然我们声明了<T>,也表明了这是一个可以处理泛型的类型的泛型方法。
    * 但是只声明了泛型类型T,并未声明泛型类型E,因此编译器并不知道该如何处理E这个类型。
    public <T> T showKeyName(Generic<E> container){
        ...
    }  
    */

    /**
    * 这个方法也是有问题的,编译器会为我们提示错误信息:"UnKnown class 'T' "
    * 对于编译器来说T这个类型并未项目中声明过,因此编译也不知道该如何编译这个类。
    * 所以这也不是一个正确的泛型方法声明。
    public void showkey(T genericObj){

    }
    */

    public static void main(String[] args) {
        ...
    }
}

5.2 泛型类中的泛型方法

有一种情况是非常特殊的,当泛型方法出现在泛型类中时,我们再通过一个例子看一下:

public class GenericFruit {
    class Fruit{
        @Override
        public String toString() {
            return "fruit";
        }
    }

    class Apple extends Fruit{
        @Override
        public String toString() {
            return "apple";
        }
    }

    class Person{
        @Override
        public String toString() {
            return "Person";
        }
    }

    class GenerateTest<T>{
        public void show_1(T t){
            System.out.println(t.toString());
        }

        //在泛型类中声明了一个泛型方法,使用泛型E,这种泛型E可以为任意类型。可以类型与T相同,也可以不同。
        //由于泛型方法在声明的时候会声明泛型<E>,因此即使在泛型类中并未声明泛型,编译器也能够正确识别泛型方法中识别的泛型。
        public <E> void show_3(E t){
            System.out.println(t.toString());
        }

        //在泛型类中声明了一个泛型方法,使用泛型T,注意这个T是一种全新的类型,可以与泛型类中声明的T不是同一种类型。
        public <T> void show_2(T t){
            System.out.println(t.toString());
        }
    }

    public static void main(String[] args) {
        Apple apple = new Apple();
        Person person = new Person();

        GenerateTest<Fruit> generateTest = new GenerateTest<Fruit>();
        //apple是Fruit的子类,所以这里可以
        generateTest.show_1(apple);
        //编译器会报错,因为泛型类型实参指定的是Fruit,而传入的实参类是Person
        //generateTest.show_1(person);

        //使用这两个方法都可以成功
        generateTest.show_2(apple);
        generateTest.show_2(person);

        //使用这两个方法也都可以成功
        generateTest.show_3(apple);
        generateTest.show_3(person);
    }
}

5.3 静态方法与泛型

静态方法有一种情况需要注意一下,那就是在类中的静态方法使用泛型:静态方法无法访问类上定义的泛型;如果静态方法操作的引用数据类型不确定的时候,必须要将泛型定义在方法上。即:如果静态方法要使用泛型的话,必须将静态方法也定义成泛型方法 。

public class StaticGenerator<T> {
    ....
    ....
    /**
    * 如果在类中定义使用泛型的静态方法,需要添加额外的泛型声明(将这个方法定义成泛型方法)
    * 即使静态方法要使用泛型类中已经声明过的泛型也不可以。
    * 如:public static void show(T t){..},此时编译器会提示错误信息:
        "StaticGenerator cannot be refrenced from static context"
    */
    public static <T> void show(T t){

    }
}

5.4 泛型方法总结

一个基本的指导原则:

无论何时,如果你能做到,你就该尽量使用泛型方法。也就是说,如果使用泛型方法将整个类泛型化,

那么就应该使用泛型方法。另外对于一个static的方法而已,无法访问泛型类型的参数。

所以如果static方法要使用泛型能力,就必须使其成为泛型方法。

6.泛型上下边界

在使用泛型的时候,我们还可以为传入的泛型类型实参进行上下边界的限制,如:类型实参只准传入某种类型的父类或某种类型的子类。为泛型添加上边界,即传入的类型实参必须是指定类型的子类型。

public void showKeyValue1(Generic<? extends Number> obj){
    Log.d("泛型测试","key value is " + obj.getKey());
}

具体情况:

Generic<String> generic1 = new Generic<String>("11111");
Generic<Integer> generic2 = new Generic<Integer>(2222);
Generic<Float> generic3 = new Generic<Float>(2.4f);
Generic<Double> generic4 = new Generic<Double>(2.56);

//这一行代码编译器会提示错误,因为String类型并不是Number类型的子类
//showKeyValue1(generic1);

showKeyValue1(generic2);
showKeyValue1(generic3);
showKeyValue1(generic4);

如果我们把泛型类的定义也修改一下:

public class Generic<T extends Number>{
    private T key;

    public Generic(T key) {
        this.key = key;
    }

    public T getKey(){
        return key;
    }
}

这种情况下:

//这一行代码也会报错,因为String不是Number的子类
Generic<String> generic1 = new Generic<String>("11111");

再来看一个例子:

//在泛型方法中添加上下边界限制的时候,必须在权限声明与返回值之间的<T>上添加上下边界,即在泛型声明的时候添加
//public <T> T showKeyName(Generic<T extends Number> container),编译器会报错:"Unexpected bound"
public <T extends Number> T showKeyName(Generic<T> container){
    System.out.println("container key :" + container.getKey());
    T test = container.getKey();
    return test;
}

简介

Ceres由两个部分组成,一个是建模API,它提供了非常丰富的工具,可以迅速构建一个优化问题模型。另一个是解算器API,用于管控最小化算法。这一章将围绕如何用Ceres进行优化问题建模展开。

自动微分AutoDiffCostFunction

定义一个CostFunction(例如使用数值微分法或者解析微分法)可能是一个繁琐且容易出错的过程,尤其是在计算导数的时候。为此,Ceres提供了AutoDiffCostFunction

template <typename CostFunctor,
        int kNumResiduals,  // Number of residuals, or ceres::DYNAMIC.
        int N0,       // Number of parameters in block 0.
        int N1 = 0,   // Number of parameters in block 1.
        int N2 = 0,   // Number of parameters in block 2.
        int N3 = 0,   // Number of parameters in block 3.
        int N4 = 0,   // Number of parameters in block 4.
        int N5 = 0,   // Number of parameters in block 5.
        int N6 = 0,   // Number of parameters in block 6.
        int N7 = 0,   // Number of parameters in block 7.
        int N8 = 0,   // Number of parameters in block 8.
        int N9 = 0>   // Number of parameters in block 9.
class AutoDiffCostFunction : public
SizedCostFunction<kNumResiduals, N0, N1, N2, N3, N4, N5, N6, N7, N8, N9> {
    public:
        explicit AutoDiffCostFunction(CostFunctor* functor);
        // Ignore the template parameter kNumResiduals and use
        // num_residuals instead.
        AutoDiffCostFunction(CostFunctor* functor, int num_residuals);
};

为了获得一个可以自动微分的代价函数,必须定义一个类。这个类中带有模板函数:operator(),它使用模板T类型进行代价函数运算。自动微分将根据需要用Jet类型替代替代模板T。但这个是隐藏的,编程的时候要把这个T看作一个双精度浮点数。这个函数必须把计算结果以最后一个参数(唯一一个非常量参数)传递出来,并且返回True,告诉计算机运算成功完成。例如,现在有一个标量的偏差函数$e = k - x^Ty$。这里$x$和$y$都是二维向量参数,$k$是个常量 。这种类型的偏差,即一个常量和一个表达式的差值,在最小二乘法问题中很常见。例如,$x ^ T y$可能是一系列测量结果的期望值,那么每一次测量$K$都对应了一个代价函数类的实例。被加到Problem中的是$e ^ 2$或者$(k - x^Ty) ^ 2$。平方处理由Ceres优化框架完成。这个例子的具体代码如下:

这里有个疑问,之前自动微分算法的代码中没有使用类,而是使用的struct,不知道为什么这里是class,个人认为应该都可以,因为我们的代码中都使用的struct。

class MyScalarCostFunctor {
    MyScalarCostFunctor(double k): k_(k) {}

template <typename T>
bool operator()(const T* const x , const T* const y, T* e) const {
    e[0] = k_ - x[0] * y[0] - x[1] * y[1];
    return true;
}

private:
    double k_;
};

注意,在operator()的声明中,首先是输入参数,他们都是指向T类型数组的常指针。如果由更多的输入参数就跟在y后面。而输出值永远是最后一个参数,并且也是一个指向数组的指针。在上述例子中,e是标量,所以只赋值e[0]

然后给出这个类的定义,它的自动微分代价函数可以如下构造:

CostFunction* cost_function
    = new AutoDiffCostFunction<MyScalarCostFunctor, 1, 2, 2>(
        new MyScalarCostFunctor(1.0));              ^  ^  ^
                                                    |  |  |
                        Dimension of residual ------+  |  |
                        Dimension of x ----------------+  |
                        Dimension of y -------------------+

在这个例子中,对每次测量k都有一个实例。模板参数1,2,2将Functor描述为一个一维输出参数和两个二维输入参数。AutoDiffCostFunction也支持在运行时动态确定参数个数。例如下面的代码:

CostFunction* cost_function
    = new AutoDiffCostFunction<MyScalarCostFunctor, DYNAMIC,  2,  2>(
        new CostFunctorWithDynamicNumResiduals(1.0),    ^     ^  ^
        runtime_number_of_residuals);  <----+           |     |  |
                                            |           |     |  |
                                            |           |     |  |
           Actual number of residuals ------+           |     |  |
           Indicate dynamic number of residuals --------+     |  |
           Dimension of x ------------------------------------+  |
           Dimension of y ---------------------------------------+

Ceres目前支持代价函数最多有10个相互独立的变量,但是对每个变量有多少维度没有限制。

注意,新用户常常犯的一个错误就是把模板参数中的数字理解成参数的个数。但事实上,模板参数中数字的含义是每个参数的维度。这两个概念不能混淆。比如在这个例子中x,y都是二维变量,所以模板参数中有两个2。

Problem的构建

Problem保持了非线性最小二乘问题的强化的边界。要创建最小二乘问题,可以使用Problem::AddResidualBlock()Problem::AddParameterBlock()。例如,下面这个Problem包含了三个参数块,维度分别为3,4,5。同时有两个残差块,维度分别是2和6。

double x1[] = { 1.0, 2.0, 3.0 };
double x2[] = { 1.0, 2.0, 3.0, 5.0 };
double x3[] = { 1.0, 2.0, 3.0, 6.0, 7.0 };

Problem problem;
problem.AddResidualBlock(new MyUnaryCostFunction(...), x1);
problem.AddResidualBlock(new MyBinaryCostFunction(...), x2, x3);

Problem::AddResidualBlock(),顾名思义,就是把残差块加入到Problem中。它添加了一个CostFunction,一个LossFunction(非必要)并且把CostFunction链接到一系列的参数块上。代价函数包含了关于期望的参数块大小的信息。该函数检查他们是否与parameter_blocks一致。如果不匹配,程序将终止。LossFunction可以是Null,这种情况下这一项的代价就是残差的平方。

另外官网中给出了很多Problem的方法,可以查看一下。这里只对添加残差块的方法给出了实例。

简介

如果想要高效地使用Ceres Solver,需要掌握一定的非线性最小二乘解算基础知识。所以在这一部分将将要介绍Ceres中核心优化算法的工作原理。

设$x \in \mathbb{R}^n$是一个$n$维向量,并且$F(x) = [f_1(x),\cdots,f_m(x)] ^ T$是关于$x$的$n$维方程。那么我们关注下列优化问题

$$
argmin_x \frac{1}{2} \left | F(x) \right | ^ 2 \
L \le x \le U
$$
其中$L$和$U$分别是参数向量$x$的下限和上限。

因为对于一个一般的函数,求解全局最小值常常非常棘手,我们不得不关注局部最小值。$F(x)$的雅可比矩阵$J(x)$是一个$m \times n$的矩阵,其中$J_{ij}(x) = \partial _j f_i(x)$,函数的梯度向量$g(x) = \nabla \frac{1}{2} \left | F(x) \right | ^ 2 = J(x)^T F(x)$。

在计算非线性优化问题的一个通用的策略是,求解原问题的近似简化问题。在每一次循环中,根据近似问题的解可以确定向量$x$的修正值$\triangle x$。对于非线性最小二问题,我们可以通过线性化来建立近似问题,即$F(x + \triangle x) \approx F(x) + J(x) \triangle x$。那么上述问题就变成下列问题:

$$
min_{\triangle x} \frac{1}{2} \left |F(x) + J(x) \triangle x \right |^2
$$

这里官方教程跳了几步。要求全局最小值非常棘手,所以转而求局部最小值。而求局部最小值就是,从一个任意的起始点,观测四周的“更小值”。如果观测四周都比当前点大,那么当前点就是局部最小值点,算法达到收敛。否则,设这个新找到的最小值点为“当前点”,重复这一步骤。这也就是下文中”用$x \longleftarrow x + \triangle x$来更新“的含义。所以现在问题变成了,如何求解四周的点的值。即,给$x$赋予一个步长$\triangle x$,观察周围的$F(x + \triangle x)$,并且寻找最小值。

根据步长的控制方法,非线性优化可以分成两大类。

  • 置信域法Trust Region (也有文献成为信任域法)置信域方法在搜索空间的子集内应用模型函数(通常是二次方程)来近似目标函数,这个空间被称为置信域。如果模型函数成功地使真正的目标函数最小化,则扩大置信域。否则收缩置信域并且再次尝试求解模型函数的优化问题。
  • 线搜索法Line Search 线搜索方法首先找到一个下降的方向,目标函数将沿其下降。然后再确定步长,从而决定沿该方向到底移动多远。 下降方向可以通过各种方法计算,如梯度下降法、牛顿法和拟牛顿法。步长可以精确或不精确地确定。

这里我们只对共轭梯度法进行介绍(因为我们用的库函数所采用的方法就是共轭梯度法)

对以下形式的线性最小二乘问题:

$$
min_{\triangle x} \frac{1}{2} \left |F(x) + J(x) \triangle x \right |^2
$$
令$H(x) = J(x) ^ TJ(x)$且$g(x) = - J(x) ^ {T}f(x)$。为了标记方便,我们舍弃对$x$的依赖,那么很容易看出求解上式等价于求解Normal Equation方程

$$
H\triangle x = g
$$
我们在程序中使用的计算上式的线性解算器是CGNR,该解算器在法向方程上使用共轭梯度求解器,但没有明确地构建Normal Equation方程。 它利用下列关系:

$$
Hx = J ^ TJx = J^T(Jx)
$$
共轭梯度的收敛取决于调节器数量$\kappa(H)$,通常$H$的条件比较弱,并且必须使用预调节器才能获得合理的性能。 目前只有JACOBI预处理器可以用于CGNR。它使用$H$的块对角线来预处理Normal Equation方程。

当用户选择CGNR作为线性求解器时,Ceres会自动从精确的步长算法切换到不精确的步长算法。

JACOBI预处理器

求解Normal Equation方程的收敛速度取决于$H$的特征值的分布。一个有用的上界是$\sqrt {\kappa H}$,$\sqrt {\kappa H}$是矩阵$H$的条件值。对于大多数$BA$问题来说,$\sqrt {\kappa H}$很大,直接应用共轭梯度法对该方程进行求解会导致糟糕的性能。

这个问题的解决方法是用一个预条件系统来替换$H\triangle x = g$方程。给定一个线性系统,$Ax = b$,预条件器$M$,预条件系统$M^{-1} Ax = M^{-1}b$。这个算法被称作预处理共轭梯度法(PCG),它最坏的情况现在取决于预条件矩阵$\sqrt{M^{-1}A}$的条件数。

使用预条件器$M$的计算成本是计算$M$以及任意向量$y$的乘积$M^{-1}y$,因此,要考虑两个相互竞争的因素:$H$的结构中有多少是由$M$占据的,以至于条件值$\kappa(HM^{-1})$,以及构造和使用$M$的计算成本。理想的预调节器是条件值$\kappa(M^{-1}A) = 1$。使用$M = A$可以实现这一效果,但是不是一个实际的选择,因为应用这个预调函数需要一个线性方程组,等价于无预先条件的问题。通常情况下,$M$的信息越多,使用的成本就越高。例如,基于不完全$Cholesky$分解的预条件器比$Jacobi$预条件器具有更好的收敛性能,但代价也更高。

所有的预调节器中最简单的是对角或雅可比的预调机。例如,$M = diag(A)$。对于像$H$这样的块状结构矩阵,可以将其推广到$Jacobi$的预调节器。Ceres实现的块$Jacobi$预调节器叫做JACOBI,当使用CGNR时,它指的是$H$的块对角线,即

$$
C_{i j}=\left{\begin{array}{cc}
A_{i i} & \text { if } i=j \
0 & \text { 其他 }
\end{array}\right.
$$

PCG算法的过程如下:假设$x_0 \in \mathbb{R}^n$是初始向量,

$$
\begin{aligned}
&r_{0}=b-A x_{0}\
&z_{0}=C^{-1} r_{0}\
&d_{0}=z_{0}\
&\text { For } k=0,1,2, \ldots\
&\alpha_{k}=\frac{z_{k}^{\top} r_{k}}{d_{k}^{\top} A d_{k}}\
&x_{k+1}=x_{k}+\alpha_{k} d_{k}\
&r_{k+1}=r_{k}-\alpha_{k} A d_{k}\
&z_{k+1}=C^{-1} r_{k+1}\
&\beta_{k+1}=\frac{z_{k+1}^{\top} r_{k+1}}{z_{k}^{\top} r_{k}}\
&d_{k+1}=x_{k+1}+\beta_{k+1} d_{k}
\end{aligned}
$$

非线性最小二乘法

介绍

Ceres可以解决有界约束形式的鲁棒非线性最小二乘问题,形式如下:

$$min_x\frac{1}{2}\sum_i\rho_i(\left |f_i(x_{i_1},\cdots,x_{i_k}) \right |^2)$$

$$s.t. l_i\le x_j\le u_j$$
这一表达式在工程和科学领域有非常广泛的应用,比如统计学中的曲线拟合,或者在计算机视觉中依据图像进行三维模型的构建等等。

$\rho_i(\left |f_i(x_{i_1},\cdots,x_{i_k}) \right |^2)$这一部分被称为残差块(ResidualBlock),其中的$f_i(\cdot )$叫做代价函数(CostFuction)。代价函数依赖于一系列参数$[x_{i_1},\cdots,x_{i_k}]$,这一系列参数(均为标量)称为参数块(ParameterBlock)。当然参数块中也可以只含有一个变量。$l_j$和$u_j$分别是变量块$x_j$的上下边界。

$\rho_i$是损失函数(LossFuction)。损失函数是一个标量函数,其作用是减少异常值(Outliers)对优化结果的影响。其效果类似于对函数的过滤。

一个特殊情况是,$\rho_i(f
(x)) = f(x)$,也就是没有对函数进行任何过滤,损失函数的输出等于输入。若同时令$l_j = -\infty$并且$u_j = \infty$,即参数块的取值没有限制,那么此时问题变成了非线性最小二乘问题。表达式如下:

$$\frac{1}{2}\sum_i\left | f_i(x_{i_1},\cdots,x_{i_k}) \right |^2$$

Hello World

每个程序最简单的示例被称为Hello World。本节将简单描述Ceres的Hello World示例,以便让读者对库的使用步骤快速建立认识。
在Hello World这个例子中,待优化的函数是$f(x) = 10 - x$,重载操作符如下:

struct CostFunctor {
    template <typename T>
    bool operator()(const T* const x, T* residual) const {
        residual[0] = T(10.0) - x[0];
        return true;
    }
};

重点要注意这里的operator()是一个模板方法,这里假设所有的输入和输出都是同一类型T。在后面的代码中,Ceres通过调用CostFunctor::operator<T>()来使用这一重载操作符。在这个例子中可以令T = double,然后仅仅以double类型输出残差值。也可以令T = Jet然后输出雅可比矩阵。这一部分在后面会有更详细的介绍。

雅可比矩阵实际上就是对一个含有多个参数的函数$f(x)$求一系列一阶偏微分

一旦残差方程建立,我们就可以用Ceres来实现非线性最小二乘法的优化算法。代码如下:

int main(int argc, char** argv) {
google::InitGoogleLogging(argv[0]);

// The variable to solve for with its initial value.
double initial_x = 5.0;
double x = initial_x;

// Build the problem.
Problem problem;

// Set up the only cost function (also known as residual). This uses
// auto-differentiation to obtain the derivative (jacobian).
CostFunction* cost_function =
    new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);
problem.AddResidualBlock(cost_function, nullptr, &x);

// Run the solver!
Solver::Options options;
options.linear_solver_type = ceres::DENSE_QR;
options.minimizer_progress_to_stdout = true;
Solver::Summary summary;
Solve(options, &problem, &summary);

std::cout << summary.BriefReport() << "\n";
std::cout << "x : " << initial_x
            << " -> " << x << "\n";
return 0;
}

AutoDiffCostFuction将刚刚建立的CostFuctor结构的一个实例作为输入,自动生成其微分并且赋予其一个CostFuction类型的接口。
编译完成,运行结果如下:(原文中$x$初始值输出错误,修正为上面代码中的$5$)

iter      cost      cost_change  |gradient|   |step|    tr_ratio  tr_radius  ls_iter  iter_time  total_time
0     4.512500e+01    0.00e+00    9.50e+00   0.00e+00   0.00e+00  1.00e+04       0     5.33e-04   3.46e-03
1     4.511598e-07    4.51e+01    9.50e-04   9.50e+00   1.00e+00  3.00e+04       1     5.00e-04   4.05e-03
2     5.012552e-16    4.51e-07    3.17e-08   9.50e-04   1.00e+00  9.00e+04       1     1.60e-05   4.09e-03
Ceres Solver Report: Iterations: 2, Initial cost: 4.512500e+01, Final cost: 5.012552e-16, Termination: CONVERGENCE
x : 5 -> 10

初始值为$5$,最终通过两次循环之后到达最优解$10$。其实本例是一个线性问题,因为$f(x) = 10 - x$是一个线性函数,但是Ceres仍然可以应用。

导数

像大多数优化软件包一样,Ceres求解器的求解基于其能够在任意参数值下评估目标函数中每个项的值和导数。 正确而高效地做到这一点对于取得优秀的运算结果至关重要。Ceres提供了一系列解决方案,其中一个就是在Hello World中用到的Automatic Differentiation (自动微分算法)。这一部分我们将探讨另外两种可能性,即解析法(Analytic)和数值法(Numeric )求导。

数值法求导(Numeric Derivatives)

在某些情况下,像在Hello World中一样定义一个代价函数是不可能的。比如在求解残差值(residual)的时候调用了一个库函数,而这个库函数的内部算法你根本无法干预。在这种情况下数值微分算法就派上用场了。用户定义一个CostFunctor来计算残差值,并且构建一个NumericDiffCostFunction数值微分代价函数。比如对于$f(x) = 10 - x$对应函数体如下:

struct NumericDiffCostFunctor {
    bool operator()(const double* const x, double* residual) const {
        residual[0] = 10.0 - x[0];
        return true;
    }
};

然后继续添加Problem

CostFunction* cost_function =
    new NumericDiffCostFunction<NumericDiffCostFunctor, ceres::CENTRAL, 1, 1>(
        new NumericDiffCostFunctor);
problem.AddResidualBlock(cost_function, NULL, &x);

这里我们引用一下Hello World中模板类函数以及自动微分算法(automatic)的代码进行比对:

//模板类函数
struct CostFunctor {
    template <typename T>
    bool operator()(const T* const x, T* residual) const {
        residual[0] = T(10.0) - x[0];
        return true;
    }
};
//自动微分算法(automatic)
CostFunction* cost_function =
    new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);
problem.AddResidualBlock(cost_function, NULL, &x);

可以发现两种算法在构建Problem时候基本差不多。但是在用Nummeric算法时需要额外给定一个参数ceres::CENTRAL。这个参数告诉计算机如何计算导数。更多具体介绍可以参看NumericDiffCostFunction的Doc文档。

Ceres官方更加推荐自动微分算法,因为C++模板类使自动算法有更高的效率。数值微分算法通常来说计算更复杂,收敛更缓慢。

解析法求导(Analytic Derivatives)

有些时候,应用自动求解算法时不可能的。比如在某些情况下,计算导数的时候,使用闭合解(closed form,也被称为解析解)会比使用自动微分算法中的链式法则(chain rule)更有效率。这里辨析一下解析解和数值解:

在解组件特性相关的方程式时,大多数的时候都要去解偏微分或积分式,才能求得其正确的解。依照求解方法的不同,可以分成以下两类:解析解和数值解。

  • 解析解(analytical solution):
    就是一些严格的公式,给出任意的自变量就可以求出其因变量,也就是问题的解。他人可以利用这些公式计算各自的问题。所谓的解析解是一种包含:分式、三角函数、指数、对数甚至无限级数等基本函数的解的形式。用来求得解析解的方法称为解析法〈analytic techniques、analytic methods〉,解析法即是常见的微积分技巧,例如分离变量法等。解析解为一封闭形式〈closed-form〉的函数,因此对任一独立变量,我们皆可将其带入解析函数求得正确的相依变量。因此,解析解也被称为闭式解(closed-form solution)。
  • 数值解(numerical solution):
    是采用某种计算方法,如有限元的方法, 数值逼近,插值的方法, 得到的解。别人只能利用数值计算的结果, 而不能随意给出自变量并求出计算值。当无法藉由微积分技巧求得解析解时,这时便只能利用数值分析的方式来求得其数值解了。数值方法变成了求解过程重要的媒介。在数值分析的过程中,首先会将原方程式加以简化,以利后来的数值分析。例如,会先将微分符号(连续)改为差分符号(离散)等。然后再用传统的代数方法将原方程式改写成另一方便求解的形式。这时的求解步骤就是将一独立变量带入,求得相依变量的近似解。因此利用此方法所求得的相依变量为一个个分离的数值〈discrete values〉,不似解析解为一连续的分布,而且因为经过上述简化的动作,所以可以想见正确性将不如解析法来的好。

在这种情况下,你就可以自己编写残差计算代码和雅可比行列式的计算代码了。还是用Hello world中的$f(x) = 10 - x$为例:

class QuadraticCostFunction : public ceres::SizedCostFunction<1, 1> {
 public:
  virtual ~QuadraticCostFunction() {}
  virtual bool Evaluate(double const* const* parameters,
                        double* residuals,
                        double** jacobians) const {
    const double x = parameters[0][0];
    residuals[0] = 10 - x;

    // Compute the Jacobian if asked for.
    if (jacobians != nullptr && jacobians[0] != nullptr) {
    jacobians[0][0] = -1;
    }
    return true;
  }
};

Evaluate函数的参数包括:参数的输入数组、残差的输出数组以及雅可比矩阵的输出数组。其中雅可比矩阵是可选的,Evaluate会在它非空时进行检查,并且如果是非空则用残差的导数值进行填充。这种情况下残差函数是线性的,雅可比行列式是常数。

从上述代码片段可以看出,实现“CostFunction““其实有点乏味。所以除非有什么特殊原因需要自行构建雅可比的计算,否则最好还是直接使用自动微分法或者数值微分法来创建残差块。

其他导数计算方法

到目前为止,计算导数其实是Ceres最复杂的部分了。根据需要,用户有时候还需要更复杂的导数计算算法。这一节仅仅是大体介绍了如何使用Ceres进行导数计算最浅显的部分。对Numeric和Auto方法都很熟悉之后,还可以深入研究一下DynamicAutoDiffCostFunction , CostFunctionToFunctor, NumericDiffFunctorConditionedCostFunction,从而实现更高级的代价函数的计算方法。

鲍威尔方程

在这一节我们使用一个复杂一些的例子——求解鲍威尔方程的最小值。我们定义参数块$x = [x_1,x_2,x_3,x_4]$,以及代价函数如下:
$$
\begin{aligned}
&f_1(x) = x_1 + 10x_2 \
&f_2(x) = \sqrt{5}(x_3 - x_4) \
&f_3(x) = (x_2 - 2x_3)^2 \
&f_4(x) = \sqrt{10}(x_1 - x_4)^2 \
&F(x) = [f_1(x),f_2(x),f_3(x),f_4(x)]
\end{aligned}
$$

$F(x)$是关于上面四个残差值得方程。我们希望找到一组$x$,使得$\frac{1}{2}\left |F(x) \right |^2$取得最小值。

同样的,第一步仍然是定义残差方程。对于每一行方程都可以定义一个对应的结构体,如对于$f_4(x_1,x_4)$:

struct F4 {
    template <typename T>
    bool operator()(const T* const x1, const T* const x4, T* residual) const {
        residual[0] = T(sqrt(10.0)) * (x1[0] - x4[0]) * (x1[0] - x4[0]);
        return true;
    }
};

类似的我们也可以实现$f_1$,$f_2$和$f_3$得代码。之后就可以通过下列代码,把各个残差块加入到Problem中。

double x1 =  3.0; double x2 = -1.0; double x3 =  0.0; double x4 = 1.0;

Problem problem;

// Add residual terms to the problem using the using the autodiff
// wrapper to get the derivatives automatically.
problem.AddResidualBlock(
    new AutoDiffCostFunction<F1, 1, 1, 1>(new F1), nullptr, &x1, &x2);
problem.AddResidualBlock(
    new AutoDiffCostFunction<F2, 1, 1, 1>(new F2), nullptr, &x3, &x4);
problem.AddResidualBlock(
    new AutoDiffCostFunction<F3, 1, 1, 1>(new F3), nullptr, &x2, &x3)
problem.AddResidualBlock(
    new AutoDiffCostFunction<F4, 1, 1, 1>(new F4), nullptr, &x1, &x4);

注意每个残差块只依赖与两个参数,而不是全部四个参数。运行结果如下:

Initial x1 = 3, x2 = -1, x3 = 0, x4 = 1
iter      cost      cost_change  |gradient|   |step|    tr_ratio  tr_radius  ls_iter  iter_time  total_time
  0  1.075000e+02    0.00e+00    1.55e+02   0.00e+00   0.00e+00  1.00e+04       0    4.95e-04    2.30e-03
  1  5.036190e+00    1.02e+02    2.00e+01   2.16e+00   9.53e-01  3.00e+04       1    4.39e-05    2.40e-03
  2  3.148168e-01    4.72e+00    2.50e+00   6.23e-01   9.37e-01  9.00e+04       1    9.06e-06    2.43e-03
  3  1.967760e-02    2.95e-01    3.13e-01   3.08e-01   9.37e-01  2.70e+05       1    8.11e-06    2.45e-03
  4  1.229900e-03    1.84e-02    3.91e-02   1.54e-01   9.37e-01  8.10e+05       1    6.91e-06    2.48e-03
  5  7.687123e-05    1.15e-03    4.89e-03   7.69e-02   9.37e-01  2.43e+06       1    7.87e-06    2.50e-03
  6  4.804625e-06    7.21e-05    6.11e-04   3.85e-02   9.37e-01  7.29e+06       1    5.96e-06    2.52e-03
  7  3.003028e-07    4.50e-06    7.64e-05   1.92e-02   9.37e-01  2.19e+07       1    5.96e-06    2.55e-03
  8  1.877006e-08    2.82e-07    9.54e-06   9.62e-03   9.37e-01  6.56e+07       1    5.96e-06    2.57e-03
  9  1.173223e-09    1.76e-08    1.19e-06   4.81e-03   9.37e-01  1.97e+08       1    7.87e-06    2.60e-03
 10  7.333425e-11    1.10e-09    1.49e-07   2.40e-03   9.37e-01  5.90e+08       1    6.20e-06    2.63e-03
 11  4.584044e-12    6.88e-11    1.86e-08   1.20e-03   9.37e-01  1.77e+09       1    6.91e-06    2.65e-03
 12  2.865573e-13    4.30e-12    2.33e-09   6.02e-04   9.37e-01  5.31e+09       1    5.96e-06    2.67e-03
 13  1.791438e-14    2.69e-13    2.91e-10   3.01e-04   9.37e-01  1.59e+10       1    7.15e-06    2.69e-03

Ceres Solver v1.12.0 Solve Report
----------------------------------
                                        Original                  Reduced
Parameter blocks                            4                        4
Parameters                                  4                        4
Residual blocks                             4                        4
Residual                                    4                        4

Minimizer                        TRUST_REGION

Dense linear algebra library            EIGEN
Trust region strategy     LEVENBERG_MARQUARDT

                                        Given                     Used
Linear solver                        DENSE_QR                 DENSE_QR
Threads                                     1                        1
Linear solver threads                       1                        1

Cost:
Initial                          1.075000e+02
Final                            1.791438e-14
Change                           1.075000e+02

Minimizer iterations                       14
Successful steps                           14
Unsuccessful steps                          0

Time (in seconds):
Preprocessor                            0.002

Residual evaluation                     0.000
Jacobian evaluation                     0.000
Linear solver                           0.000
Minimizer                               0.001

Postprocessor                           0.000
Total                                   0.005

Termination:                      CONVERGENCE (Gradient tolerance reached. Gradient max norm: 3.642190e-11 <= 1.000000e-10)

Final x1 = 0.000292189, x2 = -2.92189e-05, x3 = 4.79511e-05, x4 = 4.79511e-05

曲线拟合(Curve Fitting)

最小二乘法和非线性最小二乘分析得本来目的就是对一组数据进行曲线拟合。本节将介绍曲线拟合得问题。本节所用的采样点根据$y = e^{0.3x + 0.1}$生成,并且加入标准差为$\sigma = 0.2$高斯噪声。这$2n$个数据,存入data[]中。下面我们用下列带未知参数的方程来拟合这些采样点:
$$y = e^{mx+c}$$
同样的,我们定义一个用来计算残差的结构体。注意,对应每个采样点(观测点)都要计算一个残差。

struct ExponentialResidual {
    ExponentialResidual(double x, double y)
        : x_(x), y_(y) {}

template <typename T>
bool operator()(const T* const m, const T* const c, T* residual) const {
    residual[0] = y_ - exp(m[0] * x_ + c[0]);
    return true;
}

private:
// Observations for a sample.
const double x_;
const double y_;
};

下面构造Problem

double m = 0.0;
double c = 0.0;

Problem problem;
for (int i = 0; i < kNumObservations; ++i) {
    CostFunction* cost_function =
        new AutoDiffCostFunction<ExponentialResidual, 1, 1, 1>(
            new ExponentialResidual(data[2 * i], data[2 * i + 1]));
    problem.AddResidualBlock(cost_function, nullptr, &m, &c);
}

这里我们再次和Hello World进行对比:

struct CostFunctor {
    template <typename T>
    bool operator()(const T* const x, T* residual) const {
        residual[0] = T(10.0) - x[0];
        return true;
    }
};

CostFunction* cost_function =
    new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);
problem.AddResidualBlock(cost_function, NULL, &x);

通过对比,可以发现。在Hello World中,CostFunctor中是没有(显式)构造函数的,也就同样没有了初始值。所以在构造对象时,可以直接New CostFuntor。而在本节的曲线拟合例子中,构造对象时还要加上初始值new ExponentialResidual(data[2 * i], data[2 * i + 1]))。在方括号中的参数分别对应残差函数名<ExponentialResidual>,以及输出值(residual)的维度1,还有残差函数各个输入值(m,c)维度<1,1>。所以在本例中一共有三个1,而在Hello World中,只有两个1,即residual和x的维度。注意先是残差,后是输入参数,而且一一对应。

最后一点就是在把残差块加入problem的过程中,要把输入变量一一带入。比如&m,&c,&x等。以上就是在构建Problem的时候需要顾及到的三个方面。再就是在使用Numeric算法时,还要在方括号中指定计算机如何计算导数,如ceres::CENTRAL

运行程序,得到下列结果:

iter      cost      cost_change  |gradient|   |step|    tr_ratio  tr_radius  ls_iter  iter_time  total_time
 0  1.211734e+02    0.00e+00    3.61e+02   0.00e+00   0.00e+00    1.00e+04       0    5.34e-04    2.56e-03
 1  1.211734e+02   -2.21e+03    0.00e+00   7.52e-01  -1.87e+01    5.00e+03       1    4.29e-05    3.25e-03
 2  1.211734e+02   -2.21e+03    0.00e+00   7.51e-01  -1.86e+01    1.25e+03       1    1.10e-05    3.28e-03
 3  1.211734e+02   -2.19e+03    0.00e+00   7.48e-01  -1.85e+01    1.56e+02       1    1.41e-05    3.31e-03
 4  1.211734e+02   -2.02e+03    0.00e+00   7.22e-01  -1.70e+01    9.77e+00       1    1.00e-05    3.34e-03
 5  1.211734e+02   -7.34e+02    0.00e+00   5.78e-01  -6.32e+00    3.05e-01       1    1.00e-05    3.36e-03
 6  3.306595e+01    8.81e+01    4.10e+02   3.18e-01   1.37e+00    9.16e-01       1    2.79e-05    3.41e-03
 7  6.426770e+00    2.66e+01    1.81e+02   1.29e-01   1.10e+00    2.75e+00       1    2.10e-05    3.45e-03
 8  3.344546e+00    3.08e+00    5.51e+01   3.05e-02   1.03e+00    8.24e+00       1    2.10e-05    3.48e-03
 9  1.987485e+00    1.36e+00    2.33e+01   8.87e-02   9.94e-01    2.47e+01       1    2.10e-05    3.52e-03
10  1.211585e+00    7.76e-01    8.22e+00   1.05e-01   9.89e-01    7.42e+01       1    2.10e-05    3.56e-03
11  1.063265e+00    1.48e-01    1.44e+00   6.06e-02   9.97e-01    2.22e+02       1    2.60e-05    3.61e-03
12  1.056795e+00    6.47e-03    1.18e-01   1.47e-02   1.00e+00    6.67e+02       1    2.10e-05    3.64e-03
13  1.056751e+00    4.39e-05    3.79e-03   1.28e-03   1.00e+00    2.00e+03       1    2.10e-05    3.68e-03
Ceres Solver Report: Iterations: 13, Initial cost: 1.211734e+02, Final cost: 1.056751e+00, Termination: CONVERGENCE
Initial m: 0 c: 0
Final   m: 0.291861 c: 0.131439

最终经过计算,结果是m=0.291861,c=0.131439。这个值和一开始的设定值(m=0.3,c=0.1)略有偏差。因为额外加入了高斯噪声,所以这个偏差的存在是合理的。拟合结果如下图所示,红圈即为拟合出的曲线。

曲线拟合效果

鲁棒的曲线拟合(Robust Curve Fitting)

如果我们在数据集合中加入几个非常夸张的外围点Outliers,那么拟合结果会受到这几个点的明显影响。在这个时候需要应用损失函数(Loss function)来对异常数据进行过滤。比如在上文的例子中,我们对代码进行以下修改:

problem.AddResidualBlock(cost_function, NULL , &m, &c);

改为:

problem.AddResidualBlock(cost_function, new CauchyLoss(0.5) , &m, &c);

CauchyLoss是Ceres Solver附带的损失函数之一。 参数0.5指定了损失函数的规模。通过对下面两个图的对比,我们可以明显的发现损失函数的作用。

非鲁棒性的拟合效果

鲁棒性的拟合效果

关于微分计算(On Derivatives)

与所有基于梯度的优化算法一样,Ceres Solver也是基于评估域中任意点的目标函数及其导数。事实上,Ceres的核心就是确定目标函数机器雅可比行列式。雅可比行列式求解的正确性和效率是评判算法优劣的关键指标。用户可以灵活的从一下三种微分算法中选择:

  • 解析微分算法(Analytic Derivatives):用户自己手动或者借助Maple或者Mathematica等工具求解导数,然后写到CostFunction里面。
  • 数值微分算法(Numeric Derivatives):Ceres用有限差分数值计算导数
  • 自动微分算法(Automatic Dericatives):Ceres用C++模板和操作符重载自动分析计算微分。

应该使用这三种方法中的哪一种(单独或组合)取决于用户愿意做出的情况和权衡。官方给出了一个简单粗暴的建议:
优先选用自动微分算法,某些情况可能需要用到解析微分算法,尽量避免数值微分算法。

Spivak标记

为了简化阅读和推理,引入Spivak标记。

对于单自变量函数$f$,$f(a)$表示它在$a$处的函数值。$Df$表示它的一阶导数,那么$Df(a)$就是函数在$a$处的一阶导数。即,

$$Df(a) = \frac{d}{dx}f(x)|_{x=a}$$

$D^kf$表示$f$的第$k$阶导数。

对于双自变量函数$g(x,y)$,$D_1g$和$D_2g$分别表示关于$g$的两个偏微分。即,

$$D_1g = \frac{\partial}{\partial x}g(x,y)andD_2g = \frac{\partial}{\partial y}g(x,y)$$

$D_g$表示$g$的雅可比矩阵

雅可比矩阵即

$$
\begin{bmatrix}
\frac{\partial y_1}{\partial x_1}& \cdots & \frac{\partial y_1}{\partial x_n}\
\vdots & \ddots & \vdots\
\frac{\partial y_m}{\partial x_1}& \cdots & \frac{\partial y_m}{\partial x_n}
\end{bmatrix}
$$

这里的$y_1$即$g$,其他的行不存在,因为只存在一个因变量$g$。即雅可比矩阵是一个一行两列的矩阵。即,

$$Dg = \begin{bmatrix}
D_1g& D_2g
\end{bmatrix}$$

更一般的,如果$g:\mathbb{R}^{n} \longrightarrow \mathbb{R}^{m}$,那么$Dg$表示的就是一个$m \times n$的雅可比矩阵。

自动微分法(Automatic Derivatices)

我们来思考一个相对复杂的曲线拟合问题。待确定参数方程如下:

$$ y = \frac{b_1}{(1+e^{b_2 - b_3x})^{1/b_4}}$$

现在给定一系列的对应数据点$\left{x_i,y_i\right },\forall i=1,\cdots,n$。我们面临的问题就是求解$b_1,b_2,b_3,b_4$使下列表达式的取值最小:

$$ \begin{aligned}
E\left(b_{1}, b_{2}, b_{3}, b_{4}\right) &=\sum_{i} f^{2}\left(b_{1}, b_{2}, b_{3}, b_{4} ; x_{i}, y_{i}\right) \
&=\sum_{i}\left(\frac{b_{1}}{\left(1+e^{b_{2}-b_3x_i}\right)^{1 / b_{4}}}-y_{i}\right)^{2}
\end{aligned}$$

下面我们使用自动微分算法,它是一种可以快速计算精确导数的算法。下面的代码片段实现了上述问题的CostFunction

struct Rat43CostFunctor {
    Rat43CostFunctor(const double x, const double y) : x_(x), y_(y) {}

template <typename T>  
bool operator()(const T* parameters, T* residuals) const {
    const T b1 = parameters[0];
    const T b2 = parameters[1];
    const T b3 = parameters[2];
    const T b4 = parameters[3];
    residuals[0] = b1 * pow(1.0 + exp(b2 -  b3 * x_), -1.0 / b4) - y_;
    return true;
}

private:
    const double x_;
    const double y_;
};

CostFunction* cost_function =
    new AutoDiffCostFunction<Rat43CostFunctor, 1, 4>(    
        new Rat43CostFunctor(x, y));

接下来我们对自动微分算法的原理进行研究。为了研究其工作原理,必须要学习 二元数(Dual number) 和 **射流(Jet)**。

二元数和射流

二元数(Dual number) 是实数的一个延伸,类似于复数。复数则通过引入虚数来增加实数,比如$i$,二元数引入了一个极小二元数单位,比如$\epsilon$,且$\epsilon^2 = 0$(平方后太小可以忽略)。一个二元数$a+\upsilon\epsilon$包含两个分量,实分量$a$和极小分量$\upsilon$。令人惊喜的是,这个简单的变化带来了一种方便的计算精确导数的方法,而不需要考虑复杂的符号表达式。

例如,考虑函数

$$ f(x) = x^2$$

然后
$$ \begin{aligned}
f(10+\epsilon) &=(10+\epsilon)^{2} \
&=100+20 \epsilon+\epsilon^{2} \
&=100+20 \epsilon
\end{aligned}$$

观察$\epsilon$的系数,我们发现$Df(10) = 20$。事实上,这个规律可以推广到不是多项式的函数。考虑一个任意可微函数$f(x)$,然后我们计算$f(x+ \epsilon)$,通过在$x$附近做泰勒展开,这就得到了无穷级数

$$
\begin{array}{l}
f(x+\epsilon)=f(x)+D f(x) \epsilon+D^{2} f(x) \frac{\epsilon^{2}}{2}+D^{3} f(x) \frac{\epsilon^{3}}{6}+\cdots \
f(x+\epsilon)=f(x)+D f(x) \epsilon
\end{array}
$$

记住,$\epsilon^2 = 0$。

射流(Jet) 是一个$n$维二元数。我们定义$n$个极小单位$\epsilon_i,i=1,\cdots,n$。并且存在性质$\forall i,j:\epsilon_i\epsilon_j=0$。射流数由实数$a$和$n$维极小分量组成。

$$x = a + \sum_j \upsilon_j \epsilon_j$$

为了简化我们改写为这种形式

$$x = a + \mathbf{v}$$

然后使用泰勒级数展开,我们可以看到:

$$f(a+\mathbf{v}) = f(a) +Df(a)\mathbf{v} $$

对多变量函数$f : \mathbb{R^n} \longrightarrow \mathbb{R^m} $相似。对于自变量$x_i = a_i + \mathbf{v}_i, \forall i = 1,\cdots,n :$

$$f(x_1,\cdots,x_n) = f(a_1,\cdots,a_n) + \sum_i D_if(a_1,\cdots,a_n)\mathbf{v}_i $$

如果每个选取的极小量$\mathbf{v}_i = e_i $是$i^{th}$标准基向量,那么上面的表达式就可以简化为

$$
f(x_1,\cdots,x_n) = f(a_1,\cdots,a_n) + \sum_i D_if(a_1,\cdots,a_n) \epsilon_i
$$

我们可以查找$\epsilon_i$的系数来提取雅可比矩阵的坐标。

实现射流(Jet)

为了让上面学到的内容在实践中发挥作用,我们需要能够计算函数$f$的值,不仅在自变量是实数的时候,也需要在自变量是二元数的情况下适用。但是通常我们并非通过泰勒展开式来求函数值。这也就是为什么我们需要用到C++模板和操作符重载。下面的代码段实现了Jet类以及对该类的一些操作和函数。

template<int N> struct Jet {
    double a;
    Eigen::Matrix<double, 1, N> v;
};

template<int N> Jet<N> operator+(const Jet<N>& f, const Jet<N>& g) {
    return Jet<N>(f.a + g.a, f.v + g.v);
}

template<int N> Jet<N> operator-(const Jet<N>& f, const Jet<N>& g) {
    return Jet<N>(f.a - g.a, f.v - g.v);
}

template<int N> Jet<N> operator*(const Jet<N>& f, const Jet<N>& g) {
    return Jet<N>(f.a * g.a, f.a * g.v + f.v * g.a);
}

template<int N> Jet<N> operator/(const Jet<N>& f, const Jet<N>& g) {
    return Jet<N>(f.a / g.a, f.v / g.a - f.a * g.v / (g.a * g.a));
}

template <int N> Jet<N> exp(const Jet<N>& f) {
    return Jet<T, N>(exp(f.a), exp(f.a) * f.v);
}

// This is a simple implementation for illustration purposes, the
// actual implementation of pow requires careful handling of a number
// of corner cases.
template <int N>  Jet<N> pow(const Jet<N>& f, const Jet<N>& g) {
    return Jet<N>(pow(f.a, g.a),
            g.a * pow(f.a, g.a - 1.0) * f.v +
            pow(f.a, g.a) * log(f.a); * g.v);
}

有了这些重载的函数,我们现在可以用一个Jets数组来调用Rat43CostFunctor,而不是double双精度类型。将其与初始化的Jets结合起来,我们就可以计算雅可比矩阵了:

class Rat43Automatic : public ceres::SizedCostFunction<1,4> {
    public:
      Rat43Automatic(const Rat43CostFunctor* functor) : functor_(functor) {}
      virtual ~Rat43Automatic() {}
      virtual bool Evaluate(double const* const* parameters,
                    double* residuals,
                    double** jacobians) const {
    // Just evaluate the residuals if Jacobians are not required.
    if (!jacobians) return (*functor_)(parameters[0], residuals);

    // 初始化Jets,四个待求参数
    ceres::Jet<4> jets[4];
    for (int i = 0; i < 4; ++i) {
        jets[i].a = parameters[0][i];
        jets[i].v.setZero();
        jets[i].v[i] = 1.0;
    }

    ceres::Jet<4> result;
    (*functor_)(jets, &result);

    // 把Jet的值(前面提到的,极小单位分量的系数)复制出啦.
    residuals[0] = result.a;
    for (int i = 0; i < 4; ++i) {
        jacobians[0][i] = result.v[i];
    }
    return true;
}

private:
    std::unique_ptr<const Rat43CostFunctor> functor_;
};

这就是AutoDiffCostFunction的核心工作原理。

陷阱

自动微分使用户不必计算和推理Jacobians的符号表达式,但是这个捷径是有代价的。例如,考虑以下简单的函数:

struct Functor {
    template <typename T> bool operator()(const T* x, T* residual) const {
        residual[0] = 1.0 - sqrt(x[0] * x[0] + x[1] * x[1]);
        return true;
    }
};

查看计算残差的代码,没有人预见到任何问题。但是,如果我们看一下雅可比矩阵的解析表达式:

$$
\begin{aligned}
y &=1-\sqrt{x_{0}^{2}+x_{1}^{2}} \
D_{1} y &=-\frac{x_{0}}{\sqrt{x_{0}^{2}+x_{1}^{2}}}, D_{2} y=-\frac{x_{1}}{\sqrt{x_{0}^{2}+x_{1}^{2}}}
\end{aligned}
$$

我们发现它在$x_0 = 0,x_1 = 0$处是不确定的。

这个问题没有完美的解决方案。在某些情况下,我们需要明确地指出可能出现的不确定的点,并使用使用L’Hopital rule(这里要去Ceres Solvel官网的rotation.h文件中的转换例程),在其他情况下,可能需要对表达式进行正则化,以消除这些点。

While we were so young

我梦到当时 我们翻过墙

曼陀罗花 沿途绽放

我们光脚越过人间荒唐

We’re stupid but strong

放学的屋顶 像万人广场

从不多想 只是信仰

少年回头望 笑我还不快跟上

那路的起点谁能忘

那路的尽头谁在唱

谁成名在望 谁曾失望

却更多 的谁在盼望

那黑的终点可有光

那夜的尽头天将亮

那成名在望 无关真相

如果你 心始终信仰 谁又能怎样

谁又能怎样 你就能飞翔

你就能飞翔 你就能飞翔

安装过程

今天比较有时间,正好看完了CVPR-2018年的论文<**Single Image Reflection Separation with Perceptual Losses**>,这里不多介绍这篇论文相关的东西了。因为跑这个数据的话,自己的电脑当时在Windows下装的Tensorflow,但是作者给的运行策略是Ubuntu下,所以问了一下学长,他说可以在Windows下安装PyTorch来跑。下面就记录一下自己安装PyTorch的过程。

1.由于之前安装了Anaconda3,所以可以采用conda安装的方式,但是之前安装Tensorflow的时候Python版本的问题就一直有点疑问,所以查了一下发现如果只是想利用Pycharm运行PyTorch的话,其实直接用pip方式安装就可以

2.那么需要到PyTorch官网去查看自己所需的代码 PyTorch官网连接,相应的选择自己电脑的配置,注意如果用pip安装的话,要选择Pip选项。然后下面就会给出你所需的命令。还要注意的一点是我的电脑由于是A卡的,所以在CUDA这个部分我选择的是None,也就是所说的CPU版本的PyTorch。本人的命令如下:

pip3 install torch==1.2.0+cpu torchvision==0.4.0+cpu -f https://download.pytorch.org/whl/torch_stable.html

3.安装成功后,一定要记得看一下自己所安装的文件夹地址

4.打开Pycharm,按ctrl+alt+s,打开Project Interpreter进行配置,点击右上角的设置符号,选择Add,在下面点选Existing environment,然后在右边的…处找到自己刚才安装的文件夹地址,拉到最下面找到python.exe文件一路点击ok

5.在pycharm中新建项目,输入以下代码:

from __future__ import print_function
import torch
x=torch.rand(5,3)
print(x)

查看输出,如果输出为:

tensor([[0.9072, 0.3848, 0.9203],
        [0.1643, 0.7447, 0.1730],
        [0.4379, 0.2974, 0.1283],
        [0.4563, 0.5322, 0.9924],
        [0.4715, 0.9287, 0.7176]])

Process finished with exit code 0

证明PyTorch安装成功!

第十章


并发编程

并发(concurrency)

  • 定义:指的是多线程场景下对共享资源的争夺运行
  • 并发的应用背景:
    • 网络上的多台计算机
    • 一台计算机上的多个应用
    • 一个CPU上的多核处理器
  • 为什么要有并发:
    • 摩尔定律失效、“核”变得越来越多
    • 为了充分利用多核和多处理器需要将程序转化为并行执行
  • 并发编程的两种模式:
    • 共享内存:在内存中读写共享数据
    • 信息传递(Message Passing):通过channel交换消息

共享内存

  • 共享内存这种方式比较常见,我们经常会设置一个共享变量,然后多个线程去操作同一个共享变量。从而达到线程通讯的目的。
  • 例子:
    • 两个处理器,共享内存
    • 同一台机器上的两个程序,共享文件系统
    • 同一个Java程序内的两个线程,共享Java对象

信息传递

  • 消息传递方式采取的是线程之间的直接通信,不同的线程之间通过显式的发送消息来达到交互目的
  • 接收方将收到的消息形成队列逐一处理,消息发送者继续发送(异步方式)
  • 消息传递机制也无法解决竞争条件问题
  • 仍然存在消息传递时间上的交错
  • 例子:
    • 网络上的两台计算机,通过网络连接通讯
    • 浏览器和Web服务器,A请求页面,B发送页面数据给A
    • 即时通讯软件的客户端和服务器
    • 同一台计算机上的两个程序,通过管道连接进行通讯
并发模型 通信机制 同步机制
共享内存 线程之间共享程序的公共状态,线程之间通过写-读内存中的公共状态来隐式进行通信。 同步是显式进行的。程序员必须显式指定某个方法或某段代码需要在线程之间互斥执行。
消息传递 线程之间没有公共状态,线程之间必须通过明确的发送消息来显式进行通信。 由于消息的发送必须在消息的接收之前,因此同步是隐式进行的。

进程和线程

  • 进程:是执行中一段程序,即一旦程序被载入到内存中并准备执行,它就是一个进程。进程是表示资源分配的的基本概念,又是调度运行的基本单位,是系统中的并发执行的单位。
    • 程序运行时在内存中分配自己独立的运行空间
    • 进程拥有整台计算机的资源
    • 多进程之间不共享内存
    • 进程之间通过消息传递进行协作
    • 一般来说,进程==程序==应用(但一个应用中可能包含多个进程)
    • OS支持的IPC机制(pipe/socket)支持进程间通信(IPC不仅是本机的多个进程之间, 也可以是不同机器的多个进程之间)
    • JVM通常运行单一进程,但也可以创建新的进程。
  • 线程:它是位于进程中,负责当前进程中的某个具备独立运行资格的空间。
    • 线程有自己的堆栈和局部变量,但是多个线程共享内存空间
    • 进程=虚拟机;线程=虚拟CPU
    • 程序共享、资源共享,都隶属于进程
    • 很难获得线程私有的内存空间
    • 线程需要同步:在改变对象时要保持lock状态
    • 清理线程是不安全的
  • 进程是负责整个程序的运行,而线程是程序中具体的某个独立功能的运行。
  • 一个进程中至少应该有一个线程。
  • 主线程可以创建其他的线程。

线程的创建和启动

方式1:继承Thread

  • 方法:用Thread类实现了Runnable接口,但它其中的run方法什么都没做,所以用一个类做Thread的子类,提供它自己实现的run方法。用Thread.start()来开始一个新的线程。
  • 创建:A a = new A();
  • 启动:a.start();
  • 步骤:
    • 定义一个类A继承于java.lang.Thread类.
    • A类中覆盖Thread类中的run方法.
    • 我们在run方法中编写需要执行的操作:run方法里的代码,线程执行体.
    • main方法(线程)中,创建线程对象,并启动线程.
  • examples
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//1):定义一个类A继承于java.lang.Thread类.  
class MusicThread extends Thread{
//2):在A类中覆盖Thread类中的run方法.
public void run() {
//3):在run方法中编写需要执行的操作
for(int i = 0; i < 50; i ++){
System.out.println("播放音乐"+i);
}
}
}

public class ExtendsThreadDemo {
public static void main(String[] args) {
for(int j = 0; j < 50; j ++){
System.out.println("运行游戏"+j);
if(j == 10){
//4):在main方法(线程)中,创建线程对象,并启动线程.
MusicThread music = new MusicThread();
music.start();
}
}
}
}

方式2:实现Runable接口

  • 创建Thread t = new Thread(new A());
  • 调用t.start();
  • 步骤
    • 定义一个类A实现于java.lang.Runnable接口,注意A类不是线程类.
    • 在A类中覆盖Runnable接口中的run方法.
    • 我们在run方法中编写需要执行的操作:run方法里的,线程执行体.
    • main方法(线程)中,创建线程对象,并启动线程.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//1):定义一个类A实现于java.lang.Runnable接口,注意A类不是线程类.  
class MusicImplements implements Runnable{
//2):在A类中覆盖Runnable接口中的run方法.
public void run() {
//3):在run方法中编写需要执行的操作
for(int i = 0; i < 50; i ++){
System.out.println("播放音乐"+i);
}

}
}

public class ImplementsRunnableDemo {
public static void main(String[] args) {
for(int j = 0; j < 50; j ++){
System.out.println("运行游戏"+j);
if(j == 10){
//4):在main方法(线程)中,创建线程对象,并启动线程
MusicImplements mi = new MusicImplements();
Thread t = new Thread(mi);
t.start();
}
}
}
}
  • 实现Runnable接口相比继承Thread类有如下好处:

    • 避免点继承的局限,一个类可以继承多个接口。
    • 适合于资源的共享
  • 创建并运行一个线程所犯的常见错误是调用线程的run()方法而非start()方法,如下所示:

1
2
Thread newThread = new Thread(MyRunnable());
newThread.run(); //should be start();

  起初并不会感觉到有什么不妥,因为run()方法的确如你所愿的被调用了。但是,事实上,run()方法并非是由刚创建的新线程所执行的,而是被创建新线程的当前线程所执行了。也就是被执行上面两行代码的线程所执行的。想要让创建的新线程执行run()方法,必须调用新线程的start()方法。

时间分片、交错执行、竞争条件

时间分片

  • 虽然有多线程,但只有一个核,每个时刻只能执行一个线程。
    • 通过时间分片,再多个线程/进程之间共享处理器
  • 即使是多核CPU,进程/线程的数目也往往大于核的数目
  • 通过时间分片,在多个进程/线程之间共享处理器。(时间分片是由OS自动调度的)
  • 当线程数多于处理器数量时,并发性通过时间片来模拟,处理器切换处理不同的线程

交错执行

  顾名思义,就是说在线程运行的过程中,多个线程同时运行相互交错。而且,由于线程运行一般不是连续的,那么就会导致线程间的交错。可以说,所有线程安全问题的本质都是线程交错的问题。

竞争条件

  竞争是发生在线程交错的基础上的。当多个线程对同一对象进行读写访问时,就可能会导致竞争的问题。程序中可能出现的一种问题就是,读写数据发生了不同步。例如,我要用一个数据,在该数据修改还没写回内存中时就读取出来了,那么就会导致程序出现问题。

  程序运行时有一种情况,就是程序如果要正确运行,必须保证A线程在B线程之前完成(正确性意味着程序运行满足其规约)。当发生这种情况时,就可以说A与B发生竞争关系。

  • 计算机运行过程中,并发、无序、大量的进程在使用有限、独占、不可抢占的资源,由于进程无限,资源有限,产生矛盾,这种矛盾称为竞争(Race)。
  • 由于两个或者多个进程竞争使用不能被同时访问的资源,使得这些进程有可能因为时间上推进的先后原因而出现问题,这叫做竞争条件(Race Condition)。
  • 竞争条件分为两类:
    -Mutex(互斥):两个或多个进程彼此之间没有内在的制约关系,但是由于要抢占使用某个临界资源(不能被多个进程同时使用的资源,如打印机,变量)而产生制约关系。
    -Synchronization(同步):两个或多个进程彼此之间存在内在的制约关系(前一个进程执行完,其他的进程才能执行),如严格轮转法。
  • 解决互斥方法:
    Busy Waiting(忙等待):等着但是不停的检查测试,不睡觉,知道能进行为止
    Sleep and Wakeup(睡眠与唤醒):引入Semapgore(信号量,包含整数和等待队列,为进程睡觉而设置),唤醒由其他进程引发。
  • 临界区(Critical Region):
    • 一段访问临界资源的代码。
    • 为了避免出现竞争条件,进入临界区要遵循四条原则:
      • 任何两个进程不能同时进入访问同一临界资源的临界区
      • 进程的个数,CPU个数性能等都是无序的,随机的
      • 临界区之外的进程不得阻塞其他进程进入临界区
      • 任何进程都不应被长期阻塞在临界区之外
  • 解决互斥的方法:
    • 禁用中断 Disabling interrupts
    • 锁变量 Lock variables (no)
    • 严格轮转 Strict alternation (no)
    • Peterson’s solution (yes)
    • The TSL instruction (yes)

线程的休眠、中断

Thread.sleep

  • 在线程中允许一个线程进行暂时的休眠,直接使用Thread.sleep()方法即可。
    • 将某个线程休眠,意味着其他线程得到更多的执行机会
    • 进入休眠的线程不会失去对现有monitor或锁的所有权
  • sleep定义格式:
1
2
public static void sleep(long milis,int nanos)
throws InterruptedException

  首先,**static,说明可以由Thread类名称调用,其次throws表示如果有异常要在调用此方法处处理异常**。

所以sleep()方法要有InterruptedException异常处理,而且sleep()调用方法通常为Thread.sleep(500);形式。

Thread.interrupt

  • 一个线程可以被另一个线程中断其操作的状态,使用interrupt()方法完成。

    • 通过线程的实例来调用interrupt()函数,向线程发出中断信号
    • t.interrupt():在其他线程里向t发出中断信号
    • t.isInterrupted():检查t是否已在中断状态中
  • 当某个线程被中断后,一般来说应停止其run()中的执行,取决于程序员在run()中处理

    • 一般来说,线程在收到中断信号时应该中断,直接终止
    • 但是,线程收到其他线程发出来的中断信号,并不意味着一定要“停止”
  • 实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package Thread1;
class MyThread implements Runnable{ // 实现Runnable接口
public void run(){ // 覆写run()方法
System.out.println("1、进入run()方法") ;
try{
Thread.sleep(10000) ; // 线程休眠10秒
System.out.println("2、已经完成了休眠") ;
}catch(InterruptedException e){
System.out.println("3、休眠被终止") ;
return ; // 返回调用处
}
System.out.println("4、run()方法正常结束") ;
}
};
public class demo1{
public static void main(String args[]){
MyThread mt = new MyThread() ; // 实例化Runnable子类对象
Thread t = new Thread(mt,"线程"); // 实例化Thread对象
t.start() ; // 启动线程
try{
Thread.sleep(2000) ; // 线程休眠2秒
}catch(InterruptedException e){
System.out.println("3、休眠被终止") ;
}
t.interrupt() ; // 中断线程执行
}
};

运行结果:

1
2
1、进入run()方法
3、休眠被终止

线程安全的四个策略

  • 线程安全的定义:ADT或方法在多线程中要执行正确,即无论如何执行,不许调度者做额外的协作,都能满足正确性
  • 四种线程安全的策略:
    • Confinement 限制数据共享
    • Immutability 共享不可变数据
    • Threadsafe data type 共享线程安全的可变数据
    • Synchronization 同步机制共享共享线程不安全的可变数据,对外即为线程安全的ADT.

Confinement限制数据共享

  • 核心思想:线程之间不共享mutable数据类型
    • 将可变数据限制在单一线程内部,避免竞争
    • 不允许任何县城直接读写该数据
  • 在多线程环境中,取消全局变量,尽量避免使用不安全的静态变量。
    • 限制数据共享主要是在线程内部使用局部变量,因为局部变量在每个函数的栈内,每个函数都有自己的栈结构,互不影响,这样局部变量之间也互不影响。
    • 如果局部变量是一个指向对象的引用,那么就需要检查该对象是否被限制住,如果没有被限制住(即可以被其他线程所访问),那么就没有限制住数据,因此也就不能用这种方法来保证线程安全
  • examples
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Factorial {

/**
* Computes n! and prints it on standard output.
* @param n must be >= 0
*/
private static void computeFact(final int n) {
BigInteger result = new BigInteger("1");
for (int i = 1; i <= n; ++i) {
System.out.println("working on fact " + n);
result = result.multiply(new BigInteger(String.valueOf(i)));
}
System.out.println("fact(" + n + ") = " + result);
}

public static void main(String[] args) {
new Thread(new Runnable() { // create a thread using an
public void run() { // anonymous Runnable
computeFact(99);
}
}).start();
computeFact(100);
}
}

解释:主函数开启了两个线程,调用的是相同函数。因为线程共享局部变量的类型,但每个函数调用有不同的栈,因此有不同的i, n, result。由于每个函数都有自己的局部变量,那么每个函数就可以独立运行,更新它们自己的函数值,线程之间不影响结果。

Immutability共享不可变数据

不可变数据类型,指那些在整个程序运行过程中,指向内存的引用是一直不变的,通常使用final来修饰。不可变数据类型通常来讲是线程安全的,但也可能发生意外。

但是,程序在运行过程中,有时为了优化程序结构,默默地将这个引用更改了。此时,客户端程序员是不知道它被更改了,对于客户端而言,这个引用还是不可变的,但其实已经被悄悄更改了。这时就会发生一些线程安全问题。

解决方案就是给这些不可变数据类型再增加一些限制:

  • 所有的方法和属性都是私有的。
  • 不提供可变的方法,即不对外开放可以更改内部属性的方法。
  • 没有数据的泄露,即返回值而不是引用。
  • 不在其中存储可变数据对象。

这样就可以保证线程的安全了。

Threadsafe data type(共享线程安全的可变数据)

  • 方法:如果必须要用mutable的数据类型在多线程之间共享数据,要使用线程安全的数据类型。(在JDK中的类,文档中明确指明了是否threadsafe)
  • 一般来说,JDK同时提供两个相同功能的类,一个是threadsafe,另一个不是。原因:threadsafe的类一般性能上受影响。
  • List、Set、Map这些集合类都是线程不安全的,Java API为这些集合类提供了进一步的decorator
1
2
3
4
5
6
7
private static Map<Integer,Boolean> cache = Collections.synchronizedMap(new HashMap<>());
public static <T> Collection<T> synchronizedCollection(Collection<T> c);
public static <T> Set<T> synchronizedSet(Set<T> s);
public static <T> List<T> synchronizedList(List<T> list);
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m);
public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s);
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m);
  • 在使用synchronizedMap(hashMap)之后,不要再把参数hashMap共享给其他线程,不要保留别名,一定要彻底销毁.(可以用private static Map cache = Collections.synchronizedMap(new HashMap<>());的方式实例化集合类)
  • 即使在线程安全的集合类上,使用iterator也是不安全的:
1
2
3
4
5
6
List<Type> c = Collections.synchronizedList(new
ArrayList<Type>());
synchronized(c) { // to be introduced later (the 4-th threadsafe way)
for (Type e : c)
foo(e);
}
  • 需要注意用java提供的包装类包装集合后,只是将集合的每个操作都看成了原子操作,也就保证了每个操作内部的正确性,但是在两个操作之间不能保证集合类不被修改,因此需要用lock机制,例如

  如果在isEmptyget中间,将元素移除,也就产生了竞争。

前三种策略的核心思想:避免共享$\to$即使共享,也只能读/不可写(immutable)$\to$即使可写(mutable),共享的可写数据应自己具备在多线程之间协调的能力,即“使用线程安全的mutable ADT”

Synchronization同步与锁

  • 为什么要同步

    • java允许多线程并发控制,当多个线程同时操作一个可共享的资源变量时(如数据的增删改查)
    • 将会导致数据不准确,相互之间产生冲突,因此加入同步锁以避免在该线程没有完成操作之前,被其他线程的调用
    • 保证了该变量的唯一性和准确性
  • 同步方法

    • 即有synchronized关键字修饰的方法。

    • 由于java的每个对象都有一个内置锁,当用此关键字修饰方法时,内置锁会保护整个方法。

    • 在调用该方法前,需要获得内置锁,否则就处于阻塞状态。

    • 代码如下:

      1
      public synchronized void save(){} 
    • 注:`synchronized`关键字也可以修饰静态方法,此时如果调用该静态方法,将会锁住整个类
      
  • 同步代码块

-   在调用该方法前,需要获得内置锁,否则就处于阻塞状态。

-   被该关键字修饰的语句块会自动被加上内置锁,从而实现同步。

-   代码如:

    
1
synchronized(object){...}
- 注:同步是一种高开销的操作,因此应该尽量减少同步的内容。
  • 使用锁机制,获得对数据的独家mutation权,其他线程被阻塞,不得访问

  • Lock是Java语言提供的内嵌机制,每个object都有相关联的lock

  • 任何共享的mutable变量/对象必须被lock所保护

  • 涉及到多个mutable变量的时候,它们必须被同一个lock所保护

死锁

  • 定义:两个或多个线程相互等待对方释放锁,则会出现死锁现象。

  • java虚拟机没有检测,也没有采用措施来处理死锁情况,所以多线程编程是应该采取措施避免死锁的出现。一旦出现死锁,整个程序即不会发生任何异常,也不会给出任何提示,只是所有线程都处于堵塞状态。

  • 形成死锁的条件:

    • 互斥条件:线程使用的资源必须至少有一个是不能共享的(至少有锁);
    • 请求与保持条件:至少有一个线程必须持有一个资源并且正在等待获取一个当前被其它线程持有的资源(至少两个线程持有不同锁,又在等待对方持有锁);
    • 非剥夺条件:分配资源不能从相应的线程中被强制剥夺(不能强行获取被其他线程持有锁);
    • 循环等待条件:第一个线程等待其它线程,后者又在等待第一个线程(线程$A$等线程$B$;线程$B$等线程$C$; $\cdots$ ;线程$N$等线程$A$。如此形成环路)。
  • 防止死锁的方法:

    • 加锁顺序:当多个线程需要相同的一些锁,但是按照不同的顺序加锁,死锁就很容易发生。如果能确保所有的线程都是按照相同的顺序获得锁,那么死锁就不会发生。这种方式是一种有效的死锁预防机制。但是,这种方式需要你事先知道所有可能会用到的锁,但总有些时候是无法预知的
    • 使用粗粒度的锁,用单个锁来监控多个对象

      • 对整个社交网 络设置 一个锁 ,并且对其任何组成部分的所有操作都在该锁上进行同步。
      • 例如:所有的Wizards都属于一个Castle, 可使用 castle 实例的锁

        缺点:性能损失大;

      • 如果用一个锁保护大量的可变数据,那么久放弃了同时访问这些数据的能力;
      • 在最糟糕的情况下,程序可能基本上是顺序执行的,丧失了并发性
    • 加锁时限:在尝试获取锁的时候加一个超时时间,这也就意味着在尝试获取锁的过程中若超过了这个时限该线程则放弃对该锁请求。若一个线程没有在给定的时限内成功获得所有需要的锁,则会进行回退并释放所有已经获得的锁。
    • 用 jstack 等工具进行死锁检测

以注释的形式撰写线程安全策略

  • 在代码中以注释的形式添加说明:该ADT采取了什么设计决策来保证线程安全

  • 阐述如何使rep线程安全;

  • 写入表示不变性的说明中,以便代码维护者知道你是如何为类设计线程安全性的。

  • 需要对安全性进行这种仔细的论证,阐述使用了哪种技术,使用threadsafe data types, or synchronization时,需要论证所有对数据的访问都是具有原子性的

  • 字符串是不可变的并且是线程安全的; 但是指向该字符串的rep,特别是文本变量,并不是不可变的;

  • 文本不是最终变量,因为我们需要数据类型来支持插入和删除操作;

  • 因此读取和写入文本变量本身不是线程安全的。

第八章

第一节 软件构造性能的度量原理

性能度量指标

  • 时间性能
    • 每条指令、每个控制 结构、整个程序的执行时间
    • 不同语句或控制结构执行时间的分布情况
    • 时间瓶颈在哪里
  • 空间性能
    • 每个变量、每个复杂结构、整个程序的内存消耗
    • 不同变量/数据结构的相对消耗
    • 空间瓶颈在哪里
    • 随时间的变化情况

内存管理

对象管理模型

  • 三者的差异在于:如何与何时在程序对象与内存对象之间建立联系

  • 静态

    • 定义:静态内存是指在程序开始运行时由编译器分配的内存,它的分配是在程序开始编译时完成的,不占用CPU资源。
    • 程序中的各种变量,在编译时系统已经为其分配了所需的内存空间,当该变量在作用域内使用完毕时,系统会自动释放所占用的内存空间;
    • 不支持递归,不支持动态创建可变长的复杂数据类型;
    • 在程序执行期内实体至多关联一个运行时对象
    • eg: 基本类型,数组
  • 动态-基于栈

    • 栈定义:方法调用和局部变量的存储位置,保存基本类型
      • 如果一个方法被调用,它的栈帧被放到调用栈的顶部
      • 栈帧保存方法的状态,包括执行哪行代码以及所有局部变量的值
      • 栈顶始终是当前运行方法
    • 一个实体可以在运行时连续地连接到多个对象,并且运行时机制以堆栈中的后进先出顺序分配和释放这些对象
    • 栈无法支持复杂数据结构
  • 动态-基于堆

    • 堆定义:在一块内存里分为多个小块,每块包含 一个对象,或者未被占用
    • 自由模式的内存管理,动态分配,可管理复杂的动态数据结构
    • 代码中的一个变量可以在不同时间被关联到不同的内存对象上,无法在编译阶段确定。内存对象也可以进一步指向其他对象

Java垃圾回收机制

内存回收的三种方式

​ ①静态模式下的内存回收:在静态内存分配模式下,无需进行内存回收:所有都是已确定的。

​ ②在栈模式下的内存回收:按block(某个方法)整体进行

​ ③在堆模式下的内存回收:在heap上进行内存空间回收,最复杂——无法提前预知某个object是否已经变得无用。

动态垃圾回收相关概念

  • GC(Garbage Collection):识别垃圾并释放其占用的内存
    • 垃圾回收器根据对象的“活性”(从root的可达性)来决定是否回收该对象的内存,”死“的对象是需要回收的垃圾
  • Root
    • 根集合由root对象和局部对象构成
    • root对象:Class(不能被回收)、Thread、Java方法/接口的本地变量或参数、全局接口引用等
  • 可达/不可达对象(Reachable/Unreachable):free模式
    • 从根可以直接或间接到达的对象为可达的,否则为不可达的
    • 从根开始,不断将指向的对象加入活动集,剩下的是垃圾
  • 活动/死亡对象(Live/dead):
    • 在stack和free的结合模式下,对象的引用被视为有向图,可以从根访问的对象为活动对象,否则为死亡对象。

GC的四种算法

  • 引用计数

    • 基本思想:为每个object存储一个计数RC,当有其他 reference指向它时,RC++;当其他reference与其断开时,RC–;如 果RC==0,则回收它。
    • 优点:简单、计算代价分散,“幽灵时间”短 为0
    • 缺点:不全面(容易漏掉循环引用的对象)、并发支 持较弱、占用额外内存空间、等
  • Mark-Sweep(标记-清除)算法

    • 基本思想:为每个object设定状态位(live/dead)并记录,即mark阶段;将标记为dead的对象进行清理,即sweep可阶段。
    • 优点:可以处理循环调用,指针操作无开销,对象不变
    • 缺点:复杂度为O(heap),高 堆的占用比高时影响性能,容易造成碎片,需要找到root
  • Copying(复制)算法

    • 基本思想:为了解决Mark-Sweep算法的缺陷,Copying算法就被提了出来。它将可用内存按容量划分为大小相等的两块,每次只使用其中的一块。当这一块的内存用完了,就将还存活着的对象复制到另外一块上面,然后再把已使用的内存空间一次清理掉,这样一来就不容易出现内存碎片的问题。
    • 优势:运行高效、不易产生内存碎片
    • 缺点:复制花费大量的时间,牺牲内存空间
  • Mark-Compact(标记-整理)算法

    • 基本思想:为了解决Copying算法的缺陷,充分利用内存空间,提出了Mark-Compact算法。该算法标记阶段和Mark-Sweep一样,但是在完成标记之后,它不是直接清理可回收对象,而是将存活对象都向一端移动,然后清理掉端边界以外的内存。

JVM中的GC

Java GC将堆分为不同的区域,各区域采用不同的GC策略,以提高GC的效率

  • Java内存分配和回收的机制概括的说,就是:分代分配,分代回收。

  • 对象将根据存活的时间被分为:年轻代(Young Generation)、年老代(Old Generation)、永久代(Permanent Generation,也就是方法区)

  • 年轻代:

    • 对象被创建时,内存的分配首先发生在年轻代(大对象可以直接 被创建在年老代)
    • 大部分的对象在创建后很快就不再使用,因此很快变得不可达,于是被年轻代的GC机制清理掉(IBM的研究表明,98%的对象都是很快消 亡的)
    • 为减少GC代价,使用copying算法
    • 具体过程
      1. 绝大多数刚创建的对象会被分配在Eden区,其中的大多数对象很快就会消亡。Eden区是连续的内存空间,因此在其上分配内存极快;
      2. 当Eden区满的时候,执行Minor GC,将消亡的对象清理掉,并将剩余的对象复制到一个存活区Survivor0(此时,Survivor1是空白的,两个Survivor总有一个是空白的);
      3. 此后,每次Eden区满了,就执行一次Minor GC,并将剩余的对象都添加到Survivor0;
      4. 当Survivor0也满的时候,将其中仍然活着的对象直接复制到Survivor1,以后Eden区执行Minor GC后,就将剩余的对象添加Survivor1(此时,Survivor0是空白的)。
      5. 当两个存活区切换了几次(HotSpot虚拟机默认15次,用-XX:MaxTenuringThreshold控制,大于该值进入老年代)之后,仍然存活的对象(其实只有一小部分,比如,我们自己定义的对象),将被复制到老年代。
  • 年老代:

    • 对象如果在年轻代存活了足够长的时间而没有被清理掉,则会被复制到年老代,年老代的空间一般比年轻代大,能存放更多的对象,在年老代上发生的GC次数也比年轻代少。
    • 使用Mark-Sweep或Mark-Compact算法;
    • Minor GC和full GC独立进行,减小代价;
    • 当perm generation满了之后,无法存储更多的元数据,也启动full GC。

GVM GC性能调优

  • 尽可能减少GC时间,一般不超过程序执行时间的5%
  • 一旦初始分配给程序的内存满了,就抛出内存溢出异常,
  • 在启动程序时,可为其配置内存分配的具体大小
  • 堆的大小决定着VM将会以何种频度进行GC、每次GC的时间多长。
    • 这两个指标具体取值多少为“优”,需要针对特定应用进行分析。
    • 较大的heap会导致较少发生GC,但每次GC时间很长
    • 如果根据程序需要来设置heap大小,则需要频繁GC,但每次GC的时间较短
  • 设定堆的大小的具体方法
-   `Xmx/-Xms`:指定年轻代和老年代空间的初始值和最大值;`Xms`小于`Xmx`时,年轻代和老年代所消耗的空间量可以根据应用程序的需求增长或收缩;Java堆的增长不会比`Xms`大,也不会比`Xmx`小
-   `XX: NewSize=<n>[g|m|k]`:年轻代空间的初始和最小尺寸,`<n>`是大小,`[g | m | k]`指示大小是否应解释为千兆字节,兆字节或千字节
-   `XX: MaxNewSize=<n>[g|m|k]`:年轻代空间的最大值
-   `Xmn<n>[g|m|k]`:将年轻代的初始值、最小值、最大值设为同一值
  • GC模式选择

    • 增长或收缩年轻代或老年代的空间时需要Full GC
    • Full GC可能会降低吞吐量并导致超出期望的延迟
    • 串行收集器(-XX:+UseSerialGC):使用单个线程执行所有垃圾收集工作
    • 并行收集器(-XX:+UseParallelGC):并行执行Minor GC,显著减少垃圾收集开销
    • 并发低暂停收集器(-XX:+UseConcMarkSweepGC):收集持久代,与执行应用程序同时执行大部分收集,在收集期间会暂停一小段时间
    • 增量低暂停收集器(-XX:+UseTrainGC):收集每个Minor的部分老年代,并尽量减少Major的大停顿
    • -verbose:gc:打印GC信息
  • 堆设置
    -Xms:初始堆大小
    -Xmx:最大堆大小
    -XX:NewSize=n:设置年轻代大小
    -XX:NewRatio=n:设置年轻代和年老代的比值。如:为3,表示年轻代与年老代比值为1:3,年轻代占整个年轻代年老代和的1/4
    -XX:SurvivorRatio=n:年轻代中Eden区与两个Survivor区的比值。注意Survivor区有两个。如:3,表示Eden:Survivor=3:2,一个Survivor区占整个年轻代的1/5
    -XX:MaxPermSize=n:设置持久代大小

  • 收集器设置
    -XX:+UseSerialGC:设置串行收集器
    -XX:+UseParallelGC:设置并行收集器
    -XX:+UseParalledlOldGC:设置并行年老代收集器
    -XX:+UseConcMarkSweepGC:设置并发收集器

  • 垃圾回收统计信息
    -XX:+PrintGC
    -XX:+PrintGCDetails
    -XX:+PrintGCTimeStamps
    -Xloggc:filename

  • 并行收集器设置
    -XX:ParallelGCThreads=n:设置并行收集器收集时使用的CPU数。并行收集线程数。
    -XX:MaxGCPauseMillis=n:设置并行收集最大暂停时间
    -XX:GCTimeRatio=n:设置垃圾回收时间占程序运行时间的百分比。公式为$\frac{1}{1+n}$

  • 并发收集器设置
    -XX:+CMSIncrementalMode:设置为增量模式。适用于单CPU情况。
    -XX:ParallelGCThreads=n:设置并发收集器年轻代收集方式为并行收集时,使用的CPU数。并行收集线程数。

第二节 动态程序分析方法与工具

  • Jstat:获取JVM的Heap使用和GC的性能统计数据,命令如-gcutil
  • Jmap:输出内存中的对象分布情况 如:jmap -clstats
  • Jhat:导出heap dump,浏览/查询其中的对象分布情况
  • jstack:获取Java线程的stack trace 具体用途如下:
    • 定位线程出现长时间停顿的原因,如多线程间死锁、死循环、请求外部资源 导致的长时间等待等。
    • 线程出现停顿的时候通过jstack来查看各个线程的调用堆栈,就可以知道没 有响应的线程到底在后台做什么事情,或者等待什么资源。
  • Visual VM:提供了一个可视化界面,用于查看Java应用程序在JVM上运行时的详细信息,使用各种技术,包括jvmstat,JMX,Serviceability Agent(SA)和Attach API等
  • MAT:内存堆导出文件的分析工具,生成饼状图等,能够对问题发生时刻的系统内存状态获取一个整体印象,找到最有可能导致内存泄露的对象,进一步查看其是否有异常行为。

Memory Dump(堆转储文件)

正如Thread Dump文件记录了当时JVM中线程运行的情况一样,Heap Dump记录了JVM中堆内存运行的情况,可使用jmap或JConsole命令生成,jhat分析。

使用 jmap 命令生成

使用JConsole生成

使用jhat分析

Stack Trace

  可使用jstack查看,定位线程出现长时间停顿的原因。

第三节 代码调优的设计模式和I/O

代码调优

代码调优的概念

  • 代码调优:代码调优不是为了修复bug,而是对正确的代码进行修改以提高其性能,其常常是小规模的变化
    • 调优不会减少代码行数
    • 不要猜原因,而应有明确的优化目标
    • 不要边写程序边调优
    • 不是性能优化的第一选择
    • 代码行数与性能之间无必然的联系
    • 代码调优建立在对程序性能的精确度量基础之上(profiling)
    • 当程序做过某些调整之后,要重新profiling并重新了解需要优化的性能瓶颈,微小的变化能导致优化方向大不相同
  • 性能从不是追求的第一目标,正确性比性能更重要

单例模式(Singleton Pattern)

享元模式(Flyweight Pattern)

原型模式(Prototype Pattern)

对象池模式(Object Pool Pattern)

Java I/O

第七章

第一节 健壮性和正确性的区别

健壮性(Robustness)和正确性(correctness)

健壮性

  • 定义:系统在不 正常输入或不正常外部环境下仍能够表现正常的程度
  • 面向健壮性编程:
    • 处理未期望的行为和错误终止
    • 即使终止执行,也要准确/无歧义的向用户展示全面的错误信息
    • 错误信息有助于进行debug
  • 健壮性原则:
    • Paranoia (偏执狂):总是假定用户恶意、假定自己的代码可能失败
    • 把用户想象成白痴,可能输入任何东西(返回给用户的错误提示信息要详细、准确、无歧义)
    • 对别人宽容点,对自己狠一点(对自己的代码要保守,对用户的行为要开放)
  • 面向健壮性编程的原则:
    • 封闭实现细节,限定用户的恶意行为
    • 考虑极端情况,没有“不可能”

正确性

  • 含义:程序按照spec加以执行的能力,是最重要的质量指标。
  • 对比健壮性和正确性:
    • 正确性:永不给用户错误的结果; 让开发者变得更容易:用户输入错误,直接结束(不满足precondition调用)。
    • 健壮性:尽可能保持软件运行而不是总是退出; 让用户变得更容易:出错也可以容忍,程序内部已有容错机制。
    • 正确性倾向于直接报错(error),健壮性则倾向于容错(fault-tolerance);
    • 对外的接口,倾向于健壮性;对内的实现,倾向于正确性。
    • Reliability(可靠性) = Robustness + correctness
Problem 健壮性 正确性
浏览器发出包含空格的URL 剥离空白,正常处理请求。 将HTTP 400错误请求错误状态返回给客户端。
视频文件有坏帧 跳过腐败区域到下一个可播放部分。 停止播放,引发“损坏的视频文件”错误
配置文件使用了非法字符 在内部识别最常见的评论前缀,忽略它们。 终止启动时出现“配置错误”错误
奇怪格式的日期输入 尝试针对多种不同的日期格式解析字符串。将正确的格式呈现给用户。 日期错误无效

如何测量健壮性和正确性

  • 外部观察角度:
    • Mean time between failures (MTBF,平均失效间隔时间):描述了可修复系统的两次故障之间的预期时间,而平均故障时间(MTTF)表示不可修复系统的预期故障时间。
  • 内部观察角度:
    • 残余缺陷率:每千行代码中遗留的bug的数量

第二节 错误与异常处理

Java中的错误和异常

Throwable

  • Java.lang.throwable
    • Throwable 类是 Java 语言中所有错误或异常的超类。
    • 继承的类:extends Object。
    • 实现的接口:implements Serializable。
    • 直接已知子类:Error, Exception(直接已知子类:IOException、RuntimeException)。

Error

  • Error类描述很少发生的Java运行时系统内部的系统错误和资源耗尽情况(例如,VirtualMachineError,LinkageError)。
  • 对于内部错误:程序员通常无能为力,一旦发生,想办法让程序优雅的结束
  • Error的类型:
    • 用户输入错误
      • 例如:用户要求连接到语法错误的URL,网络层会投诉。
    • 设备错误
      • 硬件并不总是做你想做的。
      • 输出器被关闭
    • 物理限制
      • 磁盘可以填满
      • 可能耗尽了可用内存

异常(Exception)

  • 异常:程序执行中的非正常事件,程序无法再按预想的流程执行。
  • 异常处理:
    • 将错误信息传递给上层调用者,并报告“案发现场”的信息。
    • return之外的第二种退出途径:若找不到异常处理程序,整个系统完全退出

【异常按结构层次的分类】

  • 运行时异常:由程序员处理不当造成,如空指针、数组越界、类型转换
  • 其他异常:程序员无法完全控制的外在问题所导致的,通常为IOE异常,即找不到文件路径等

【异常按处理机制角度的分类】

  • 为什么区分checked 和 unchecked:原因其实很简单,编译器将检查你是否为所有的已检查异常提供了异常处理机制,比如说我们使用Class.forName()来查找给定的字符串的class对象的时候,如果没有为这个方法提供异常处理,编译是无法通过的。

  • Checked exception:

    • 编译器可帮助检查你的程序是否已抛出或处理了可能的异常
    • 异常的向上抛出机制进行处理,如果子类可能产生A异常,那么在父类中也必须throws A异常。可能导致的问题:代码效率低,耦合度过高。
    • checked exception是需要强制catch的异常,你在调用这个方法的时候,你如果不catch这个异常,那么编译器就会报错,比如说我们读写文件的时候会catch IOException,执行数据库操作会有SQLException等。
    • 对checked Exception处理机制    
      • 抛出:声明是throws,抛出时throw   
      • 捕获(try/catch):try出现异常,忽略后面代码直接进入catch;无异常不进入catch;若catch中没有匹配的异常处理,程序退出;若子类重写了父类方法,父类方法没有抛出异常,子类应自己处理全部异常而不再传播;子类从父类继承的方法不能增加或更改异常
      • 处理:不能代替简单的测试,尽量苛刻、不过分细化、将正常处理与异常处理分开、利用好层次结构、早抛出晚捕获、避免不必要的检查
      • 清理现场、释放资源(finally):finally中语句不论有无异常都执行
  • unchecked exception:

    • 程序猿对此不做任何事情,不得不重写你的代码(不需要在编译时使用try-catch等机制处理)
    • 这类异常都是RuntimeException的子类,它们不能通过client code来试图解决
    • 这种异常不是必须需要catch的,你是无法预料的,比如说在调用一个list.size()时,如果listnull,那么就会报NullPointerException,而这个异常就是 RuntimeException,也就是UncheckedException
    • 常见的unchecked exception:JVM抛出,如空指针、数组越界、数据格式、不合法的参数、不合法的状态、找不到类等

checked和unchecked总结

  • 当要决定是采用checked exception还是Unchecked exception的时候,问一个问题: “如果这种异常一旦抛出,client会做怎样的补救?”
    • 如果客户端可以通过其他的方法恢复异常,那么采用checked exception;
    • 如果客户端对出现的这种异常无能为力,那么采用unchecked exception;
    • 异常出现的时候,要做一些试图恢复它的动作而不要仅仅的打印它的信息。
  • 尽量使用unchecked exception来处理编程错误:因为uncheckedexception不用使客户端代码显式的处理它们,它们自己会在出现的地方挂起程序并打印出异常信息。
  • 如果client端对某种异常无能为力,可以把它转变为一个unchecked exception,程序被挂起并返回客户端异常信息

Checked exception应该让客户端从中得到丰富的信息。

要想让代码更加易读,倾向于用unchecked exception来处理程序中的错误

checked异常的处理机制

异常中的LSP原则

  • 如果子类型中override了父类型中的函数,那么子类型中方法抛出的异常不能比父类型抛出的异常类型更广泛
  • 子类型方法可以抛出更具体的异常,也可以不抛出任何异常
  • 如果父类型的方法未抛出异常,那么子类型的方法也不能抛出异常。
  • 其他的参考第五章第二节的LSP

利用throws进行声明

  • 使用throws声明异常:此时需要告知你的client需要处理这些异常,如果client没有handler来处理被抛出的checked exception,程序就终止执行。
  • 程序员必须在方法的spec中明确写清本方法会抛出的所有checked exception,以便于调用该方法的client加以处理
  • 在使用throws时,方法要在定义和spec中明确声明所抛出的全部checked exception,没有抛出checked异常,编译出错,Unchecked异常和Error可以不用处理。

利用throw抛出一个异常

  • 步骤:
    • 找到一个能表达错误的Exception类/或者构造一个新的Exception
    • 构造Exception类的实例,将错误信息写入
    • 抛出它
  • 一旦抛出异常,方法不会再将控制权返回给调用它的client,因此也无需考虑返回错误代码

try-catch语句

  • 使用trycatch关键字可以捕获异常。try/catch代码块放在异常可能发生的地方。
  • try/catch代码块中的代码称为保护代码,
  • catch语句包含要捕获异常类型的声明。当保护代码块中发生一个异常时,try后面的catch块就会被检查。
  • 如果发生的异常包含在catch块中,异常会被传递到该catch块,这和传递一个参数到方法是一样。

finally语句

  • 场景:当异常抛出时,方法中正常执行的代码被终止;但如果异常发生前曾申请过某些资源,那么异常发生后这些资源要被恰当的清理,所以需要用finally语句。
  • finally 关键字用来创建在 try 代码块后面执行的代码块。
  • 无论是否发生异常,finally 代码块中的代码总会被执行。
  • finally 代码块中,可以运行清理类型等收尾善后性质的语句。
  • finally 代码块出现在catch代码块最后:
  • 注意下面事项:
    • catch不能独立于try存在。
    • try/catch后面添加 finally 块并非强制性要求的。
    • try代码后不能既没catch块也没 finally块。
    • try, catch, finally块之间不能添加任何代码。

自定义异常

  • 如果JDK提供的exception类无法充分描述你的程序发生的错误,可以创建自己的异常类。
    • 如果希望写一个检查性异常类,则需要继承Exception类。
    • 如果你想写一个运行时异常类,那么需要继承RuntimeException类。

第三节 断言和防御性编程

断言

什么是断言

  • 作用:允许程序在运行时检查自己,测试有关程序逻辑的假设,如前置条件、后置条件、内部不变量、表示不变量、控制流不变量等
  • 目的: 为了在开发阶段调试程序、尽快避免错误
  • 使用阶段:
    • 断言主要用于开发阶段,避免引入和帮助发现bug
    • 实际运行阶段, 不再使用断言
    • 软件发布阶段,禁用断言避免影响性能。

应用场景

  • 输入参数或输出参数的取值处于预期范围
  • 子程序开始执行(结束)时,文件或流处于打开(关闭)状态
  • 子程序开始执行(结束)时,文件或流的读写位置处于开头(结尾)
  • 文件或流已打开
  • 输入变量的值没有被子程序修改
  • 指针非空
  • 传入子程序的数组至少能容纳X个元素
  • 表已初始化,存储着真实的数据
  • 子程序开始(结束)时,容器空(满)
  • 一个高度优化过的子程序与一个缓慢的子程序,结果一致
  • 断言只在开发阶段被编译到目标代码中,而在生成代码时不编译进去。使用断言的指导建议:
  • 用错误处理代码来处理预期会发生的状况,断言不行
  • 避免把需要执行的代码放入断言中(如果未编译断言呢?)
  • 用断言来注解并验证前条件和后条件
  • 对于高健壮性的代码,应该先用断言,再处理错误

注意

  • 编译时加入-ea(enable assertion)选项运行断言,-da(disable assertion)关闭断言
  • 条件语句或开关没有涵盖所有可能的情况,最好使用断言来阻止非法事件
  • 可以在预计正常情况下程序不会到达的地方放置断言:assert false
  • 断言有代价,需慎用,一般用于验证正确性,处理绝不应该发生的情况
  • 不能作为公共方法的检查,也不能有边界效应

断言和异常的对比

  • 用异常处理技术来处理你“希望发生”的不正常情况
  • 用断言来处理“不希望发生”的情况;断言的方式处理一定是发生了错误
  • 不要把业务逻辑(执行代码)放到断言里面去处理
  • 参数检查通常是方法发布的规范(或契约)的一部分,无论断言是启用还是禁用,都必须遵守这些规范。
    • 如果参数来自于外部(不受自己控制),使用异常处理
    • 如果来自于自己所写的其他代码,可以使用断言来帮助发现错误(例如postcondition就需要)

第四节 调试

什么是bug

  • bug即程序中的错误,导致程序以非预期或未预料到的方式执行。
  • 一个包含大量bug和/或严重干扰其功能的bug的程序被称为buggy。
  • 报告程序中的bug通常被称为bug报告、故障报告、问题报告、故障报告、缺陷报告等

bug产生的原因

  • 代码错误
  • 未完成的要求或不够详细
  • 误解用户需求
  • 设计文档中的逻辑错误
  • 缺乏文件
  • 没有足够的测试

bug的常见类型

  • 数学bug:例如 零除法,算术溢出
  • 逻辑bug:例如 无线循环和无限递归
  • 源头bug:例如 使用了为被定义的变量、资源泄漏,其中有限的系统资源如内存或文件句柄通过重复分配耗尽而不释放。缓冲区溢出,其中程序试图将数据存储在分配存储的末尾。
  • 团队工程bug:例如 评论过时或者评论错误、文件与实际产品的区别

调试的基本过程

  • Debug是测试的后续步骤:测试发现问题,debug消除问题;当防御式编程和测试都无法挡住bug时,我们就必须进行debug了;
  • Debug的目的:寻求错误的根源并消除它;(Debug占用了大量的时间)

调试的过程

  • 常用方法:假设-检验
  • 重现(Reproduce)$\to$诊断(Diagnose/Locating)$\to$修复(Fix)$\to$反思(Reflect)
  • 重现(Reproduce):寻找一个可靠、方便得在线需求问题的方法。
    • 从最小的测试用例开始复现错误(保持复现bug的前提下降低输入规模)
    • 消除因版本、环境、配置等不同引起的差异(通过构建软件实现),确定bug出现的环境(通过程序模拟硬件平台的细节,实现不同的操作系统环境)
    • 利用逆向设计推断导致错误的输入
    • 若无法重现,则无法观察以证明分析和修补的正确性
  • 诊断(Diagnose/Locating):构建假设,并通过执行实验来测试它们,直到您确信已识别错误的根本原因。
    • 从假设开始,构造实验,证明它是对的或者错的
    • 从不符合理论的观察结果开始,修正理论
    • 查看导致错误的测试输入,以及错误的结果,失败的断言以及由此导致的堆栈跟踪
    • 提出一个与所有数据一致的假设,说明错误发生的位置或错误发生的位置,设计实验测试假设
    • 收集实验数据,减少错误可能出现的范围,做出新的假设
    • 设计不同的实验:检查内部状态、修改运行方式、改变本身逻辑
    • 每次只做一个修改、做好记录、不忽略细节、运行不同的测试用例、设置断点、用可实现相同功能并且被证实无问题的组件替代当前组件
  • 修复(Fix):设计和实施解决问题的变化,避免引入回归,并保持或提高软件的整体质量。
    • 确保从干净的源代码树开始
    • 运行现有的测试,并证明它们通过
    • 添加一个或多个新测试,或修复现有测试,以演示错误
    • 修复错误、发现可改进之处
    • 证明你的修复工作正常且没有引入回归(以前通过的测试现在失败)
    • 如果引入回归,通过回顾以前的版本来找出确切的变化
  • 反思(Reflect):思考需求、设计、测试、结构(库、编译器等)

调试的技术和工具

调试技术

  • 暴力调试(Brute Force Attack)
    • 蛮力方法可以分为至少三类:
      • 看内存导出文件
      • 根据“在整个程序中分散打印语句”的常见建议进行调试。
      • 自动化调试工具
  • 递归调试(Induction)
  • 演绎调试(Decution)
  • 回溯调试(Backtracking)
  • 测试调试(Testing)

调试工具

  • 语法和逻辑检查(本课程未涵盖)
  • 源代码比较器(Source-code comparator)
  • 内存堆转储(Memory heap dump)
  • 打印调试/日志记录(Print debugging / logging)
  • 堆栈跟踪(Stack trace)
  • 编译器警告消息(Compiler Warning Messages)
  • 调试器(Debugger)
  • 执行分析器(Execution Profiler)
  • 测试框架(Test Framework)

第五节 测试与测试优先编程

测试和测试优先编程

测试的定义

  • 测试:发现程序中的错误 提高程序正确性的信心
  • 程序正确确认的基本方法:
    • 形式化推理
    • 代码评审
    • 测试
  • 测试是提高软件质量的重要手段
    • 确认是否可达到可用的级别
    • 关注系统某一侧面的质量特性
    • 是否满足需求
    • 是否正确响应所有需求
    • 性能是否可接受
    • 是否可用
    • 可否正确部署安装
    • 是否达到期望

测试的分类

  • 单元测试
  • 集成测试
  • 系统测试
  • 回归测试
  • 验收测试

黑盒测试

  • 白盒测试:对程序内部代码结构的测试 只关注代码内部的问题

  • 黑盒测试:对程序外部表现出来的行为的测试 采用两个方法

    • 等价划分

      将程序可能的输入进行分类 划分为不同集合 包括不合法数据

      • 等价类划分可有两种不同的情况:有效等价类和无效等价类。
      • 若一组对象自反、对称、传递,则为等价类
      • 可产生相似结果的输入集合中的一个可代替整个集合
      • 同理,对输出也可以划分等价类
      • 极端:每个分区只有一个测试用例,覆盖所有分区
    • 边界值分析方法

      边界值分析法是对输入输出的边界值进行测试一种黑盒测试方法,是对等价类分析法的补充。

      • 错误通常隐藏在边界中,如一位偏移、边界值需单独处理等
      • 找到有效数据和无效数据的分界点(最大值、最小值),对该分界点以及两边的值分别单独进行测试。
      • 等价类划分法可以挑选等价类范围内任意一个数据作为代表,而边界值分析法要求每个边界值都要作为测试条件。
  • 测试困难

    • 软件行为在离散输入空间中差异巨大
      • 大多数正确,少数错误
      • bug出现不遵循特定概率分布
    • 无统计规律可循

代码覆盖度

  • 定义:已有的测试用例有多大程度覆盖了被测程序;
  • 代码覆盖度越低,测试越不充分;但要做到很高的代码覆盖度,需要更多的测试用例,测试代价高;
  • 代码覆盖率高的程序在测试期间执行了更多的源代码,与低代码覆盖率的程序相比,包含未检测到的软件错误的可能性较低
  • 基本覆盖标准:函数覆盖;语句覆盖、分支覆盖、条件覆盖、路径覆盖
  • 测试效果:路径 > 分支 > 语句
  • 测试难度:路径 > 分支 > 语句

以注释的形式撰写测试策略

  • “测试策略”通俗来讲就是6个字:“测什么”和“怎么测”。测试策略非常重要,需要在程序中显性记录下来。
  • 目的:在代码评审过程中,其他人能够理解你的测试,并评判测试是否充分
  • 在测试类的顶端写策略
  • 在每个测试方法前说明测试用例是如何选择的

JUnit 测试用例写法

  • JUnit单元测试是依据 注释中@Test之前的方法编写的
  • JUnit测试经常调用多次方法,使用assertEqual || assertTrue || assertFalse来检查结果
  • @Before:准备测试、完成初始化,每个测试方法前执行一次
  • @After:清理现场,每个测试方法后执行一次
  • @Test:表明测试方法,内含assert语句
    • 第一个参数是预期结果、第二个参数实施及结果;
    • 如果断言失败,该测试方法直接返回,JUnit记录该测试的失败;
    • 一个测试方法失败,其他测试方法仍运行
    • @Test(expected = *.class):对错误的测试,expected的属性值是一个异常
    • @Test(timeout = xxx):测试方法在制定的时间之内没有运行完则失败
  • @ignore:忽略测试方法
  • examples
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Calculator {
public int evaluate(String expression) {
int sum = 0;
for (String summand: expression.split("\\+"))
sum += Integer.valueOf(summand);
return sum;
}
}

import static org.junit.Assert.assertEquals;
import org.junit.Test;

public class CalculatorTest {
@Test
public void evaluatesExpression() {
Calculator calculator = new Calculator();
int sum = calculator.evaluate("1+2+3");
assertEquals(6, sum);
}
}

img


0%