什么是回文串？

回文串是如abcdedcba，abccba这样的字符串，从前往后和从后往前读是一样的结果。
算法逻辑也很简单，从前和从后同时校验一个字符串，如果不相等直接返回失败。时间复杂度为 $O(n)$。

1
2
3
4
5
6
7
8
9

bool check(string s) {
    int len = s.size();
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

最长回文串问题

给你一个字符串 s，找到 s 中最长的回文子串。
示例：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

暴力搜索

暴力搜索就是依次判断每个子串，如果是回文串就记录下他的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

string longestPalindrome(string s) {
    int len = s.size();
    if (len <= 1) {
        return s;
    }
    int maxlen = 1;
    string res = s.substr(0, maxlen);
    for (int i = 0; i < len; i++) {
        for (int j = 2; i + j <= len; j++) { // j是子串的长度，一种优化手段就是从 maxlen + 1 开始取
            string sub = s.substr(i, j);
            if (check(sub) && j > maxlen) { // 更新最长的回文串信息
                res = sub;
                maxlen = j;
            }
        }
    }
    return res;
}

遍历每个子串的时间复杂度是 $O(n^2)$，检验回文串时间复杂度为 $O(n)$，所以暴力求解的时间复杂度为 $O(n^3)$。

中心扩散法

从每一个位置出发，向两边扩散即可，遇到不是回文串就结束。

举例，s=acdbbdaa时，从s[2]=b开始扩散，是什么步骤呢？

1. 向左扩散，直到不和原字符相等。
   left = 2, right = 2, cur = 2, len = 1
   acdbbdaa
2. 向右扩散，直到不和原字符相等。
   left = 2, right = 3, cur = 2, len = 2
   acdbbdaa
3. 同时向左右扩散，直到左右不相等。
   left = 1, right = 4, cur = 2, len = 4
   acdbbdaa

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

string longestPalindrome(string s) {
    int len = s.size();
    if (len <= 1) {
        return s;
    }
    int left = 0, right = 0, cur = 0;
    string res = "";
    while (cur < len) {
        left = cur, right = cur;
        while (left > 0 && s[left - 1] == s[cur]) { // 向左扩散
            left--;
        }
        while (right < len - 1 && s[right + 1] == s[cur]) { // 向右扩散
            right++;
        }
        while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]) { // 两边扩散
            left--;
            right++;
        }
        if (right - left + 1 > res.size()) { // 更新结果
            res = s.substr(left, right - left + 1);
        }
        cur++;
    }
    return res;
}

该方法遍历中心点时间复杂度 $O(n)$，扩散的时间复杂度 $O(n)$，总时间复杂度 $O(n^2)$。

动态规划

要判断 $dp[l][r]$ 是否是回文串，只需要知道 $dp[l+1][r-1]$ 是否是回文串就可以了。如果是的话，那么如果 $s[l] == s[r]$，那么就是回文串，否则不是。其中有一种特殊情况，在 $s[l] == s[r]$ 相等时，如果这俩相隔是 $2$， 也可以认为是回文串。
初始化边界条件为所有都是 $false$ ，当 $l==r$ 时为 $true$（单个字符是回文串）。
递推关系式为

$$dp[l][r] = ((dp[l+1][r-1]\ \ || \ \ j - i <= 2)\ \ \&\& \ \ s[l]==s[r])\ ?\ true : false$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false)); // 初始化为都不是
    for (int i = 0; i < n; i++) { // 初始化边界
        dp[i][i] = true;
    }
    string res = s.substr(0, 1);
    for (int i = n - 1; i >= 0; i--) { // 注意遍历顺序，倒着遍历是为了保证依赖的数据是经过计算的
        for (int j = i + 1; j < n; j++) {
            if (dp[i + 1][j - 1] || j - i <= 2) {
                if (s[i] == s[j]) {
                    dp[i][j] = true;
                }
                if (dp[i][j] && j - i + 1 > res.size()) {
                    res = s.substr(i, j - i + 1);
                }
            }
        }
    }
    return res;
}

这种方式时间复杂度为 $O(n^2)$，空间复杂度也为 $O(n^2)$。

Manacher算法

这种算法又被称为“马拉车”，可以用 $O(n)$的时间复杂度解决最长回文字符串问题。这个算法的总框架是，遍历所有的中心点，寻找每个中心点对应的最长回文子串，然后找到所有中心点对应的最长回文子串。但是在时间复杂度上做了优化，使其变成线性。

臂长

为了表述方便，我们定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 $2 * length + 1$，其臂长为 $length$。
下面的讨论只涉及长度为奇数的回文字符串。长度为偶数的回文字符串可以在每个字符串之间添加用不到的字符从而达到长度变为 $2n + 1$ 为奇数的目的。

从中心扩展的长度即为臂长，$臂长 - 1$ 就是原子串的回文字符串长度。所以问题就变成了求臂长数组。

求原字符串下标

用 $(i - P[i]) / 2$，就是原字符串开头的下标了。例如 $P[6] = 5$，那么原字符串开头下标为 $(6 - 5) / 2 = 0$，所以返回的结果为原字符串的 $[0, 5 - 1]$ 即可。

求每个 P[i]

用 $C$ 表示回文串中心 $Centre$，用 $R$ 表示臂长右半部分下标边界，即 $R = C + P[i]$。$C$ 和 $R$ 对应当前循环中 $R$ 最靠右的回文串（手最长的，能管这个数组到最远的，之所以可以保证复杂度是因为保证 $R$ 不退缩）。

如图，在求 $P[i]$ 时，用 $i\_mirror$ 表示要求的第 $i$ 个字符关于 $C$ 对应的下标。我们要求 $P[i]$，用中心扩展法就是向两边伸长。但是可以利用已经求出来的回文串中心 $C$ 的对称性，因为 $P[i\_mirror] = 3$，那干脆让 $P[i] = 3$。有以下 $3$ 中情况会导致这个直接赋值不正确：

1. 超出了 R

当求 $P[i]$ 时，$P[i\_mirror] = 7$，但是却不应该等于 $7$，因为从 $i$ 往后面数 $7$ 个已经等于 $22$ 了，然而 $R$ 才到 $20$，很显然还没有探索到那里。但是可以保证我们一定可以扩展到 $R$（因为对称），所以 $P[i]$ 至少可以为 $5$。剩下的只能中心扩展了。

2. P[i_mirror] 遇到了原字符串左边界

此时 $P[i\_mirror] = 1$，但是 $P[i]$ 赋值成 $1$ 是不正确的，原因是 $P[i\_mirror]$ 在扩展时首先是 $\#=\#$ ，之后遇到了边界才终止循环的，但是 $P[i]$ 并没有遇到边界，所以和上面一样继续中心扩展。

3. i == R

这个和情况一很像，将 $P[i] = 0$，之后中心扩展即可。

C 和 R 的更新

一步一步求 $P[i]$， 当求出的 $P[i]$ 的右边界大于当前 $R$ 时，就要更新 $C$ 和 $R$ 了。

此时 $P[i] = 3$，导致 $R_(new) = 10 + 3 = 13 > 11$，那么 $C = 10, R = 13$。

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
37
38
39
40
41
42
43

string longestPalindrome(string s) {
    int len = s.length();
    if (len < 1) {
        return "";
    }
    // 预处理
    string s1;
    for (int i = 0; i < len; i++) {
        s1 += "#";
        s1 += s[i];
    }
    s1 += "#";
    len = s1.length();
    int R = 0;               // 当前访问到的所有回文子串，所能触及的最右一个字符的位置
    int C = 0;               // R对应的回文串的对称轴所在的位置
    int MaxP = 0;            // 最大回文串的回文半径
    int MaxC = 0;            // MaxP对应的回文串的对称轴所在的位置
    vector<int> P(len, 0);   // P[i] 表示以第 i 个字符为对称轴的回文串的回文半径
    for (int i = 0; i < len; i++) {
        if (i < R) {  // 1) 当i在R的左边
            P[i] = min(P[2 * C - i], R - i);
        } else {  // 2) 当i在R的右边
            P[i] = 1;
        }
        // 尝试扩展 P[i]，注意处理边界
        while (i - P[i] >= 0 && // 可以把 P[i] 理解为左半径,即回文串的起始位不能小于 0
               i + P[i] < len && // 同上,即回文串的结束位不能大于总长
               s1[i - P[i]] == s1[i + P[i]]) {  // 回文串特性，左右扩展，判断字符串是否相同
            P[i] += 1;
        }
        // 更新 R, C
        if (P[i] + i - 1 > R) {
            R = P[i] + i - 1;
            C = i;
        }
        // 更新 MaxP, MaxC
        if (MaxP <= P[i]) {
            MaxP = P[i];
            MaxC = i;
        }
    }
    return s.substr((MaxC - MaxP + 1) / 2, MaxP - 1);
}

基类析构函数为虚函数的必要性

由于 C++ 中类的多态性，使用基类指针指向派生类时，若函数是虚的，则调用派生类中的函数。析构函数也是如此。如果有个基类指针指向了派生类对象，删除这个指针，调用的则是派生类的析构函数。派生类的析构函数又会自动调用基类的析构函数，达到所有空间都释放的目的。

如果不声明为虚函数，那么编译器实行静态绑定，在删除基类指针时，只调用基类的虚构函数而不调用派生类的析构函数，造成派生类中有空间没有释放完全而导致内存泄漏。

所以声明为虚函数是必要的，为了防止只析构基类而不析构派生类。

非虚析构函数会发生什么

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

#include <iostream>
using namespace std;
class Parent {
    public:
        Parent() {
            cout << "父类构造函数" << endl;
        }
        ~Parent() {
            cout << "父类析构函数" << endl;
        }
};

class Son : public Parent {
    public:
        Son() {
            cout << "子类构造函数" << endl;
        }
        ~Son() {
            cout << "子类析构函数" << endl;
        }
};

int main() {
    Parent *p = new Son();
    delete p;
    p = nullptr;
    return 0;
}

结果：

1
2
3
4

@└────> # ./a.out 
父类构造函数
子类构造函数
父类析构函数

可以看到，子类析构函数并没有被调用到。

基类析构函数定义为虚函数

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

#include <iostream>
using namespace std;
class Parent {
    public:
        Parent() {
            cout << "父类构造函数" << endl;
        }
        virtual ~Parent() {
            cout << "父类析构函数" << endl;
        }
};

class Son : public Parent {
    public:
        Son() {
            cout << "子类构造函数" << endl;
        }
        ~Son() {
            cout << "子类析构函数" << endl;
        }
};

int main() {
    Parent *p = new Son();
    delete p;
    p = nullptr;
    return 0;
}

结果：

1
2
3
4
5

@└────> # ./a.out 
父类构造函数
子类构造函数
子类析构函数
父类析构函数

小技巧

如果父类的设计者忘记了在析构函数处加 virtual，子类的设计者有义务提醒父类设计者，避免内存泄漏。

C++11 的关键字 override 可以起作用。override 表示函数应当重写基类中的虚函数（用于派生类的虚函数中）。编译器会检查基类中的虚函数和派生类中带有 override 的虚函数有没有相同的函数签名，一旦不匹配便会报错。

因此子类设计者可以在其析构函数后增加关键字 override，一旦父类缺少关键字 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
27
28

#include <iostream>
using namespace std;
class Parent {
    public:
        Parent() {
            cout << "父类构造函数" << endl;
        }
        ~Parent() {  // 此处没加 virtual，会有编译错误
            cout << "父类析构函数" << endl;
        }
};

class Son : public Parent {
    public:
        Son() {
            cout << "子类构造函数" << endl;
        }
        ~Son() override {
            cout << "子类析构函数" << endl;
        }
};

int main() {
    Parent *p = new Son();
    delete p;
    p = nullptr;
    return 0;
}

编译结果：

1
2
3
4

@└────> # g++ test.cc 
test.cc:18:9: error: ‘Son::~Son()’ marked ‘override’, but does not override
         ~Son() override {
         ^

并查集是为了解决什么问题

有10个人，他们之间有错综复杂的关系。如果认定1和2为朋友，2和3也为朋友，那么就认定1和3也是朋友。现在给定两个编号，能否快速知道这两个人是否是朋友？这就是并查集的领域了。

基本思想：

并查集的本质是一个单向且出度为1的图。可以用一个数组来表示，这个数组记录的内容为这个节点所指向的另一个节点的编号。由于这个图出度为1，所以每个元素只唯一的指向另一个元素。而指向的这个节点，我们称为该节点的父节点。
并查集英文叫 unionFind，顾名思义这个数据结构有两个方法，union 和 find。union 用于连接两个集合，find 用于找到这个集合所属的编号。

初始化

只需要把每个节点的父节点设置为自己即可。

1
2
3
4
5

void init() {
    for (int i = 0; i < N; i++) {
        parent[i] = i;
    }
}

所属集合的判断

所属的集合只要一直向上遍历，直到找到祖先为止。祖先的编号就是这整个集合的标志编号。

1
2
3
4
5
6

int find(int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

关系的建立

如果要把两个节点建立并查集关系，只需要指定一个节点的祖先为另一个节点的父节点就可以了。

1
2
3
4
5
6
7
8

void merge(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x == y) {
        return;
    }
    parent[x] = y;
}

路径压缩

在某些极端情况下，这棵树型结构的集合可能会退化为线性结构，这样的情况下find函数会十分耗时。所以我们可以试着在某些方面优化这个效率。

查找时优化

在查找的过程中就直接将沿途的所有元素都指向根节点，大大的缩短下次查找时的时间。

1
2
3
4
5
6

int find(int i) {
    if (i == parent[i]) {
        return i;
    }
    return parent[i] = find(parent[i]); //在第一次查找的时候 将结点直接连到祖先
}

合并时优化

目前的合并是无论如何都让第二个节点的祖先当第一个节点祖先的新祖先，无视了每个集合内树的高度。如果我们记录下树的高度，让较高的树作为新的祖先，较低的树作为它的子节点，可以一定程度的平衡下树的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void merge(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x == y) {
        return;
    }
    // 比高度
    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}

为什么要零拷贝

传统的 IO 拷贝在计算机中拷贝次数太多，速度太慢，零拷贝可以减少拷贝次数，增加系统性能。另外，零拷贝并不是指没有进行文件的拷贝，只是减少了拷贝的次数。

DMA

直接内存访问（Direct Memory Access）是一种执行 I/O 的工作方式。在这种方式中，DMA 控制器从 CPU 完全接管对总线的控制。这意味着数据交换不经过 CPU，而直接在内存和 I/O 设备之间进行 。DMA 方式一般用于高速传送成组数据。DMA 控制器将向内存发出地址和控制信号，修改地址，对传送的字的个数计数，并且以中断方式向 CPU 报告传送操作的结束。

DMA 方式的主要优点是速度快。由于 CPU 根本不参加传送操作，因此就省去了 CPU 取指令、取数、送数等操作。在数据传送过程中，没有保存现场、恢复现场之类的工作。内存地址修改、传送字个数的计数等等，也不是由软件实现，而是用硬件线路直接实现的。所以 DMA 方式能满足高速 I/O 设备的要求，也有利于 CPU 效率的发挥。

用户态和内核态

在 Linux 系统中，有的程序权限很高，可以访问计算机的任何资源，但是有的程序权限就低，只能访问部分资源。这两个类型的程序，就可以映射为用户态和内核态。内核态是计算机的核心，可以访问计算机的任何资源，如网卡、硬盘。为了安全，CPU 不能让用户程序肆无忌惮的访问计算机的任何资源，这样如果用户程序不稳定可能会造成系统崩溃，因此才有的用户态。

• 内核态：可以访问内存的所有数据，包括外围设备，例如硬盘，网卡，cpu 也可以将自己从一个程序切换到另一个程序。
• 用户态：只能受限的访问内存，且不允许访问外围设备，占用 cpu 的能力被剥夺，cpu 资源可以被其他程序获取。

综上所述，在 CPU 想要读取硬盘文件的时候，需要从用户态切换为内核态，才有权限。读取完成之后，为了程序安全，需要从内核态切换为用户态。

普通拷贝

在普通的拷贝时，流程如下：

1. 切换到内核态，先到内核态查询内核缓冲区，如果内核缓冲区有数据，则可以直接拷贝到用户空间中。如果内核缓冲区没有，则 CPU 会让 DMA 加载到内核空间中。这里就会有一次 DMA 拷贝。
2. 拷贝到内核缓冲区之后，CPU 将会从内核缓冲区拷贝走。这是一次 CPU 拷贝。拷贝完成切换到用户态。
3. 写数据的时候，再次切换到内核态。切换完成之后，写到 socket 缓冲区。写完之后，切换到用户态。
4. DMA 通过异步的方式将 socket 缓冲区的数据通过网卡发送到对端。

这种普通的IO。总共有 4 次 CPU 切换（上图蓝色）。分别是：读 2 次、写 2 次。

4 次文件拷贝，分别是：

1. 文件从硬盘到内核空间
2. 内核空间到 CPU
3. CPU 到 socket 缓冲区
4. socket 缓冲区到网卡。

零拷贝

mmap

mmap 是零拷贝的一种方式通过虚拟内存的方式实现。也就是说用户空间和内核空间使用同一个物理地址。这样，文件就不在需要经过用户空间。可以从内核缓冲区直接复制到 socket 缓冲区。减少了一次文件拷贝。流程如下：

1. 调用 mmap，将一块用户空间映射到内核空间。此时进入内核态。DMA 把数据加载到内核空间，这是一次 DMA 拷贝。
2. 切换回用户态。
3. 调用 write，向用户空间写数据。数据直接从内核缓冲区写入到 socket 缓冲区。这是一次 CPU 拷贝。
4. 返回用户态。DMA 异步的将 socket 缓冲区内容通过网卡发送到对端。

共计 3 次内存拷贝，4 次用户内核态切换。

sendfile

sendfile 函数可以在两个文件描述符之间传递数据（完全在内核中操作），从而避免了内核缓冲区和用户缓冲区之间的数据拷贝。流程如下：

1. 系统调用 sendfile() 通过 DMA 把硬盘数据拷贝到内核缓冲区，这是一次 DMA 拷贝。
2. 然后数据被内核拷贝到另外一个与 socket 相关的 socket 缓冲区。这里没有用户态和核心态之间的切换，在内核中直接完成了从一个缓冲区到另一个缓冲区的拷贝。这里虽说是写了 cpu 复制，但是如果网卡支持 scatter-gather ，并没有直接复制内容，而是复制了一些 offset 和 length 之类的数据到 socket 缓冲区。如下图：
   
3. DMA 异步将 socket 缓冲区内容发送给对端，是一次 DMA 拷贝。如果网卡支持 scatter-gather，那么就直接从内核缓冲区直接 DMA 拷贝到网卡驱动。

共计 3 次或 2 次内存拷贝，2 次用户内核态切换。

进程内存布局

在 x86_64 架构的 32 位操作系统中，linux 的进程内存布局如图所示。这个是进程的虚拟地址空间，这些虚拟地址通过页表映射到物理内存。页表由操作系统维护，由处理器引用。每一个进程都有一个自己的页表。内核也是一个特殊的进程，因为虚拟地址被使能会应用于所有软件，所以内核需要在每个进程的地址空间中都保留一部分虚拟地址专门给内核使用。

内核空间

从 0xC0000000 到 0xFFFFFFFF 这 1G 的空间是内核空间，而 0x00000000 到 0xBFFFFFFF 是用户空间。用户空间无法直接访问内核的虚拟内存空间，仅能通过系统调用来进入内核态，从而来访问内核空间的内存地址。只要用户态的程序试图访问这些页，就会导致一个页错误（page fault）。在 linux 中，内核空间持续存在，并且所有进程中都映射到同样的物理内存。内核的代码和数据总是可以被寻址的，因为随时为系统调用和中断做准备。另外，用户进程也是无法访问 0x00000000 ~ 0x08048000 这一段虚拟内存地址的，在这段地址上有诸多例如 C 库，动态加载器如 ld.so 等的映射地址。 如果用户进程访问到该区间会返回段错误。

用户空间

栈

在用户空间的最顶部的部分被叫做栈空间，它一般用于存放函数参数或局部变量。例如：调用一个函数会将函数参数压入到栈空间中，在函数返回时，参数会被栈弹出清理。进程中的每一个线程都有属于自己的栈。

mmap

在栈的低一段便是 mmap，mmap 是一种高效便捷的文件 I/O 方式。内核将文件内容映射在此段内存中，例如加载动态链接库。另外，在 linux 中，如果你通过 malloc 申请一块大于 MMAP_THRESHOLD（默认大小是 128KB）大小的堆空间时，glibc 会返回一块匿名的 mmap 内存块而非一块堆内存。

堆

堆同栈一样，都是为进程运行提供动态的内存分配，但其和栈的的一个很大区别在于堆上内存的生命周期和执行分配的函数的生命周期不同，堆上分配的内存只有在对应进程通过系统调用主动释放或进程结束后才会释放。堆的内存分配效率比栈要低得多。因为栈是由操作系统提供管理的，会在底层堆栈提供支持，分配专门的寄存器（$esp）存放栈的地址，包括压栈出栈也都有专门的指令执行，所以执行效率很高。而堆则是由 C 函数库提供支持，它的机制相对复杂，例如分配一块内存，库函数会按照一定的算法在堆内存空间中搜索可用的足够大的内存空间，如果没有足够大的连续空间，则需要操作系统来重新整理堆内存，这样才有机会分到足够大小的空间，然后才返回。对于堆来说，频繁的 malloc/free（new/delete）势必会造成内存空间的不连续，从而造成大量的内存碎片，程序的运行效率降低。而对于栈来说，分配的一定是连续的内存空间。

BSS段

堆段再往下便是 BSS 段这个静态内存区域，它是用来存储静态局部或静态全局变量的，其在编译期间便决定了虚拟内存的消耗，BSS 段存放的是未初始化的变量。另外根据 C 语言标准规定，未初始化的静态成员变量的初始值必须为 0，所以内核在加载二进制文件后执行程序前会将 BSS 段清 0。

DATA段

DATA 段也是个静态内存区域，也是用来存储静态局部或静态全局变量。但是放的是已经初始化的变量。

代码段

DATA 段再往下便是代码段，这段中存有程序的指令代码。TEXT 段是通过只读的方式加载到内存中的，它可以在多个进程中被安全共享。

什么是树状数组

有这样一个问题，给定一个数组，求它的前 $n$ 项和。

最简单粗暴的方式，就是一个个加起来，存到一个大小为 $n$ 的数组里面，时间复杂度为 $O(n)$。
但是有一个数变了,由 $b_1$ 变为了 $b_2$，需要更新上述的数组，那么更改的时间复杂度为 $O(n)$，因为为了维护上述数组的性质，需要在变更的数之后的所有数都给加上这个变化 $b_2 - b_1$。求和的时间复杂度为 $O(1)$，因为拿到前缀和之后数组的结果就是答案了。
如果这个数组要被频繁修改，那这种方式效率就很低下了。有没有更快的方式呢？

树状数组的雏形

我们可以做以下处理：

首先将每两个数的和都记录下来，那么求和的时候就可以只求 $(n/2)$ 次了。那么再对第二层的数组再做一个两两求和…次数就变为 $(n/4)$ 次了。以此类推。最后就变成上图这个样子了。如果是这样的话，修改一个数，我们只需要更改 $log_2n$个数就可以了！
仔细观察上述数组，我们发现有一些数字是根本用不上的。第 $i$ 层的偶数个数都用不上。那么他就会变成这个样子：

这样空间复杂度就从 $O(n^2)$ 退化为 $O(n)$ 了。这其中的每个数代表一段区间内数字的和。

lowerbits

在介绍树状数组的操作之前，先引入一个函数，这个函数代码如下：

1
2
3

inline int lowerbits(int x) {
    return x & (-x);
}

这个函数的作用是将一个数的二进制格式中最低位的1单独拿出来，比如：

1
2

binary(12) = 00001100   (就展示最低的一个字节)
lowerbits(12) = 00000100  (取最后一个1之后的部分)

这个函数在树状数组中有什么作用呢？$lowerbits(x)$指代的是下标为 $x$ 的树状数组元素所代表的原数组的区间长度。如图：

$lowerbits(12) = 4$ 代表树状数组 $12$ 下标（从 $1$ 开始）所代表的原数组中 $4$ 个数字元素的和。即树状数组元素 $10$ 是原数组 $3,1,2,4$ 的和。

用树状数组的求和

顺着图上的树形结构依次往左上角求和。如图所示。求前 $14$ 项和的值等于 $b[14] + b[12] + b[8]$ 。
代码如下：

1
2
3
4
5
6
7
8

int count(int n) {
    int res = 0;
    while (n > 0) {
        res += b[n];
        n -= lowerbits(n);
    }
    return res;
}

由此可见，利用树状数组求和的时间复杂度是 $O(log_2n)$。

更新树状数组

更新操作则是把所有包含了新数字的树状数组元素统统更新一遍，如图中红线所示。顺着树形结构向右上角更新。

1
2
3
4
5
6
7

// delta 是第 i 位数字的变化值
void add(int i, int delta) {
    while (i < N) {
        i += delta;
        i += lowerbits(i);
    }
}

由此可见，更新时间复杂度为 $O(log_2n)$，比最开始的方式快了很多。

初始化树状数组

以下表示中 $a[i]$ 为原数组元素，$b[i]$ 为树状数组元素。

直接初始化为0，并且对每个点调用add。

1
2
3
4
5

void init() {
    for (int i = 1; i < N; i++) {
        add(i, a[i]);
    }
}

时间复杂度 $O(nlog_2n)$。

使用前缀和辅助数组

1
2
3
4
5
6

void init() {
    for (int i = 1; i < N; i++) {
        pre[i] = pre[i - 1] + a[i];
        b[i] = pre[i] - pre[i - lowerbits(i)];
    }
}

这种方式时间复杂度为 $O(n)$，但是要占用额外的空间。

继承目的

继承的本质是为了复用代码，派生类复用基类的代码，从而减少冗余的代码，使得创建和维护一个引用变得更加容易。继承代表的是 is-a 的关系。

继承种类

公有继承

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
37
38
39
40

#include <iostream>
using namespace std;

class A {
public:
    A() = default;
    A(int a, int b, int c) : pub(a), pro(b), priv(c) {}
    int pub;
protected:
    int pro;
private:
    int priv;
};

class B : public A { // 公有继承
public:
    B(int a, int b, int c) {
        pub = a;
        pro = b;
        // pri = c;
        // test.cc:20:9: error: ‘pri’ was not declared in this scope
        //       pri = c;
        //       ^~~
    }
};


int main() {
    B b(1, 2, 3);
    cout << "b.pub:" << b.pub << endl;
    // cout << "b.pro:" << b.pro << endl;
    // test.cc:31:27: error: ‘int A::pro’ is protected within this context
    //  cout << "b.pro:" << b.pro << endl;
    //                        ^~~
    // cout << "b.priv:" << b.priv << endl;
    // test.cc:32:28: error: ‘int A::priv’ is private within this context
    //  cout << "b.priv:" << b.priv << endl;
    //                         ^~~~
    return 0;
}

1
2

@└────> # ./a.out 
b.pub:1

可以看到，公有继承即保留基类的成员属性，公有 => 公有，保护 => 保护，私有 => 无法访问。

保护继承

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

#include <iostream>
using namespace std;

class A {
public:
    A() = default;
    A(int a, int b, int c) : pub(a), pro(b), priv(c) {}
    int pub;
protected:
    int pro;
private:
    int priv;
};

class B : protected A { // 保护继承 
public:
    B(int a, int b, int c) {
        pub = a;
        pro = b;
    }
};

int main() {
    B b(1, 2, 3);
    cout << "b.pub:" << b.pub << endl;
    return 0;
}

1
2
3
4
5

@└────> # g++ test.cc 
test.cc: In function ‘int main()’:
test.cc:25:27: error: ‘int A::pub’ is inaccessible within this context
     cout << "b.pub:" << b.pub << endl;
                           ^~~

保护继承会把 公有 => 保护，保护 => 保护, 私有 => 无法访问。所以原先的公有成员也不能以公有形式访问了。

私有继承

私有继承结果和保护一样，公有 => 私有，保护 => 私有，私有 => 无法访问。

覆写规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
using namespace std;

class A {
public:
    void func(int a) {
        cout << "A::func(int a)" << endl;
    }
};

class B : public A {
public:
    void func(int a, int b) {
        cout << "B::func(int a, int b)" << endl;
    }
};

int main() {
    B b;
    b.func(10);
    return 0;
}

1
2
3
4
5
6
7
8
9

@└────> # g++ test.cc 
test.cc: In function ‘int main()’:
test.cc:20:14: error: no matching function for call to ‘B::func(int)’
     b.func(10);
              ^
test.cc:13:10: note: candidate: ‘void B::func(int, int)’
     void func(int a, int b) {
          ^~~~
test.cc:13:10: note:   candidate expects 2 arguments, 1 provided

在基类中的某些函数，如果没有 virtual 关键字，函数名是 func （参数类型我们不管）。如果派生类中也声明了这个成员函数，那在派生类的作用域中，所有和这个函数同名的函数都被隐藏。

如果基类中的函数和派生类中有两个名字一样的函数 func 满足下面的两个条件

1. 在基类中函数声明的时候有 virtual 关键字
2. 基类中的函数和派生类中的函数一模一样，包括函数名，参数，返回类型都一样。

那么这就是叫做覆盖（override），这也就是虚函数，多态的性质。其他的情况，只要名字一样，不满足上面覆盖的条件，就是隐藏。

好多人认为，基类中的函数会继承下来和派生类中的同名不同参的函数构成重载。

重载（overload）：
必须在一个域中，函数名称相同但是函数参数不同。重载的作用就是同一个函数有不同的行为，因此不是在一个域中的函数是无法构成重载的。

必须在一个域中，而继承是在两个类中了，所以上面的想法是不成立的。所以，相同的函数名的函数，在基类和派生类中的关系只能是覆盖或者隐藏。

隐藏（hide）:
指派生类的成员函数隐藏了基类函数的成员函数。隐藏一词可以这么理解:在调用一个类的成员函数的时候，编译器会沿着类的继承链，逐级的向上查找函数的定义，如果找到了那么就停止查找。所以如果一个派生类和一个基类都有同一个同名（暂且不论参数是否相同）的函数，而编译器最终选择了在派生类中的函数，那么这个派生类的成员函数“隐藏”了基类的成员函数，阻止了编译器继续向上查找函数的定义。

CUDA 编程

CUDA 一种异构计算平台

CUDA 是 NVIDIA 推出的用于自家 GPU 的并行计算框架，也就是说 CUDA 只能在 NVIDIA 的 GPU 上运行，而且只有当要解决的计算问题是可以大量并行计算的时候才能发挥 CUDA 的作用。CUDA 的主要作用是连接 GPU 和 应用程序，方便用户通过 CUDA 的 API 调度 GPU 进行计算。

一个CUDA应用通常可以分解为两部分，

1. CPU 主机端代码
2. GPU 设备端代码

CUDA nvcc 编译器会自动分离你代码里面的不同部分，host 代码用 cpp 写成，使用本地的 g++ 编译器编译，设备端代码，也就是核函数，用 CUDA C 编写，通过 nvcc 编译，链接阶段，在内核程序调用或者明显的 GPU 设备操作时，添加运行时库。

CUDA 编程

简单示例代码

hello world 例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/*
*hello_world.cu
*/
#include<stdio.h>
__global__ void hello_world(void) {
  printf("GPU: Hello world! \n");
}

int main(int argc, char **argv) {
  printf("CPU: Hello world!\n");
  hello_world<<<1,10>>>();
  cudaDeviceReset(); //if no this line, it can not output hello world from gpu
  return 0;
}

简单介绍其中几个关键字

1

__global__ // 是告诉编译器这个是个可以在设备上执行的核函数

1

hello_world<<<1, 10>>>(); // 其中变量的含义是<<<线程块的个数,每个线程块中线程的个数>>> 一个核函数被执行的次数就是两个参数的乘积

1

cudaDeviceReset();

这句话如果没有，则不能正常的运行，因为这句话包含了隐式同步，GPU 和 CPU 执行程序是异步的，核函数调用后成立刻会到主机线程继续，而不管 GPU 端核函数是否执行完毕，所以上面的程序就是GPU 刚开始执行，CPU已经退出程序了，所以我们要等 GPU 执行完了，再退出主机线程。

调用核函数

核函数就是在 CUDA 模型上诸多线程中运行的那段串行代码，这段代码在 GPU 上运行，用 NVCC 编译，产生的机器码是 GPU 的机器码，所以我们写 CUDA 程序就是写核函数，第一步我们要确保核函数能正确的运行产生正确的结果，第二优化 CUDA 程序的部分，无论是优化算法，还是调整内存结构，线程结构都是要调整核函数内的代码，来完成这些优化的。
我们一直把我们的 CPU 当做一个控制者，运行核函数，要从 CPU 发起。

1

kernel_name<<<grid, block, share_mem, stream>>>(argument list);

<<<grid, block, share_mem, stream>>> 是对 GPU 代码执行的线程结构的配置。我们通过 CUDA C 内置的数据类型 dim3 类型的变量来配置 grid 和 block。

1. grid: grid 中 block 的个数
2. block: 每个 block 中 thread 的布局
3. 是一个可选参数，用于设置每个 block 除了静态分配的 shared memory 外，最多能动态分配的 shared memory 大小，单位为字节，默认为 0。
4. 是一个可选参数，是 cudaStream_t 类型，初始值为 0，用于表示该核函数处于哪个流中。

例如：

1

kernel_name<<<4, 8>>>(argument list);

表现为

可以用 threadIdx.x 和 blockIdx.x （dim3 类型，可以为x, y, z）来组合获得对应的线程的唯一标识。当主机启动了核函数，控制权马上回到主机（不阻塞），而不是主机等待设备完成核函数的运行。想要主机等待设备端执行可以用下面这个指令：

1

cudaError_t cudaDeviceSynchronize(void);

当然，有些操作要阻塞，比如内存拷贝，因为要用到 host。

编写核函数

1
2
3
4

__global__ void sumArraysOnGPU(float *A, float *B, float *C) {
  int i = threadIdx.x;
  C[i] = A[i] + B[i];
}

Kernel核函数编写有以下限制

1. 只能访问设备内存
2. 必须有 void 返回类型
3. 不支持可变数量的参数
4. 不支持静态变量
5. 显示异步行为

完整示例代码

一般 CUDA 程序分成下面这些步骤：

1. 分配 GPU 内存
2. 拷贝内存到设备
3. 调用 CUDA 内核函数来执行计算
4. 把计算完成数据拷贝回主机端
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <cuda_runtime.h>
#include <stdio.h>
// 错误检验的宏
#define CHECK(call)\
{\
  const cudaError_t error=call;\
  if(error!=cudaSuccess)\
  {\
      printf("ERROR: %s:%d,",__FILE__,__LINE__);\
      printf("code:%d,reason:%s\n",error,cudaGetErrorString(error));\
      exit(1);\
  }\
}

__global__ void sumArraysGPU(float* a, float* b, float* res) {
  int i = threadIdx.x;
  res[i] = a[i] + b[i];
}

void initialData(float* vec, int n) {
    for (int i = 0; i < n; i++) {
        vec[i] = (float)i;
    }
}

int main(int argc,char **argv) {
  int dev = 0;
  cudaSetDevice(dev);

  int nElem = 32;
  printf("Vector size:%d\n", nElem);
  int nByte = sizeof(float)*nElem;
  float *a_h = (float*)malloc(nByte); // 输入数据 a
  float *b_h = (float*)malloc(nByte); // 输入数据 b
  float *res_from_gpu_h = (float*)malloc(nByte); // 用于接受从 gpu 返回的结果
  memset(res_from_gpu_h, 0, nByte);

  float *a_d, *b_d, *res_d; // 核函数的输入核输出地址（在 gpu 上申请的内存）
  CHECK(cudaMalloc((float**)&a_d, nByte)); // 在 gpu 上申请内存
  CHECK(cudaMalloc((float**)&b_d, nByte));
  CHECK(cudaMalloc((float**)&res_d, nByte));

  initialData(a_h, nElem);
  initialData(b_h, nElem);

  CHECK(cudaMemcpy(a_d, a_h, nByte, cudaMemcpyHostToDevice)); // 将输入数据拷贝到 gpu
  CHECK(cudaMemcpy(b_d, b_h, nByte, cudaMemcpyHostToDevice));

  dim3 block(nElem);
  dim3 grid(nElem / block.x);
  sumArraysGPU<<<grid, block>>>(a_d, b_d, res_d); // 调用核函数
  printf("Execution configuration<<<%d, %d>>>\n", block.x, grid.x);

  CHECK(cudaMemcpy(res_from_gpu_h, res_d, nByte, cudaMemcpyDeviceToHost)); // 将核函数结果从 gpu 返回给 主机

  cudaFree(a_d);
  cudaFree(b_d);
  cudaFree(res_d);

  free(a_h);
  free(b_h);
  free(res_from_gpu_h);

  return 0;
}

1

nvcc xxx.cu -o a.out

gpu计算

异构计算

异构计算，首先必须了解什么是异构，不同的计算机架构就是异构，按照指令集划分或者按照内存结构划分。

GPU 本来的任务是做图形图像的，并行度很高，一定距离外的像素点之间的计算是独立的，所以属于并行任务。GPU 插在主板的 PCIe 卡口上，运行程序的时候，CPU 像是一个控制者，指挥两台 显卡完成工作后进行汇总，和下一步工作安排，所以 CPU 我们可以把它看做一个指挥者，主机端，host，而完成大量计算的 GPU 是我们的计算设备，device。

上面这张图能大致反应 CPU 和 GPU 的架构不同。

左图：一个四核 CPU 一般有四个 ALU，ALU 是完成逻辑计算的核心，也是我们平时说四核八核的核，控制单元，缓存也在片上，DRAM 是内存，一般不在片上，CPU 通过总线访问内存。

右图：GPU，绿色小方块是 ALU，我们注意红色框内的部分 SM，这一组 ALU 共用一个 Control 单元和 Cache，这个部分相当于一个完整的多核 CPU，但是不同的是 ALU 多了，Control 部分变小。所以计算能力提升了，控制能力减弱了。所以对于控制密集的程序，一个 GPU 的 SM 是没办法和 CPU 比较的，但是对了逻辑简单，数据量大的任务，GPU 更高效。并且，一个 GPU 有好多个 SM。

CPU和GPU之间通过 PCIe 总线连接，用于传递指令和数据，这部分也是后面要讨论的性能瓶颈之一。
一个异构应用包含两种以上架构，所以代码也包括不止一部分：

1. 主机代码在主机端运行，被编译成主机架构的机器码
2. 设备端的在设备上执行，被编译成设备架构的机器码。

所以主机端的机器码和设备端的机器码是隔离的，自己执行自己的，没办法交换执行。
主机端代码主要是控制设备，完成数据传输等控制类工作，设备端主要的任务就是计算。

因为当没有 GPU 的时候 CPU 也能完成这些计算，只是速度会慢很多，所以可以把 GPU 看成 CPU 的一个加速设备。

GPU 硬件结构

GPU的硬件结构，也不是具体的硬件结构，就是与 CUDA 相关的几个概念：thread，block，grid，Wrap，SP，SM。

1. SP：最基本的处理单元，streaming processor。最后具体的指令和任务都是在 SP 上处理的。GPU 进行并行计算，也就是很多个 SP 同时做处理。每个 SP 有它自己的寄存器，比较稀缺的资源。

2. SM：多个（几十或者上百，取决于设备） SP 加上其他的一些资源组成一个 SM，streaming multiprocessor。其他资源也就是存储资源，共享内存，寄储器等。各个 SM 之间只能通过全局内存间接通信，没有其它互联通道，所以这个集群只适合进行纯并行化计算。如果在计算过程中每个 SM 之间还需要通信，则整体运行效率很低。

3. Wrap：

1. SM 中的 SP 会分成成组的 Warp，每组 32 个。
2. Wrap Scheduler 会从在 SM 上的所有 Warp 中进行指令调度。从已经有指令可以被执行的 Warp 中挑选然后分配下去。这些 Warp 可能来自与驻留在 SM 上的任何线程块。
3. 所以，Warp 是 GPU 执行程序时的调度单位，同在一个 Wrap 的线程，以不同数据资源执行相同的指令。
4. 一个 SM 上在某一个时刻，有 32 个线程在执行同一条指令，这 32 个线程可以选择性执行，虽然有些可以不执行，但是他也不能执行别的指令。
5. 当一个 Warp 空闲时（或者在读数据，或者执行完），SM 就可以调度驻留在该 SM 上的另一个 Warp。
6. 并发的 Warp 之间切换是没消耗的，因为资源早就被分配到所有 thread 和 block。

如上图，如果有 if-else 分支，同一个 Warp 内的线程，不能在执行 if 的同时，另一群在执行 else，而是在执行 if 时，另一群选择等待。这种现象又被称为 Warp 发散。

4. grid、block、thread：在利用 cuda 进行编程时，一个核函数会分配一个 grid。一个 grid 分为多个 block，而一个 block 分为多个 thread。其中任务划分到是否影响最后的执行效果。划分的依据是任务特性和 GPU 本身的硬件特性。

1. block 是软件概念，通过设置该属性告诉 GPU 我有多少个线程，该如何组织。
2. 一个 block 只会由一个 SM 进行调度，一旦被分配好 SM，block 就会一直驻留在 SM 中直到程序结束。
3. 一个 SM 可以拥有多个 block，但是要顺序执行：

4. 一个 block 有多个 Warp，例如一个有 512 线程的 block，有（512 / 32 = 16）个 Warp，这些 Warp 轮流进入 SM，由 Warp Scheduler 负责调度。若 block 内的线程数不是 32 的整数倍，那多余的 thread 单独为一个 Warp。
5. 目前一个 block 内最多 1024 个线程。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

#ifndef THREADPOOL_H
#define THREADPOOL_H

#include <list>
#include <cstdio>
#include <exception>
#include <pthread.h>
#include "locker.h"

// 线程池类，定义为模板类是为了代码复用，模板参数T是任务类
template< typename T >
class threadpool
{
public:
    // thread_number是线程池中线程的数量， max_requests是请求队列中最多允许的 等待处理的请求的数量
    threadpool( int thread_number = 8, int max_requests = 10000 );
    ~threadpool();
    // 向请求队列添加任务
    bool append( T* request );

private:
    // 工作线程运行的函数， 它不断从工作队列中取出任务执行之
    static void* worker( void* arg );
    void run();

private:
    int m_thread_number; // 线程池中线程数
    int m_max_requests;  // 请求队列中允许的最大请求数量
    pthread_t* m_threads; // 描述线程池的数组，其大小为m_thread_number
    std::list< T* > m_workqueue; // 请求队列
    locker m_queuelocker; // 保护请求队列的互斥锁
    sem m_queuestat; // 是否有任务要处理
    bool m_stop; // 是否结束线程
};

template< typename T >
threadpool< T >::threadpool( int thread_number, int max_requests ) : 
        m_thread_number( thread_number ), m_max_requests( max_requests ), m_stop( false ), m_threads( NULL )
{
    if( ( thread_number <= 0 ) || ( max_requests <= 0 ) )
    {
        throw std::exception();
    }

    m_threads = new pthread_t[ m_thread_number ];
    if( ! m_threads )
    {
        throw std::exception();
    }
    // 创建thread_number个线程，并将它们设置为脱离线程
    for ( int i = 0; i < thread_number; ++i )
    {
        printf( "create the %dth thread\n", i );
        if( pthread_create( m_threads + i, NULL, worker, this ) != 0 )
        {
            delete [] m_threads;
            throw std::exception();
        }
        if( pthread_detach( m_threads[i] ) )
        {
            delete [] m_threads;
            throw std::exception();
        }
    }
}

template< typename T >
threadpool< T >::~threadpool()
{
    delete [] m_threads;
    m_stop = true;
}

template< typename T >
bool threadpool< T >::append( T* request )
{
    m_queuelocker.lock(); // 操作工作队列要加锁，因为他被所有线程共享
    if ( m_workqueue.size() > m_max_requests )
    {
        m_queuelocker.unlock();
        return false;
    }
    m_workqueue.push_back( request );
    m_queuelocker.unlock();
    m_queuestat.post();
    return true;
}

template< typename T >
void* threadpool< T >::worker( void* arg )
{
    threadpool* pool = ( threadpool* )arg;
    pool->run();
    return pool;
}

template< typename T >
void threadpool< T >::run()
{
    while ( ! m_stop )
    {
        m_queuestat.wait();
        m_queuelocker.lock();
        if ( m_workqueue.empty() )
        {
            m_queuelocker.unlock();
            continue;
        }
        T* request = m_workqueue.front();
        m_workqueue.pop_front();
        m_queuelocker.unlock();
        if ( ! request )
        {
            continue;
        }
        request->process(); // 模板类需要实现这个接口
    }
}

#endif

在c++中使用pthread_create时，第三个参数必须为静态函数。在静态函数中使用类的动态成员（包括成员函数和成员变量），只能通过两种方式实现：

1. 通过类的静态对象来调用。比如单例模式中，静态函数可以通过类的全局唯一实例来访问动态成员函数。
2. 将类的对象作为参数传给该静态函数，在静态函数中引用这个对象，并调用动态方法。

上面代码中向线程参数设置为this指针，在worker函数中获得该指针并调用动态方法run()。

reference:
linux高性能服务器编程——游双$P_{301}$