子非鱼的技术博客

设计原则

依赖倒置原则（DIP）

高层模块（稳定）不应该依赖于低层模块（变化），二者都应该依赖 于抽象（稳定）

抽象（稳定）不应该依赖于实现细节（变化），实现细节应该依赖于 抽象（稳定）

开放封闭原则（OCP）

对扩展开放，对更改封闭

类模块应该是可扩展的，但是不可修改

模版方法（Template Method）

模式动机

一些功能在底层开发模块时不知具体实现，而需要在高层模块实现

什么问题适合用动态规划（最优子结构）

符合最优子结构的问题适合用动态规划

最优子结构 是指一个问题的最优解可以通过其子问题的最优解构造出来。换句话说，问题的最优解依赖于子问题的最优解。

例如要计算年级的最高分，可通过计算每个班级的最高分之后取最值得到

动态规划算法框架

确定状态和选择

明确当前值需要通过哪些子结构通过哪些选择得到，用以确定dp数组是一维还是二维的

例如对于斐波那契数列只要知道前2项即可，所以是一维的

对于零钱兑换问题，如果target=10，则粗略估计需要知道0-9的最小值（列），而且要对于不同零钱选择（行）计算最值（也可用一维的做，但二维从语意上更明确）

定义dp数组

事务并发时遇到的问题

数据完整性方面（不同事务对同一行的读写/写写操作）

问题

不同事务对于同一范围内的数据进行增/删/改时需要锁确保在事务提交前只有一个事务能操作该数据

解决方法

对于要修改的数据加锁（lock）

查询结果方法（幻读现象）

问题

在当前读（区别于使用MVCC中ReadView的快照读）的场景下，在事务内不同时间对同一查询条件得到的查询结果不同

解决方法

数据库需要解决的问题（背景）

在转账场景中，A向B转账100元。转账过程需要保证的是要么转账成功，要么转账失败恢复到原始值（原子性 Atomicity）；转账前后A与B账号的存款总数不变（一致性 Consistency）；转账过程中A与B的其他转账操作不影响当前转账（隔离性 Isolation）；转账成功则不可撤回（持久性 Durability）。所以引入事务（Transaction）的概念

事务（解决方案）

特性（ACID）

1. 原子性（Atomicity）：一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节，而且事务在执行过程中发生错误，会被回滚到事务开始前的状态，就像这个事务从来没有执行过一样
2. 一致性（Consistency）：是指事务操作前和操作后，数据满足完整性约束，数据库保持一致性状态
3. 隔离性（Isolation）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致
4. 持久性（Durability）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失

InnoDB 引擎通过什么技术来保证事务的这四个特性的呢？

• 持久性是通过 redo log （重做日志）来保证的；
• 原子性是通过 undo log（回滚日志） 来保证的；
• 隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；
• 一致性则是通过持久性+原子性+隔离性来保证；

并行事务的问题与解决方案（读的隔离性）

问题

1. 脏读：如果一个事务「读到」了另一个「未提交事务修改过的数据」，就意味着发生了「脏读」现象

事务并发带来的问题

• 丢失修改（lost update）：事务 1 与事务 2 从数据库中读入同一数据并修改，事务 2 的提交结果破坏了事务 1 提交的结果， 导致事务 1 的修改被丢失。(W-W)
• 读 “脏” 数据（dirty read）：事务 1 修改某一数据，并将其写回磁盘，事务 2 读取同一数据后，事务 1 由于某种原因被撤消，这时事务 1 已修改过的数据恢复原值，事务 2 读到的数据就与数据库中的数据不一致，是不正确的数据，又称为 “脏” 数据。（W-R）
• 不可重复读（non-repeatable read）：事务 1 读取数据后，事务 2 执行更新操作，使事务 1 无法再现前一次读取结果。(R-W)

并发不一致性的解决办法（封锁协议）

• 一级封锁协议

  事务 T 在修改数据 W 之前必须先对其加 X 锁，直到事务结束才释放（读不加锁）

  一级封锁协议可防止 丢失修改

• 二级封锁协议

  一级封锁协议基础上，事务 T 在读取数据 R 之前必须先对其加 S 锁，读完后即可释放 S 锁

  **二级封锁协议可以防止 丢失修改 和 读 “脏” 数据 **

• 三级封锁协议

  一级封锁协议基础上，事务 T 在读取数据 R 之前必须先对其加 S 锁，直到事务结束才释放

  三级封锁协议可防止 丢失修改、读脏数据和不可重复读

并行事务正确性的唯一准则（可串行化调度）

可串行性的定义

几个事务的并行执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同。 这种并行调度策略称为可串行化（Serializable） 的调度

可串行性是并行事务正确性的唯一准则

什么是冲突操作

冲突操作是指读写操作和写写操作

类不是实体，对象是实体

成员变量（filed）属于对象

成员函数（member function）属于类

Big Three（构造函数，拷贝构造，拷贝赋值）

构造函数

初始化列表

列表初始化（initialize list）仅对成员变量初始化。

在构造函数里对成员变量初始化则为先初始化（默认）后赋值，故所有成员变量必须要有默认的初始化方法（成员变量包含其他类但该类没有默认构造函数则会报错）。构造函数无法主动调用。

尽量使用列表初始化

1
2
3
4
5
6

class A{
  public:
  	int a;
    A(int i):a(i){};  //initialize list
  	// A(int i):{a=i;} 
};

索引存储结构

存储结构

使用B+树作为存储结构，非叶子结点存放索引，叶子节点才会存放实际数据（索引+记录）

为什么使用B+树

B+树与B树的对比如下

• B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少
• B+ 树有大量的冗余节点（所有非叶子节点都是冗余索引），这些冗余索引让 B+ 树在插入、删除的效率都更高，比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化
• B+ 树叶子节点之间用链表连接了起来，有利于范围查询，而 B 树要实现范围查询，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

使用索引时的查询流程

叶子节点存放的是实际数据时（聚簇索引）

当通过主键指定条件时，通过主键索引遍历到叶子结点，获得主键值和其对应的数据

1. 选择合适的模型

对于回归或分类问题使用合适的模型，在本文中对于回归问题使用线形回归模型，对于分类问题使用Logistic回归模型

2. 如何判定当前模型及参数是符合现实要求的（Cost Function）

$$
J(w,b) = \frac{1}{2m} \sum\limits_{i = 0}^{m-1} (f_{w,b}(x^{(i)}) - y^{(i)})^2
$$

$$
f_{w,b}(x^{(i)}) = wx^{(i)} + b \tag{2}
$$

计算预测值与现实值的均方误差后取平均（除以2是为了在求导时与平方的2约去）

3. 数据预处理

特征缩放（Feature Scaling）

如果不同属性的取值返回相差过大则会导致模型收敛得很慢，所以要对属性值做映射。

常用缩放方法：
均值标准化
$$
x_i := \dfrac{x_i - \mu_i}{max - min}\tag{Mean normalization}
$$

图的建立

邻接表

1
2
3
4
5
6
7

vector<vector<int>> build_tree_with_table(int node_count,vector<vector<int>> prerequisites)
{
    vector<vector<int>> graph(node_count);
    for (int i=0;i<prerequisites.size();i++)
        graph[prerequisites[i][0]].push_back(prerequisites[i][1]);
    return graph;
}

邻接矩阵

1
2
3
4
5
6
7

vector<vector<int>> build_tree_with_martix(int node_count,vector<vector<int>> prerequisites)
{
    vector<vector<int>> graph(node_count,vector<int>(node_count,0));
    for (int i=0;i<prerequisites.size();i++)
        graph[prerequisites[i][0]][prerequisites[i][1]] = 1;
    return graph;
}

图的遍历（获取所有路径）

DFS

使用on_path判断当前访问的结点是否在当前访问列表中，如果在则表示有环

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

vector<vector<int>> path_lists;
vector<int> path;
vector<bool> on_path;
void traverse_dfs(vector<vector<int>> graph,int start)
{
if (src < 0 || src >= graph.size()) return;
    if (on_path[start] == true)
        return;
    path.push_back(start);
    on_path[start] = true;
    path_lists.push_back(path);
    
    for (int i=0;i<graph[start].size();i++)
        traverse_dfs(graph, graph[start][i]);
    path.pop_back();
    on_path[start] = false;
}

判断图是否有环

基础

竖向堆叠起来的输入特征被称作神经网络的输入层（the input layer）。

神经网络的隐藏层（a hidden layer）。“隐藏”的含义是在训练集中，这些中间节点的真正数值是无法看到的。

输出层（the output layer）负责输出预测值。

正向传播（推理）

概念

通过线性回归对不同的输入x计算，之后通过激活函数（Activation Function）映射后输出到下一层

激活函数