子非鱼的技术博客

事务并发带来的问题

• 丢失修改（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）映射后输出到下一层

激活函数

序言

二叉树题型的算法主要分为回溯，动态规划，迭代三类。从本质上三者都是在遍历算法基础上的修改。回溯关心的是在每个结点的访问过程中如何更新结果；动态规划关心的是如何拆解出子问题，不具体分析每个结点的状态，而是通过划分子问题让其通过基本问题递归解决；迭代主要是指BFS层序遍历，适用于与深度（或高度）相关的问题求解

二叉树基本结构

1. 二叉树

1
2
3
4
5
6
7

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. 多叉树

1
2
3
4
5

class TreeNode {
public:
    int val;
    vector<TreeNode *> children;
};

二叉树遍历

1. 递归遍历

前序位置：刚进入当前子树根结点的时候（已知根结点信息）

回溯框架

回溯算法求解时要考虑三个问题

1. 路径：已经做出的选择
2. 选择列表：当前可以做的选择，即孩子结点的情况（剪枝做的就是精简孩子结点，避免重复讨论，反映到代码里就是对于某些情况直接continue调过）
3. 结束条件：何时到达决策树的底层，返回结果

求解的关键在于画出决策树，并运用合理的剪枝条件。不要跳出此框架自己去想新写法，很容易漏解或者多解

1
2
3
4
5
6
7
8
9
10

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

全排列问题

排列问题（元素不重复不可复选）

选择列表：避免选当前路径上已经选择过的数字

解决方法：引入used数组，记录从根结点到当前结点的路径信息，判断数字是否被使用

文件系统操作

整体架构

在文件系统和应用程序间有一层抽象层，称为虚拟文件系统（VFS）

• VFS作为抽象层向应用层提供了统一的文件接口（read，write等）
• VFS实现了一些公共的功能，如Directory Cache和Page Cache等
• 规范了接口

VFS向应用层提供统一接口，具体实现不同文件系统有不同实现，VFS将函数指针指向对应函数

核心操作

文件系统的注册

在Linux中，具体文件系统通常是一个内核模块，在内核模块被加载时完成文件系统的注册

磁盘挂载

磁盘的工作原理

磁盘读写的过程

1. 磁盘移动，找到要读的柱面（cylinder，简称C）
2. 从柱面选择具体读哪个磁道（magnetic head，简称H），选择对应的磁头上电（每次只能有一个磁头上电）
3. 旋转磁盘，将对应磁道中要读写的那个扇区（sector，简称S）转到磁头下方
4. 开始读写，将扇区中的内容读到内存缓存区中，或者将内存缓存区中的内容写到该扇区中

生磁盘的使用

第一层抽象：从扇区到磁盘块请求（抽象读写请求）

正常寻址需要通过CHS三维向量，但是可以通过一位扇区编号编址

磁盘读写时间 = 寻道时间（选择柱面）+旋转时间（选择+读取扇区）+传输时间（磁生电活电生磁）

其中寻道时间占主导，故每次只读/写一个扇区是对于时间的浪费，故一次读/写多个扇区，称为块

第二层抽象：多个进程产生的磁盘请求队列（抽象读写方法）