C++

回顾cpp-多态-RTTI

RTTI的主要内容

RTTI：运行时类型识别。主要有两个运算符实现：

  • typeid： 返回对象
  • dynamic_cast： 用于将父类的指针或引用安全地转化成子类的指针或引用。

为什么设计RTTI

当处于这种情况时，使用RTTI：当我们想使用基类对象的指针或引用，执行某个派生类的操作，并且该操作不是虚函数时。

一般讲，只要有可能，我们应该尽量使用虚函数。当一个方法被定义成虚函数时，编译器将根据对象的动态类型自动正确地选择正确的方法版本。

但，并不是任何时候都能定义虚函数的。当无法使用虚函数时，就使用RTTI。另一方面，使用RTTI，程序员必须清楚地知道要转换成什么类型，并且检查转换是否成功。

dynamic_cast 使用规则：

  • 只能使用对象指针或对象引用的转换：dynamic_cast<bird*>或dynamci_cast<&bird>，而不能是对象本身。
  • 需要转换的类型中必须包含虚函数，
  • 如果转换成功返回子类地址，否则返回NULL。

typeid 使用规则：

  • type_id 返回一个type_info对象的引用。
  • 如果想通过基类指针获得派生类的数据类型，基类必须带有虚函数。
  • 只能判断当前对象是基类还是子类，无法判断指针是基类还是子类。即typeid()参数是对象，而非指针。

type_info 中的内容：

1
2
3
4
5
6
7
8
9
10
class type_info{
public:
    const char* name() const;
    bool operator==(const typ_info& rhs) const;
    bool operator!=(const typ_info& rhs) const;
    int before(const type_info& rhs) const;
    virtual ~type_info();
private:
    ......
};

用法与实例

假如由两个类都继承了借口类Flyable：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Flyable{
public:
    virtual void takeoff()=0;
    virtual void landing()=0;
};


class Bird : public Flyable{
public:
    // foraging()方法不是虚函数
    void foraging(){cout<<"bird--foraging"<<endl;}
    virtual void takeoff(){cout<<"bird--takeoff"<<endl;}
    virtual void landing(){cout<<"bird--landing"<<endl;}
};


class Plane : public Flyable{
public:
    // carry()方法不是虚函数
    void carry(){cout<<"plane--carray"<<endl;}
    virtual void takeoff(){cout<<"plane--takeoff"<<endl;}
    virtual void landing(){cout<<"plane--landing"<<endl;}
};

Bird由飞行能力，且可以觅食，Plane有飞行能力，且可以运输。

可以定义一个函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void func(Flyable* obj){
    // 1)
    cout<< typeid(*obj).name()<<endl;
    obj->takeoff();

    // 2)
    if(typeid(*obj)== typeid(Bird)){

        // 3)
        Bird* bird = dynamic_cast<Bird*>(obj);
        bird->foraging();
    }
    // 4)
    if(typeid(*obj)== typeid(Plane)){
        Plane* plane = dynamic_cast<Plane*>(obj);
        plane->carray();
    }

    obj->landing();
}

1)打印obj是什么类型。typeid(对象)：参数是obj所指向的对象
2)判断当前obj指针所指向的是什么类型。如果obj指向的对象是Bird类型，
3)将原本是Flyable 类型的obj指针，cast为Bird 类指针。并且将转化后的指针复制给一个新的指针。
4)同3)。

此时在main中调用func()。

1
2
3
Bird b ;
func(&b);
cout<< typeid(b).name()<<endl;     //

b为Bird类。

1
2
3
4
Flyable* plane = new Plane();
func(plane);
cout<< typeid(plane).name()<<endl;     // 
cout<< typeid(*plane).name()<<endl;    //

分别返回Flyable 指针类，和Plane 类。

typeid().name()使用前需要#include <typeinfo>。

敲黑板在可能的情况下，最好定义虚函数，而非直接管理类型。

C++

回顾cpp-多态-接口类

封装->继承->多态

  • 普通虚函数 check
  • 虚析构函数 check
  • 纯虚函数 check
  • 抽象类 check
  • 接口类 check
  • RTTI
  • 异常处理
  • 隐藏 覆盖 check
  • 早绑定 晚绑定 check
  • 虚函数表 check

纯虚函数

类中，一个虚函数没有函数体，直接=0。称为纯虚函数。如下：

1
2
3
4
5
6
class Shape{
public:
    Shape(){}
    virtual double calcAera(){ return 0; }
    virtual double calcPerimeter() = 0;     // 纯虚函数
};

上一篇中提到，一个类中因为有虚函数，所以一定有虚函数表指针，当然也有虚函数表。如果类中虚函数是一个普通的虚函数，这个虚函数的地址存储在虚函数表中。如果是纯虚函数，则在虚函数表中存储0，即该函数没有实现，没有函数体，所以自然就没有地址。

抽象类

纯虚函数一定是某个类的成员函数。包含纯虚函数的类称作抽象类。

  1. 含有一个或多个纯虚函数的类叫做抽象类。

  2. 抽象类是不被允许实例化对象的。

  3. 抽象类的子类也可以是抽象类。

    Person类太抽象，所以设计成抽象类：

    1
    2
    3
    4
    5
    6
    class Person{
    public:
        Person(string name);
        virtual void work()=0;
        virtual void printInfo()=0;
    };

    Worker类作为子类还是抽象，仍然是抽象类：

    1
    2
    3
    4
    5
    6
    7
    8
    class Worker:public Person{
    public:
        Worker(string name);
        virtual void work()=0;
        virtual void printInfo(){ cout<<m_strName; };
    private:
        string m_strName;
    };

  4. 抽象类的子类，只有把抽象类中的所有纯虚函数都做了实现，那么这个子类才可以实例化对象：

    1
    2
    3
    4
    5
    6
    7
    8
    class Dustman:public Worker{
    public:
        Worker(string name);
        virtual void work(){ cout<<"Cleaning"; };
        virtual void printInfo(){ cout<<m_strName; };
    private:
        string m_strName;
    };

一个实例：
Person被设计为一个抽象类，它work可是什么不好说：

1
2
3
4
5
6
7
8
class Person{
public:
    Person(std::string name){ m_strName=name; };
    virtual void work()=0;      // 纯虚函数
    virtual ~Person(){}
private:
    std::string m_strName;
};

Worker类还是抽象，具体做什么呢：

1
2
3
4
5
6
7
8
9
// 还是抽象类
class Worker:public Person{
public:
    Worker(std::string name, int age):Person(name){
        m_iAge=age;
    };
private:
    int m_iAge;
};

Dustman就具体了，做清洁的一类工人：

1
2
3
4
5
class Dustman:public Worker{
public:
    Dustman(std::string name, int age):Worker(name, age){};
    virtual void work(){ std::cout<<"cleaning"<<std::endl; }
};

接口类

只含有纯虚函数的类称为接口类。即这个类中没有任何数据成员，只有成员函数，而这仅有的成员函数又都是纯虚函数。
接口类长这样：

1
2
3
4
5
class Shape{
public:
    virtual double calcAera()=0;
    virtual double calcPerimeter()=0;
};

“只有纯虚函数”真的是只有纯虚函数。

使用时，接口类表达一种能力或协议。接口类要被继承，且所有纯虚函数要被实现。最常使用方式如下例：

两个接口类：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 饮食习惯
class Diet{
public:
    virtual void breakfirst()=0;
    virtual int numMeal()=0;
};

// 训练方式
class Training{
public:
    virtual void method()=0;
    virtual int timeOfTraining()=0;
};

一个普通类：

1
2
3
4
5
6
7
8
9
10
11
12
// ID 即姓名
class ID{
public:
    ID(std::string name){
        m_strName = name;
    }
    void printName(){
        std::cout<<"candidate name is: "<<m_strName<<std::endl;
    }
private:
    std::string m_strName;
};

Fighter是一个更具体的类，分别继承上述两个接口和一个普通类，并且实现所有的纯虚函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Fighter: public ID, public Diet, public Training{
public:
    Fighter(std::string name, int trainTime, int numMeal):ID(name){
        num_meal = numMeal;
        time_training = trainTime;
    }

    // 实现所有接口中的纯虚函数：
    virtual int numMeal(){ return num_meal; }
    virtual int timeOfTraining(){ return time_training; }
    virtual void breakfirst(){ cout<<"breakfirst ture"<<endl; }
    virtual void method(){ cout<<"scientific"<<endl; }
    
private:
    int num_meal;
    int time_training;
};

最近的子类（在本例中也是唯一的子类）Fighter 继承了ID， 表示Fighter 有ID类的姓名。而且继承了Diet， 表示Fighter有各自的饮食习惯。还继承了Training类， 表示Fighter有各自的训练方式。只是Fighter的饮食和训练方式要自己定义。

最终使用的是那个没有被继承的类Fighter：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void match(Fighter* candidate1, Fighter* candidate2){
    if (candidate1->timeOfTraining() > candidate2->timeOfTraining())
        cout<<"candidate1 is more likely going to win"<<endl;
    else
        cout<<"candidate2 is more likely going to win"<<endl;
}

int main() {
    // How to use API
    // 应该实例化“没有被继承的类”
    Fighter f1("Junhui", 5, 3);
    Fighter f2("Uunnui", 6, 4);

    f1.printName();
    f2.printName();

    match(&f1, &f2);

    return 0;
}

该实例是接口类的常用形式。

C++

回顾cpp-多态-虚函数表

封装->继承->多态

  • 普通虚函数 check
  • 虚析构函数 check
  • 纯虚函数
  • 抽象类
  • 接口类
  • RTTI
  • 异常处理
  • 隐藏 覆盖 check
  • 早绑定 晚绑定 check
  • 虚函数表 check

虚函数实现原理

虚函数实现原理是

函数指针：

  • 对象指针—>指针指向对象
  • 函数指针—>指针指向函数

函数存在内存中，可以通过指针指向这段代码的开头，那么函数就会从头一直向下执行。如图：

比如可以通过Func1_ptr 得到fun3()函数入口，并开始执行。函数指针与普通指针一样，存储着内存的地址，这个地址就是函数的首地址。

虚函数实现原理是虚函数表指针。假如有两个类Shape和Circle类：
父类Shape：

1
2
3
4
5
6
7
8
9
class Shape{
public:
    virtual ~Shape(){}   // virtual 析构函数
    virtual double calcArea(){  // 虚函数
        return 0;
    }
protected:
    int m_iEdge;
};

此时，当实例化一个Shape对象时，此Shape对象中包含如下左侧内容：

此Shape对象中，除了m_iEdge外，还有一个成员vftable_ptr，称为虚函数表指针。

  1. 这个指针指向一个虚函数表，此虚函数表与Shape类的定义同时出现。
  2. 此表占空间，从起始位置0xCCFF处开始，也就是vftable_ptr这里存储内容为0xCCFF。
  3. 此表只有一个，通过Shape实例化出的所有对象都指向同一个虚函数表，即所有通过Shape实例化的对象，其vftable_ptr都存储0xCCFF。也就是说每一个实例的vftable_ptr都指向Shape类的虚函数表。言外之意，虚函数表属于类，而非类对象。

在父类Shape的虚函数表中一定定义了一个函数指针：calcArea_ptr，它是calcArea函数入口地址，即calcArea_ptr中存储0x3355（0x3355是Shape类中calcArea函数地址）。调用calcArea时，先通过vftable_ptr 找到虚函数表，再通过位置偏移找到虚函数的入口地址，从而最终找到calcArea计算面积。

上述过程实例化Shape父类对象。
当定义了子类Circle：

1
2
3
4
5
6
7
class Circle : public Shape{   // 共有继承Shape
public:
    Circle(double r);
    // 没有自己的calcArea
private:
    double m_dR;
};

注意Circle中并没有calcArea()函数，也就说，Circle使用Shape类的calcArea计算面积。
当实例化Circle子类对象后。此Circle对象中存储的内容如下：

因为Circle中没有定义虚函数，但它从父类中继承了虚函数calcArea，所以在实例化一个Circle对象时，也会产生一个虚函数表（这个虚拟性是从父类继承过来的）。注意此虚函数表是Circle类自己的虚函数表，起始地址为0x6688，而Shape类的虚函数表起始地址是0xCCFF。但是Circle虚函数表中计算面积的指针calcArea_ptr是一样的，都存储0x3355（因为是继承过来的）。

这就能够保证在Circle中访问父类Shape的calcArea时，也能够通过虚函数表指针找到自己的虚函数表，从而找到父类Shape的calcArea。

如果子类Circle定义中定义了自己的calcArea函数，即子类的calcArea有自己的函数地址0x4B2C：

1
2
3
4
5
6
7
class Circle : public Shape{   // 共有继承Shape
public:
    Circle(double r);
    double calcAera();   // 定义了自己的calcArea，覆盖父类calcArea
private:
    double m_dR;
};

当实例化一个Circle类对象时，Shape类没有任何变化(当然，父类不会因为子类的变化而改变呀！)，但是Circle会有变化：如图：

Circle虚函数表是一样的(即表地址是一样的)，但是因为Circle自己定义了自己的calcArea方法，所以calcArea_ptr所指向的也是Circle自己的calcArea地址0x4B2C，换句话说，原先calcArea_ptr中父类的calcArea地址被Circle自己的calcArea地址覆盖。所以，此时如果使用Shape的指针指向Circle的对象，执行子类的虚函数calcArea。这便是virtual的功能

上述过程就是多态原理。

函数的覆盖与隐藏

  • 覆盖即上述过程：

    当Circle没有自己的calcArea()时，Circle的虚函数表中calcArea_ptr存的是0x3355，即父类calcArea()的地址。

    当Circle有自己的calcArea()时，Circle的虚函数表中calcArea_ptr存的是0x4B2C，即子类自己的calcArea()的地址。
    此时虚函数表中，子类的虚函数地址覆盖父类虚函数地址。

  • 隐藏与多态无关：

    与多态（virtual）无关，即当父类子类中没有virtual虚函数时，也就是说这个类我不希望他有多塔的性质，父类子类出现了同名函数，且父类指针分别指向子类对象，父类同名函数隐藏了子类同名函数。（毕竟这个子类对象类型是父类，回顾继承篇）

敲黑板首先判断需不需要这个父类有多态的性质，如果需要，这个父类中一定要有virtual函数，才会有虚函数表。虚函数表属于类，而非对象。

虚析构函数原理

回顾上一篇笔记，当父类中析构函数都为virtual析构函数时，通过父类指针指向子类对象，最后通过delete 接父类指针就可以，先执行子类析构函数紧接着执行父类析构函数。这个过程与虚函数表有关。

强调一下前提：先执行子类析构函数紧接着执行父类析构函数（也就是说通过父类指针执行到了子类的析构函数，这就是为什么先执行子类析构函数）

在父类Shape中加上虚虚析构函数：

1
2
3
4
5
6
7
8
9
class Shape{
public:
    virtual double calcAera(){  // 虚函数
        return 0;
    }
    virtual ~Shape(){}        // 虚析构函数
protected:
    int m_iEdge;
};

定义子类，写上子类虚析构函数：

1
2
3
4
5
6
7
8
class Circle : public Shape{   // 
public:
    Circle(double r){};
    virtual double calcAera(){};   
    virtual ~Circle(){};         // 子类虚析构函数
private:
    double m_dR;
};

此时用父类指针指向子类对象，且delete接父类指针：

1
2
3
4
5
6
7
int mian(){
    Shape* shape = new Circle(1.0);

    delete shape;
    shape = NULL;
    return 0;
}

虚函数表如何工作：

当在Shape中定义了虚析构函数，Shape类的虚函数表中就会有一个Shape类的虚函数指针～Shape_ptr（指向父类析构函数），

同时在Circle类中也会产生一个子类析构函数的函数指针～Circle_ptr（指向子类析构函数）。注意上述两个析构函数指针同时出现。

如果使用Shape的指针指向Circle的对象，执行子类的虚函数calcArea。当delete接Shape指针时，通过Shape找到Circle类的vftable_ptr（Shape类指针指向Circle类对象），进而找到虚函数表，最后找到Circle类的析构函数，从而使得Circle类析构函数得意执行。最后执行Shape类析构函数。

{有疑惑，父类指针指向子类对象，会执行子类虚函数？（delete父类的指针时，程序会去找父类的指针指向的地址，该地址就是子类头部虚函数表指针的地址，进而找到子类虚函数表，最后执行子类析构函数） delete时，发生了什么？回顾继承篇}

现实中的虚函数

明确概念：

  1. 对象的大小：实例化对象中数据成员所占内存大小，（不包括成员函数）。
  2. 对象的地址：通过类实例化一个对象，这个对象的所占的内存单元的首地址。
  3. 对象成员的地址：一个对象中每一个成员所占据的地址。因为每个成员的数据类型不同，所以占用不同大小的内存。
  4. 虚函数表指针：当实例化一个对象后，这个对象的第一个内存中所存储的指针，这个指针就是虚函数表的指针。就是上述所有的vftable_ptr。可以根据这个特点，通过计算对象的大小来证明虚函数表示的存在。

当没有virtual时

假如有两个类：

父类Shape：

1
2
3
4
5
6
7
8
class Shape{   
public:
    Shape(){}
    ~Shape(){}
    double calcArea(){ 
        std::cout<<"Shape->calc area"<<std::endl;
    }
};

子类Circle：

1
2
3
4
5
6
7
class Circle : public Shape{
public:
    Circle(int r){ m_iR = r; }
    ~Circle(){}
private:
    int m_iR;   
};

执行1：

1
2
3
4
Shape shape;                  // 实例化一个对象
cout<<sizeof(shape)<<endl;    // 该对象的大小
int* p = (int*)&shape;        // 该对象的地址
cout<<p<<endl;                // 对象起始地址

结果1：

1
2
1                 // 对于一个数据成员都没有的类对象，c++ 用一个内存单元来标记它。 
0x7fff478ce38f    // 对象起始地址

执行2：

1
2
3
4
5
Circle circle(100);
cout<<sizeof(circle)<<endl;
int* q= (int*)&circle;
cout<<q<<endl;         // 指针q中内容
cout<<(unsigned int)(*q)<<endl;  // 指针q中内容的内容

结果2：

1
2
3
4                  // int 型数据占4个内存单元
0x7ffdca8b3e20    // 对象起始地址
100               // 起始地址中的内容

当有virtual时

父类与子类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Shape{
public:
    Shape(){}
    virtual ~Shape(){}
    virtual double calcArea(){ } // 虚函数
};

class Circle : public Shape{
public:
    Circle(int r){ m_iR = r; }
    virtual ~Circle(){}
private:
    int m_iR;
};

执行：

1
2
3
4
5
6
7
8
9
10
11
Shape shape;
cout<<sizeof(shape)<<endl;
int* p = (int*)&shape;
cout<<(unsigned int)(*p)<<endl;   

Circle circle(100);
int* q= (int*)&circle;
cout<<(unsigned int)(*q)<<endl;
q++;   
q++;
cout<<(unsigned int)(*q)<<endl;

返回：

1
2
3
4
8              
4198160
4198120
100

shape对象大小是8，Shape类对象地址中第一个内容是虚函数表地址4198160；
Circle类对象地址中的第一个内容是虚函数表地址4198120，之后移动指针2次，便是存储数据成员100的位置。

C++

回顾cpp-多态-虚函数

封装->继承->多态

  • 普通虚函数
  • 虚析构函数 check
  • 纯虚函数
  • 抽象类
  • 接口类
  • RTTI
  • 异常处理
  • 隐藏 覆盖
  • 早绑定 晚绑定 check
  • 虚函数表

静态多态（早绑定）

函数重构

1
2
3
4
5
6
7
8
9
10
11
12
class Rect{
public:
    int calcArea(int width);
    int calcAera(int width, int height);
};

int main(){
    Rect rect;
    rect.calcAera(10);
    rect.calcAera(10, 20);
    return 0;
}

程序在运行之前，在编译阶段就已经确定下来要使用哪个calsAera()函数了。很早地就将函数编译进去了。此情况叫做早绑定，即静态多态。

动态多态（晚绑定）

不同的对象下达相同的指令，做着不同的操作，为动态多态。有前提的：它必须以封装，继承为基础。

也就是说，有了封装继承之后，才能谈动态多态。动态多态至少由两个类，父子类，三个类时动态多态才表现的更加明显。

注意只有当一个类需要有多态的的性质时，才体现多态。此时的base classes需要将其析构函数声明为virtual。当没有声明virtual时，看下例：

父类：

1
2
3
4
5
6
7
8
9
10
11
class Shape{
public:
    Shape(){}
    ~Shape(){
        std::cout<<"~Shape()"<<std::endl;
    }
    double calcArea(){                  // 不是虚函数
        std::cout<<"Shape->calc area"<<std::endl;
        return 0;
    }
};

子类Circle：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Circle : public Shape{
public:
    Circle(double r){
        m_dR = r;
    }
    ~Circle(){
        std::cout<<"~Circle()"<<std::endl;
    }
    double calcArea(){                 // 不是虚函数
        return 3.14*m_dR*m_dR;
    }
private:
    double m_dR;
};

子类Rect：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Rect : public Shape{
public:
    Rect(double width, double height){
        m_dWidth = width;
        m_dHeight = height;
    }
    ~Rect(){
        std::cout<<"~Rect()"<<std::endl;
    }
    double calcAera(){                  // 不是虚函数
        return m_dHeight*m_dWidth;
    }
private:
    double m_dWidth;
    double m_dHeight;
};

含有多态性质的base class的设计目的是为了通过base class的接口来使用derived class，所以，如果用两个base class指针分别指向两个不同derived class，后分别调用两个derived class的计算面积方法：

1
2
3
4
5
6
7
8
9
10
Shape *shape1 = new Circle(1.0);     // 父类指针指向子类对象
Shape *shape2 = new Rect(3.0, 5.0);  // 父类指针指向子类对象

cout<<shape1->calcArea()<<endl;    
cout<<shape2->calcArea()<<endl;

delete shape1;
shape1 = NULL;
delete shape2;
shape2 = NULL;

结果并不是我们想要的：

1
2
3
4
5
6
Shape->calc area    //  调用父类方法
0
Shape->calc area    // 调用父类方法
0
~Shape()     // 调用父类析构函数
~Shape()     // 调用父类析构函数

都调用了父类的calcArea()方法。且都调用了父类的析构函数。此现象称为隐藏.

WHY：我们不希望这样，我们希望通过父类指针可以调用子类的方法。如何解决？使用virtual 关键字。

解决方法：在父类中想要实现多态的函数前加virtual，同时在子类的相同函数前也加上virtual：

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
class Shape{
public:
    ...
    virtual double calcArea(){         // 虚函数
        std::cout<<"calc area..."<<std::endl;
    }
    ...
};

class Circle : public Shape{
public:
    ...
    double calcArea(){         //  虚函数
        return 3.14*m_dR*m_dR;
    }
    ...
};

class Rect : public Shape{
public:
    ...
    double calcArea(){       // 虚函数
        return m_dHeight*m_dWidth;
    }
    ...
};

此时的结果：

1
2
3
4
3.14     // 调用Circle 的方法
15       // 调用Rect 的方法
~Shape()    // 只调用父类析构函数
~Shape()

只有base class的同名函数被声明为virtual。

很自然的情况是：当使用derived class指针指向derived class对象时，不管是不是virtual，都会由正确执行结果：

1
2
3
4
5
6
7
8
...
Circle *circle1 = new Circle(1.0);
Rect *rect1 = new Rect(3.0, 5.0);

delete circle1;
circle1 = NULL;
delete rect1;
rect1 = NULL;

输出：

1
2
3
4
5
6
3.14
15
~Circle()    // 既调用子类析构函数
~Shape()     // 又调用父类析构函数
~Rect()
~Shape()

敲黑板

  • 父类子类要实现多态的方法前，父类要声明为virtual。
  • 当父类的析构函数不是虚函数时，类指针指向子类对象时，只调用父类析构函数。
  • 当父类的析构函数不是虚函数时，delete 后跟父类指针，只执行父类析构函数，如果delete 后跟子类指针，执行父类和子类析构函数。
  • 只将要作为父类的类的析构函数声明为virtual。

虚析构函数

为啥要有虚析构函数？如果要将这个class作为基类而且是有多态性质的基类，应该把其析构函数定义成virtual！看以下例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Circle : public Shape{
public:
    Circle(double r, int x, int y){
        m_pCenter = new Coordinate(x, y)   // 2.实例化一个坐标对象
        m_dR = r;
    }
    ~Circle(){
        delete m_pCenter;                 // 3.释放坐标对象
        m_pCenter = NULL;
    }
    double calcArea(){
        return 3.14*m_dR*m_dR;
    }
private:
    double m_dR;
    Coordinate* m_pCenter;      // 1.多一个坐标类属性
};

在析构函数中释放了坐标对象，不会内存泄露。可是！
在多态时：

1
2
3
4
5
Shape *shape1 = new Circle(1.0);    
cout<<shape1->calcArea()<<endl;    

delete shape1;      // 使用父类指针销毁子类对象
shape1 = NULL;

使用父类指针销毁子类对象时，只调用了父类析构函数~Shape()，而子类~Circle()未被调用。坐标对象不会被释放，此时内存泄漏。这就不合理了，虚构函数设计就是要被执行的

如何解决？
虚析构函数！在父类的析构函数前加virtual：

1
2
3
4
5
6
7
8
virtual ~Shape(){            // 虚析构
    ...
}

~Circle(){           
    delete m_pCenter;                 // 释放坐标对象
    m_pCenter = NULL;
}

此时，使用父类指针销毁子类对象时，既调用了父类析构函数~Shape()，又调用子类~Circle()。父类子类的析构函数都被执行。情理上就对了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Shape{
public:
    virtual ~Shape(){   //  虚
        std::cout<<"~Shape()"<<std::endl;
    }
};

class Circle : public Shape{
public:
    ~Circle(){ 
        std::cout<<"~Circle()"<<std::endl;
    }
};

class Rect : public Shape{
public:     
    ~Rect(){
        std::cout<<"~Rect()"<<std::endl;
    }
};

父类子类的析构函数都被执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    Shape *shape1 = new Circle(1.0);
    Shape *shape2 = new Rect(3.0, 5.0);

    delete shape1;
    shape1 = NULL;
    delete shape2;
    shape2 = NULL;

OUTPUT：
3.14
15
~Circle()
~Shape()
~Rect()
~Shape()

执行完子类虚析构函数，再执行父类虚析构函数。

virtual使用限制

  • 普通函数不能是虚函数

  • 不能修饰静态成员函数

    1
    2
    3
    4
    class Animal{
    public:
        virtual static int func(); 
    }；

  • 不能修饰inline函数，如果这么做了，计算机会忽略inline关键字，使之成为虚函数。

  • 不能修饰构造函数。

敲黑板
任何时候都应该为含有多态性质的基类（父类）声明virtual析构函数。如果一个class含有任何virual函数，就一定要有一个virtual析构函数。

LeetCode

LeetCode-方法论-数组相关-一

与数组相关的问题是最常出现的问题。
这篇笔记记录问题编号：
283, 167, 209, 75, 11, 125, 3

敲黑板
常用技术：

  • 计数排序，当元素种类较小时使用
  • 对撞指针，当数据元素有序时使用
  • 滑动串口，注意此窗口大小不一定固定
  • 图示简化实现，有些情况下，画好了中间过程的图示，实现起来就像看图说话
  • 循环不变量，保证程序正确性，并且使图示简化实现成为可能
  • 更新记录，更新循环中的每一步结果
  • 跳过，
  • 频数记录，技巧 记录频数
  • 大条件先满足，在if语句中，大小条件一定要在小条件之前

实现时的注意：

  • 对边界的正确处理，明确循环不变量的定义且需要始终维护。
  • 使用小数据集调试，先保证算法的正确性。
  • 应尽量减少代码量，合并可以合并的，删掉无用的。经验上讲，同一个算法，代码量越多越容易出错。
  • 先由算法过程，后实现，不要上来就实现。

#283 Move Zeros

  • 描述：给出一个序列，将所有0元素移动到序列尾部，并且其他元素相对位置不变。

    1
    2
    Input: [0,1,0,3,12]
    Output: [1,3,12,0,0]

  • 思路一：

    如图，整个过程保持[0,..,k)中元素非零。遍历结束后，将k及其以后的元素值设为0。就得到最后值。

    时间复杂度：O(N)
    空间复杂度：O(1)

  • 思路二：

    将思路一中，当nums[i]!=0时，的执行改为 swap(nums[i], nums[k++])。如此不需要思路一的最后一步。

    时间复杂度：O(N)
    空间复杂度：O(1)

  • 实现见这里，的对应文件。

关键：协调两指针

#167 Two Sum II 对撞指针

  • 问题描述：

    1
    2
    Input: numbers = [2,7,11,15], target = 9
    Output: [1,2]

    当数组有序时使用对撞指针。
    number[0+1] + number[1+1] = target.

  • 思路：

    一个指针`i`从左端向右，另一个指针`j`从右端向左。
如果`number[i] + mumber[j] = target` 时，返回对应的`i+1, j+1`。
如果`number[i] + number[j] < target`, 说明`number[i]`小，所以`i++`；
如果`number[i] + number[j] > taregt`, 说明`number[j]`大，所以`j--`；

  • 实现见这里，的对应文件。

  • 同类问题：
    345

#209 Minimum Size Subarray Sum 滑动窗口

  • 问题描述：

    1
    2
    3
    Input: s = 7, nums = [2,3,1,2,4,3]
    Output: 2
    Explanation: the subarray [4,3] has the minimal length under the problem constraint.

  • 思路

    设置窗口左右端，并且初始化：

    1
    2
    3
    int  l=0, r=-1  //始终保证nums[l,...,r]为滑动窗口，初始化为空
    int sum = 0;
    int res = nums.size()-1  // 结果设置为可能的最大值

    然后窗口向右移动，移动过程中要判断两次：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while(l < nums.size()){
        // 第一次判断
        if (r+1 < nums.size() && sum < s)
            sum += nums[++r];
        else
            sum -= nums[l++];

        // 第二次判断
        if (sum>s)
            res = min(res, r-l+1);  // 更新结果
    }

    循环中:

    第一次判断:
    如果r没有到头，且sum小于s：则r右移，sum加上此时的nums[r]。
    如果r到最右边，或sum大于等于s：则Sum减去nums[l]，且l右移。
第二次判断:
    如果sum大于等于s，
    结果res取这次res和上次res的最小值。

最后一步，判断，如果res扔等于初始值，即没有发生变化，则表示sum中所有元素和都小于s。返回0.

    第一次判断的两种情况：

关键：图示简化实现，循环不变量，更新记录，滑动窗口，大条件先满足

#75 Sort Colors 三路快排

  • 问题描述：

    1
    一个数组由n个元素，元素只有0,1,2三种数值，为这个数组排序

  • 思路

    1. 思路一： 计数排序

      先统计每个数值出现过多少次，之后从小到大将对应的值放入元素组，放入多少个呢，放入对应数值出现的次数个。实现：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      void sortColor(vector<int>& nums){
          int count[3] = {0,0,0};   
          if (nums.size() == 0)
              return;

          // 记录每个数值出现的频数
          for (int i=0; i<nums.size(); i++){
              count[nums[i]]++;
          }

          // 挨个儿放入元素组
          int index = 0;
          for (int i=0; i<count[0]; i++)
              nums[index++] = 0;
          for (int i=0; i<count[1]; i++)
              nums[index++] = 1;
          for (int i=0;i<count[2]; i++)
              nums[index++] = 2;
      }

      很容易理解。

    2. 思路二： 三路快排

      初始化函数操作，

      1
      2
      3
      void sortColors(vector<int>& nums){
          int zero = -1;         // 定义[0,...,zero] 的元素为0
          int two = nums.size();   // 定义[two,...,n-1] 的元素为 3

      明确循环不变量的定义 zero：数组中元素为0的最后一个index，two：数组中元素为2的第一个index。

      之后执行如下图的操作：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
          for (int i=0; i<two; ){
              if(nums[i] == 1)
                  i++;
              else if(nums[i] == 2)
                  swap(nums[--two], nums[i] );
              else {
                  assert( nums[i] == 0 );
                  swap(nums[++zero], nums[i++]);
              }
          }
      }

关键：图示简化实现，循环不变量

#11 Container With Most Water 对撞指针

  • 问题描述：

    1
    2
    3
    4
    The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49. 

    Input: [1,8,6,2,5,4,8,3,7]
    Output: 49

  • 思路(无序数组求最值)：

    两指针分别从数组首位处开始，两个指针向中间移动，两指针的距离为宽，两指针对应的数值的较小值为高度，要最大化宽度x高度。注意两指针相互靠近，所以宽度是单调减小的，所以，要想记录最大值，就要跳过高度减小的值，即i++和j++。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int maxArea(vector<int>& height){
        // 初始化时，宽度是最大的
        int maxWater = 0;
        int i=0;
        int j=height.size()-1;

        // 开始对撞
        while(i<j){
            int h = min(height[i], height[j]);
            maxWater = max(maxWater, h*(j-i));  // 每次循环，更新最大值
            while(height[i]<=h && i<j) i++;   // h减小了，所以跳过
            while(height[j]<=h && i<j) j--;   // 跳过
        }
        return maxWater;
    }

    关键：两指针对撞，跳过，更新记录

#125 PalineDrome 判断是否是回文

  • 问题描述：

    1
    2
    3
    Input: "A man, a plan, a canal: Panama"
    Output: true
    Note: For the purpose of this problem, we define empty string as valid palindrome.

  • 实现：

    1
    2
    3
    4
    5
    6
    7
    8
    bool isPalindrome(string s) {
        for(int l = 0,r=s.length()-1;l<r; l++,r-- ){
            while(isalnum(s[l])==false && l<r) l++;  //跳过 non alnum
            while(isalnum(s[r])==false && l<r) r--;  //跳过 non alnum
            if(tolower(s[l]) != tolower(s[r])) return false;
        }
        return true;
    }

关键：两指针对撞，跳过，常用字符串函数

#3 Longest Substring Without Repeating Charactors 最长无重复子串

  • 描述

    1
    2
    3
    4
    Input: "pwwkew"
    Output: 3
    Explanation: The answer is "wke", with the length of 3. 
                Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

  • 思路见图示：

  • 看图说话：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int lengthOfLongestSubstring(string s) {
        int freq[256] = {0};   // 记录频数

        int l = 0;    // 滑动窗口保证s[l,...,r]始终无重复字符，初始化为空 
        int r = -1;
        int res = 0;  

        while (l < s.size()){

            if (r+1<s.size() && freq[s[r+1]] == 0){
                r++;
                freq[s[r]] ++;
            }
            else {   // r is out of bound || freq[r+1] == 1
                freq[s[l]] --;
                l++;
            }

            res = max(res, r-l+1);   // 更新结果
        }
        return res;
    }

关键：图示简化实现，循环不变量，更新记录，记录频数，滑动窗口，大条件先满足

敲黑板想要思维升级，就需要见足够多的问题类型，每种类型见过并解决不止一遍。只见过一遍就像完全掌握，是不实际的。见得多了，自然大脑就接受了，思维就升级了。另外一点，“回头看”会把之前不明白或者不能接受的问题“回锅”，可以增强大脑对这个问题的接纳程度。

LeetCode

LeetCode-方法论-回溯法

46, 77, 40, 515,

  • 回溯法解决一类问题，排列与组合。
  • 属于树型问题，所以通常需要画递归树。
  • 通常需要有个容器来保存状态。
  • 实现方法：理解问题，画递归树。
  • 递归实现，需要“跳进跳出”的思维
  • 分清楚操作部分和结点移动部分
  • 一个模式：移动控制+结点操作 对上一条的强调

#46

  • 描述

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    给出一组不重复的整数，返回所有排列。如：
    Input: [1,2,3]
    Output:
    [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
    ]

  • 逻辑

    每一种排列包含3个元素，思路很直接：构建一棵树，树的结点表示形成的一个组合，叶节点表示一个完整的组合。过程中需要一个容器来记录每一个叶节点，即一个排列。还需要一个布尔型容器来记录已经处理过的元素。最后还需要一个容器记录所有找到的排列，即最终返回的结果。过程可以用一棵树的先序遍历完成：

    图中橘红色箭头表示程序执行过程。体会递归“跳进跳出”的执行方式，每到“触底反弹”，便体现了回溯的“回”，所有变量值均回到上一层。递归算法很”整齐”，所有结点执行相同的操作。

  • 实现

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    // res 记录所有排列，最终返回res
    vector<vector<int>> res;
    // used 记录检查过的元素
    vector<bool> used;

    // 这个函数找到一个排列, num是输入，index表示当前考察元素的Index，p表示逐渐形成的一个排列
    // 向这个排列的末尾添加第index个元素，获得一个有Index个元素的排列。
    void getPermutaion(const vector<int>& nums, int index, vector<int>& p){

        // 递归到底的情况，所有元素都考察过之后。
        if (index == nums.size()){
            res.push_back(p);
            return;
        }

        // 以每一个元素作为这棵树的根：
        for (int i=0; i<nums.size(); i++){
            // 只有当元素没有考察过，才执行以下
            if (used[i] == false){
                used[i] = true;        //
                p.push_back(nums[i]);   // 把这个元素放入p中
                getPermutaion(nums, index+1, p);   // 形成这棵树的子树
                p.pop_back();    // 这里体现了回溯的“回”，回到上一步
                used[i]=false;   // 回到上一步
            }
        }
        return ;
    }

    // 入口函数
    vector<vector<int>> permute(vector<int>& nums) {
        used = vector<bool>(nums.size(), false);
        vector<int> p;
        getPermutaion(nums, 0, p);
        return res;
    }

    敲黑板

  1. 思维：跳进跳出
  2. 实现：跳进跳“回”
  3. 明确(写出)结点函数的定义，并且保持整个过程定义不变。

组合问题

#77

  • 描述：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    从n个数中取k个数，一共有哪些组合：
    Input: n = 4, k = 2
    Output:
    [
    [2,4],
    [3,4],
    [2,3],
    [1,2],
    [1,3],
    [1,4],
    ]

  • 逻辑

    分析问题：
    开始，根节点中不存在任何值，它的子节点从1开始遍历，形成组合中的第一个值[1], [2], [3], [4]。
    当结点第一个值为1时，它的子节点从2开始向后遍历。形成的组合有[1,2], [1,3], [1,4]。
    当结点第一个值为2时，其子节点从3开始遍历。得到组合[2,3], [2,4]。
    当结点第一个值为3时，其子节点从4开始遍历。得到组合[3,4]。
    当结点第一个值为4时，4超过了索引0~3，返回到根节点。

    给出递归树：

  • 实现

    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
    28
    29
    // res保存所有的组合
    vector<vector<int>> res;

    // 定义：从n个数中取k个数，把当前的数值放入c中，从Index开始向后查找：
    void generatCombination(int n, int k, int index, vector<int>& c){
        // 当c的大小为2时，表示找到一个组合
        if (c.size()==k){
            res.push_back(c);
            return;
        }

        // 
        for (int i=index; i<n; i++){
            c.push_back(i);
            // 以当前结点为根，从index+1开始向后找：
            generatCombination(n, k, index+1, c);
            c.pop_back();   // 回溯的“回”，跳回上一层。
        }
        return;
    }

    vector<vector<int>> combination(int n, int k){
        if (n<k || n<=0||k<=0 )
            return res;
        vector<int> c;
        // 从根节点开始，
        generatCombination(n, k, 1, c);
        return res;
    }

    这个问题的实现中，在递归函数里的for循环，循环变量i与index有关，表示从Index后查找，这保证了，组合中元素无重复，且组合无重复。这也是与上一个问题不同之处。可以回过去看排列问题，其递归函数中for循环i与Index无关，表示，i每次从0开始查找，使得每个排列中元素不必只是递增，就是说像[3,2,1]，也是一个排列。

敲黑板体会递归函数中for循环循环变量与index有关，无关的不同。

#40. Combination Sum II

  • 描述

    1
    2
    3
    4
    5
    6
    Input: candidates = [2,5,2,1,2], target = 5,
    A solution set is:
    [
    [1,2,2],
    [5]
    ]

  • 思路

    感觉上，需要回溯，所以先画出递归树：

    假设candidate=[1,2,3,4,5], target=5。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target){
        set<vector<int>> res;
        vector<int> tmp;   // res中的每个元素
        sort(candidates.begin(), candidates.end());
        DFS(candidates, target, res, tmp ,0);
        return {res.begin(), res.end()};

    }

    // 每一个结点的操作
    void DFS(vector<int>& candidates, int target, set<vector<int>>& res, vector<int>& tmp, int index){
        if (target==0){   // 如果最后剩下为0，则表示找到一个sum为target
            res.insert(tmp);
            return;
        }

        for (int i=index; i<candidates.size(); i++){
            if (candidates[i]<=target){
                tmp.push_back(candidates[i]);
                DFS(candidates, target-candidates[i], res, tmp, i+1);
                tmp.pop_back();
            }else break;
        }
    }

    敲黑板一定要先画递归树，后写code，试图从别人的code中画递归树，是很容易懵掉的。

#515 Find Largest Value in Each Tree Row

  • 描述

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    You need to find the largest value in each row of a binary tree.
    Example:

    Input: 

            1
            / \
            3   2
        / \   \
        5   3   9 

    Output: [1, 3, 9]

  • 逻辑

    先画二叉树，见下图。

    本质是二叉树的遍历，先序遍历，顺序为下图中粉色箭头。而对于每个结点的操作是下图中橙色箭头。每个操作改变的是res数组，根据res的长度与row的索引决定。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    vector<int> largestValues(TreeNode* root){
        vector<int> res;
        DFS(root, 0, res);
        return res;
    }

    void DFS(TreeNode* root, int row, vector<int>& res){
        // operation ORANGE
        if (!root) return;

        if (row >= res.size())
            res.push_back(root->val);
        else
            res[row] = max(res[row], root->val);

        // move PINK
        DFS(root->left, row+1, res);
        DFS(root->right, row+1, res);
        return;
    }

关键： 变量row的跳进跳出,分清楚操作部分和结点移动部分

#17 Letter Combinations of a phone number

#491 All increasing Sub-sequences

Machine Learning

线性模型-(一)-最小二乘

  • 线性模型形式简单，具有很好的可解释性。虽然简单却蕴藏着重要的机器学习的基本思想。一般实践中，都会先使用线性回归方法尝试。
  • 把分类问题的样本点放在在坐标轴上，坐标轴每一个轴代表一个特征。而回归问题的样本点放到坐标轴上，x轴是连续的，可以是其中一个特征的连续值，其他轴代表不同的特征。
  • 线性回归的目标是度量出模型没有拟合住样本点的部分，此时的目标函数称为 loss fucntion。
  • 而有的算法中度量的是拟合的程度，此时成目标函数为效用函数 utility function 。
  • 通过分析问题，确定问题的目标函数，通过最优化目标(最小化loss 或最大化utility)，获得机器学习模型。
  • 为参数学习，找到一组参数，这组参数可以最小化loss 或最大化utility。涉及到最优化原理或凸优化理论，如常见的牛顿法，梯度下降，模拟退火等算法。许多计算机问题如最短路径，背包问题都属于最优化问题。
  • 对于(一元或多元)线性回归，直接用最小二乘法求解。
  • 使用线性模型的前提，是假设数据与目标间由线性关系。

最小二乘法解一元线性回归

基于最小化均方误差来进行模型求解的方法为最小二乘法，即试图找一条直线，使得所有样本点到该直线的欧氏距离之和最小。具体的结果是经过数学推导，而非迭代参数学习。

数据为一维向量：

1
2
3
# 小写X表示这是一个向量
x = np.array([1,2,3,4,5,6,7,8,9,10,])
y = np.array([3,4,6,5,5,6,8,10,9,11,])

根据最小二乘法结果公式的得：

1
2
3
4
5
6
7
8
9
10
11
12
# 最小二乘法
x_bar = np.mean(x)
y_bar = np.mean(y)

fenzi = 0.0
fenmu = 0.0
for i, j in zip(x, y):
    fenzi += (i - x_bar) * (j - y_bar)
    fenmu += (i - x_bar)**2

a = fenzi / fenmu
b = y_bar - a * x_bar

绘制拟合直线：

1
2
3
4
5
6
7
# 绘制直线
y_hat = a*x + b

plt.scatter(x, y)
plt.plot(x, y_hat, color='r')
plt.axis([0, 12, 0, 12])
plt.show()

结果：

使用模型，分别预测单个值，预测一组值：

1
2
3
4
5
6
7
# 预测单个值
def predict(x):
    return a * x + b

# 预测多个值
def predict_X(X):
    return np.asarray([a * x + b for x in X])

上述计算过程是遍历每一个x和y，部分相乘后相加，这样计算的效率并不高。另一种方式是使用矩阵的乘法，即内积(Dot Product 点乘)

向量化

使用矩阵的内积，便可以用python中的向量相乘法则快速计算：

1
2
3
4
5
x_mean = np.mean(x_train)
y_mean = np.mean(y_train)

a = (x_train - x_mean).dot(y_train - y_mean) / (x_train - x_mean).dot(x_train - x_mean)
b = y_mean - a * x_mean

用内积代替了循环遍历，计算性能上会有很大提升。对于1亿的数据量，两者使用时间：

循环遍历： 55.904422
内积：    2.4315210000000036

很多时候，算法原理的数学推导，最终要能变化成向量内积的形式，很重要。

评价现行模型的性能

评价线性模型主要用MSE, RMSE, MAE:

1
2
3
4
5
6
7
8
# 公式：
mse = np.sum((y_predict - y_test)**2 / len(y_test))
rmse = math.sqrt(mse)
mae = np.sum(np.absolute(y_predict - y_test)) / len(y_test)

# sklearn：
from sklearn.metrics import mean_squared_error
from sklearn.metrics import mean_absolute_error

相对来说，RMSE比MAE好，最小化RMSE，它表示错误样本中最大的错误值相应的比较小。而在线性回归中最好的指标要数R Squared。

R Squared

这个是线性回归最常用的性能指标。其定义为：

1
2
3
r_squared = 1 - (y_predict - y_test).dot(y_predict - y_test)
               /
               (y_means - y_test).dot(y_means - y_test)

其中分子可以表示，使用我们的模型预测产生的错误。
而分母表示使用baseline 模型y=y_means 预测产生的错误。

分母的预测是不论x是多少，我都把他预测成y_means，错误率自然多。而分子是我们训练模型的实际预测，即我的模型实际拟合住样本的地方。

所以

  • r_squared 是我的模型与baseline的比较。
  • 两者相除小于等于1，
  • r_squared 越大，表示我们的模型越好
  • 当r_squared = 1，表示，我的模型没有犯任何错。
  • 当r_squared = 0，表示，我的模型性能等同于baseline。
  • 当r_squared < 0，表示，我的模型不如baseline，很可能，原数据不存在现线性关系。

当r_squared 定义中分子分母同时除以测试样本个数，r_squared还可以写成：

1
r_squared = 1 - mse(y_predict, y_test)/var(y_test)

其中var(y_test)，表示y_test 数据方差。所以r_squared 是由统计意义的。

在sklearn中使用

1
2
3
from sklearn.metrics import r2_score

r2_score(y_predict, y_test)

在sklearn中的LinearRegression模型里的 score成员方法返回的就是r_squared：

1
2
3
4
# MODEL 表示任何模型的实例
def score(x_test, y_test):
    y_predict = MODEL.predict(x_test)
    return r2_score(y_test, y_predict)

多元线性回归与Normal Equation

依旧可以使用最小二乘法得到最终解，即normal equation。但是计算机求解normal equation 的时间复杂度为O(n^3)。优点是根据数学解方程得到，不需要归一化处理。

sklearn中多元线性回归套路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from sklearn import datasets

boston = datasets.load_boston()
# print(boston.DESCR)  # (503, 13)
# print(boston.feature_names)

X = boston.data
y = boston.target

# 除去异常点
X = X[y < 50]
y = y[y < 50]

from sklearn.linear_model import LinearRegression
from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=123)

lin_reg = LinearRegression()
lin_reg.fit(X_train, y_train)

print(lin_reg.coef_)      #  得到最终模型所有参数
print(lin_reg.intercept_)  # 包括截距
print(lin_reg.score(X_test, y_test))   # 应用在测试数据集上的得分

实现normal equation：

首先在原本X_train中加入一列全为1：

1
X_b = np.hstack([np.ones((len(X_train), 1)), X_train])

根据normal equation 的公式，其中intercept_表示直线上的截距，截距与样本特征无关，或者说，截距对应的特征是常数1。coef_表示coefficient，每个特征的系数：

1
2
3
4
_theta = np.linalg.inv(X_b.T.dot(X_b)).dot(X_b.T).dot(y_train)  # 完全根据公式

intercept_ = _theta[0]  # 参数的第一列为截距
coef_ = _theta[1:]

有了参数，就可以用于测试样本。写成函数：

1
2
3
4
5
6
7
8
def predict(X_sample):
    assert intercept_ is not None and coef_ in not None, \
        "Must fit before predict"
    assert X_sample.shape[1] == len(coef_), \
        "the feature number of X_sample must be equal to the lenght of coef_"
    
    X_b = np.hstack([np.ones((len(X_sample), 1)), X_sample])
    return X_b.dot(_theta)

创建样本，使用模型：

1
2
3
X_sample = np.array([[0.5, 20., 4., 0., 0.57, 7., 52., 2.8, 5., 264., 13., 390., 3.16]])

lr.predict(X_sample)  # 返回模型认为的预测值

线性回归的可解释性

对所有数据解normal equation 方程得所有系数：

1
2
3
4
[ -1.05574295e-01   3.52748549e-02  -4.35179251e-02   4.55405227e-01
  -1.24268073e+01   3.75411229e+00  -2.36116881e-02  -1.21088069e+00
   2.50740082e-01  -1.37702943e-02  -8.38888137e-01   7.93577159e-03
  -3.50952134e-01]

系数的正负表示，这个特征与预测指标(如房价)是正相关还是负相关。
正值表示正相关，越大表示这个特征越大房价越高。
负值表示负相关，越大表示这个特征越大，房价越低。
系数的绝对值的大小表示了该特征对房价的影响程度。可以把特征的值从小到大排列，分析什么特征的影响大，什么特和那个的影响小：

1
2
3
4
# 按系数排序，返回排序后的索引
sort_index = np.argsort(lin_reg2.coef_)
# 使用排序后的索引，给特征名称排序 
boston.feature_names[sort_index]

比如，最大值系数表示房间数目。房间数目与房价正相关，且越大房价越高。合理。
最小系数对应一氧化氮浓度。浓度与房价成负相关，且值越大，房价越低。合理。

这就是“现行模型的可解释性”，有针对的采集更多数据，帮助决策。

注意：

1
2
np.array([1, 2, 3, 4, 5, 6, 7, 8])  
np.array([[1, 2, 3, 4, 5, 6, 7, 8]])

前者是向量，大小为： (8,)

后者是矩阵，大小为： (2, 8)

敲黑板机器学习算法实现不是目的，一个算法的优劣是将它放在特定任务中，与其他算法比较得出的。也就是说，单单训练好一个模型，还没结束，而是与其他训练好的模型一起评价，比如使用由confusion matrix 得到的指标：查准率，查全率，F-alpha，P-R曲线， ROC曲线等。

Machine Learning

集成学习-Boosting-(四)

之前说过，集成学习分为两类：学习器间无关系，和基学习器间有关系。前者常使用Bagging 和随机森林。而后者常使用Boosting。Boosting的工作机制如下：先从训练集中训练出一个基学习器，然后根据这个学习器的表现调整样本分布，使得先前的学习器分类错误的样本在后续收到更多关注，最后基于调整后的样本训练下一个学习器。如此反复。也就是说，每个基学习器都在尝试提升整体效果。可以看出，Boosting不能并行执行。

常见两个Boosting

  1. Ada Boosting
  2. Gradient Boosting

Ada Boosting

Boosting算法最著名的代表是AdaBoost：其过程如下：

图 多个学习器串行，调整样本权值

初始样本集每个样本有一个权值，当第一个学习器学习完后，对于不能正确捕捉的样本，调整这些样本的权值。然后第二个学习器接着学习，对于不能正确捕捉的样本调整权值。然后让第三个学习器接着学习。如此反复。可以看出，在整个样本的学习过程中，样本的权值在不断变化。
那么怎样给样本点附上权值，这其实是个问题转化，转化为求极值的问题。

sklearn中使用AdaBoostClassifier()实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 数据集
x, y = datasets.make_moons(n_samples=200, noise=0.4, random_state=111)
from sklearn.model_selection import train_test_split
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=111)

# 创建adaboost 模型
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier

ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=2),
                         n_estimators=100)
model = ada.fit(x_train, y_train)
print(model)
print(model.score(x_test, y_test))

在测试集上结果：92.0%

Gradient Boosting

Gradient Boosting 是另外一种思路，它仅以决策树为基学习器。过程如下图：

对于所有样本，训练第一个模型m1，得到所有分类错误样本。对于上一步中的所有错误分类样本，训练第二个模型m2， 得到这次分类错误样本。如此反复。最终的模型m等于这个过程中所有模型之和：m = m1 + m2 + m3 + m4 + ...。

sklearn使用GradientBoostingClassifier()实现：

1
2
3
4
5
6
7
8
# 同样的数据集
from sklearn.ensemble import GradientBoostingClassifier

# Gradient Boosting使用决策树为基学习器：
gb = GradientBoostingClassifier(max_depth=2, n_estimators=100)
gb.fit(x_train, y_train)

print(gb.score(x_test, y_test))

模型在测试集上的性能： 88.0%

Gradient Boosting 其实是一种残差学习，每一个学习器并不是学习整个样本集，只学习错误分类集。

同样的，Ada Boosting 和 Gradient Boosting 也可以用来处理回归任务。

Machine Learning

集成学习-(三)-随机森林

为什么随机森林强

当集成学习的基学习器均为决策树时，称随机森林，是Bagging的一种变体。决策树在选择划分属性时，是在当前属性集合中选择最优属性；而在随机森林中，对每个基决策树的每个结点，从该节点的属性集合中随机选择一个包含k个属性的子集，再从这个子集中选择最优的属性用作划分。

这个k控制了随机性的程度：当k值等于当前结点的属性集合中所有属性时，表示随机性为0；当k=1时，则表示，在当前结点的属性集合中随机选取一个，之后就使用这一个作为划分，不管它是好是坏(因为没得选，只有这一个)。一般情况下，选取k为log(d), 以2为底数。

为什么随机森林可以“代表集成学习技术”，Bagging中的基学习器多样性是仅仅通过数据的扰动达到的。而随机森林的多样性，不仅来源于数据扰动，还来自属性的扰动。

实现随机森林：

例

使用moon数据集：

1
x, y = datasets.make_moons(n_samples=1000, noise=0.2, random_state=111)

构建一片由500棵树的森林：

1
2
3
4
5
6
7
8
9
10
11
from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(n_estimators=500,
                            random_state=233,
                            oob_score=True)

model = rf.fit(x, y)
# 查看模型参数
print(model)
# 使用oob，用剩下的样本做测试
print(model.oob_score_)

模型参数：

1
2
3
4
5
6
RandomForestClassifier(bootstrap=True, class_weight=None, criterion='gini',
            max_depth=None, max_features='auto', max_leaf_nodes=None,
            min_impurity_decrease=0.0, min_impurity_split=None,
            min_samples_leaf=1, min_samples_split=2,
            min_weight_fraction_leaf=0.0, n_estimators=500, n_jobs=1,
            oob_score=True, random_state=233, verbose=0, warm_start=False)

可以看出随机森林由那些参数，可以如何设置。理解了算法原理，才能理解每个参数如何使用。测试集上准确率为95.6%.

Extra-Tree

还有一种特殊随机森林：Extra-Tree，与经典森林不同的是，这种森林在结点划分时，完全随机，也就是说在当前节点的所有属性里随机选择一个，而非选择最优的。如此一来，森林中的每一棵树的就更加不同了，即多样性更强了。示例如下：

1
2
3
4
5
6
7
8
9
from sklearn.ensemble import ExtraTreesClassifier
etree = ExtraTreesClassifier(n_estimators=500,
                             bootstrap=True,
                             oob_score=True,
                             random_state=233)

model2 = etree.fit(x, y)
print(model2)
print(model2.oob_score_)

结果 95.5%

回顾了Bagging，随机森林，Extra-Tree 都进行了分类任务的应用。也可以将这些集成用于回归任务。

敲黑板样本数量的扰动，样本属性的扰动，增强不同决策树的多样性。

Machine Learning

集成学习-(二)-Bagging

集成学习可以分为两大类：

  • 学习器之间存在依赖关系，必须串行生成序列化方法。
  • 学习器之间不存在依赖关系，可以同时生成的并行化方法。

前者的代表是“Boosting”，后者的代表是“Bagging”和“随机森林(Random Forest)”.

得到泛化能力强的集成，每个学习器要尽量不同，如何做到不同。一个方法是由训练集产生多个不同的子集，在每个子集上训练学习器。如5000个样本，用5个学习器分别学习1000个样本集。如此产生5个不同的模型。但是如此一来，每个模型的性能会有所下降，同时，集成学习的一个优势是每个学习器并不需要具有很强的性能。

从数据中采样

但是，“好而不同”毕竟每个学习器要“好”。所以根据每个学习器只使用数据的一部分，产生两种采样方式：

  • 有放回抽样 自助采样（Bootstrap Sampling）
  • 无放回抽样

自助采样：假设原始数据集由m个样本，对于第一个学习器，随机采样一个样本，放入采样集中，后把该样本放回原数据集。如此采样m次便得到含有m个样本的子集来训练学习器#1。对于其他学习器，采用同样的方式得到训练集。如此得到的不同子集中一定存在重复的元素。最后基于每一个子集训练学习器，后集成。此过程成为Bagging。

对于无放回抽样，就如上述所述，5000个样本是数据集，若分给5个学习器，每个得到1000个样本；10 个学习器，每个得到500个样本。这种方法成为Pasting。其局限性很显然，学习器个数与其子集样本数成反比。

Bagging常用。例：
所使用数据集：

1
2
x, y = datasets.make_moons(n_samples=1000, noise=0.2, random_state=111)
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=111)

使用决策树为基学习器，设置5个，采样为放回采样：

1
2
3
4
5
6
7
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import BaggingClassifier

bagg = BaggingClassifier(DecisionTreeClassifier(),
                         n_estimators=5, max_samples=100, bootstrap=True)
bagg.fit(x_train, y_train)
print(bagg.score(x_test, y_test))

测试集的正确率为：94.4%

设置500个基学习器：

1
2
3
4
bagg2 = BaggingClassifier(DecisionTreeClassifier(),
                         n_estimators=500, max_samples=x_train.shape[0], bootstrap=True)
bagg2.fit(x_train, y_train)
print(bagg2.score(x_test, y_test))

测试集准确率： 96.0%

Out-of-bag Estimate（OOB）

可以计算，通过自助采样，原始数据集中大约有36.8%的样本未出现在每个学习器的样本子集中。所以对于Bagging，天然的，在原始数据集中就有测试集了，即那剩下的原始数据集中的36.7%。

使用sklearn 中的oob_score_ 实现oob：
在放回采样过程中，记录那些样本没有被取到，这些未被取到的作为验证集或测试集，这个过程由oob_score=True 实现：

1
2
3
4
5
bagg3 = BaggingClassifier(DecisionTreeClassifier(),
                          n_estimators=500, max_samples=x.shape[0],
                          bootstrap=True, oob_score=True)
bagg3.fit(x, y)
print(bagg3.oob_score_)

结果0.958。

多核心并行

由于每个学习器没有相互影响，所以所有学习器可以同时学习：
指定n_jobs的值，当其为-1时，表示使用计算机所有物理核心：

1
2
3
4
5
6
7
8
9
10
11
# 并行执行，使用所有核心
bagg4 = BaggingClassifier(DecisionTreeClassifier(),
                          n_estimators=500, max_samples=x.shape[0],
                          bootstrap=True,
                          oob_score=True,
                          n_jobs=-1)
start2 = clock()
bagg4.fit(x, y)
end2 = clock()
print(bagg4.oob_score_)
print(end2 - start2)

计时得到最终执行时间：0.1591450000000001
而使用一个核心的执行时间为：0.6764169999999998

更多采样方式

当数据集的特征较多时，可是对特征进行随机采样：Random Subspaces。只在列上随机采样。如下左图。

另一种采样方式，既对样本随机采样，又对特征的随机采样：Random Patches。既在行又在列上随机采样。如下右图：

左Radom Subspaces & 右Random Patches

既然有对样本数量的自助采样（bootstrap sampling），也有对样本特征的自助采样。如此得到的特征为bootstrap features：

  • Random Subspaces

    只对特征进行随机采样，将学习机的bootstrap_features参数置为True：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # 关闭样数量的随机采样
    random_subspaces_bag = BaggingClassifier(DecisionTreeClassifier(),
                                            n_estimators=500,
                                            max_samples=x.shape[0],  # 所有行
                                            max_features=1,
                                            bootstrap=True,
                                            bootstrap_features=True,  # 一部分列
                                            oob_score=True,
                                            n_jobs=-1)
    start3 = clock()
    random_subspaces_bag.fit(x, y)
    end3 = clock()
    print(random_subspaces_bag.oob_score_)
    print(end3 - start3)

    结果为： 0.835
    运行时间：0.1876460000000002

  • Random Patches，

    既对样本数据量采样，又对特征进行采样。因为原始数据只有2个特征，所以此处只采样一个特征。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    ## random patches 既有样本数的随机采样， 又有特征的随机采样：
    random_patches_bag = BaggingClassifier(DecisionTreeClassifier(),
                                            n_estimators=500,
                                            max_samples=200,  # 一部分行
                                            max_features=1,
                                            bootstrap=True,
                                            bootstrap_features=True,  # 一部分列
                                            oob_score=True,
                                            n_jobs=-1)
    start3 = clock()
    random_patches_bag.fit(x, y)
    end3 = clock()
    print(random_patches_bag.oob_score_)
    print(end3 - start3)

    结果为：0.897
    运行时间： 0.16168400000000016

    对于图像信息，除了pooling采样操作，还可以使用这两种采样操作。

敲黑板

”好而不同“是集成学习的核心。
”不同“的实现方式之一是”采样“：对样本数量采样，对样本特征采样。
即，使用一部分数据训练基学习器。