什么问题适合用前缀和

适用于快速、频繁地计算一个索引区间内的元素之和

前缀和算法框架

一维

每次累加前缀，当前元素指的是0-i的前缀和

注：从1开始是为了避免边界另外讨论，sum_list大小为原数组大小+1。填充的边界为0

什么问题适用滑动窗口

对于连续子序列问题，可以使用滑动窗口。例如按要求得到最长/短的序列

滑动窗口算法框架

int low = 0, high = 0;

while (high < nums.size()) {
    // 增大窗口
    window.addLast(nums[high]);
    high++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.removeFirst(nums[low]);
        low++;
    }
}

滑动窗口方法需要考虑两个问题

1. 何时满足题目条件

词嵌入（word embedding）

通过 one-hot 编码来表示单词有两个缺陷：

1. 词维度过高，使得模型更加复杂，训练成本高
2. 词与词之间无法表示关联（其余弦相似度为0）

所以基于此提出了词嵌入技术。将一个维数为所有词的数量的高维空间（one-hot 形式表示的词）“嵌入”到一个维数低得多的连续向量空间中，每个单词或词组被映射为实数域上的向量

word2vec（词嵌入的训练方法）

word2vec 是训练词嵌入的训练方法，其输入为 one-hot 编码，通过一个隐藏层输出单词（CBOW）或者上下文（Skip-gram）的one-hot 编码。其模型结构为 y=softmax(wx+b)

状态机切换流程

初始化

初始化流程主要包括从磁盘中加在持久化配置，将自己的状态设为 Follower

init：从磁盘中加在持久化配置，将自己的状态设为 Follower

becomeFollower：状态机切换为 Follower，执行 Follower 的处理流程

视图（view）

概念

在MySQL中，视图是一种虚拟表，它是由一个或多个基本表的行或列组成的。视图并不实际存储数据，而是根据定义的 select 语句动态生成结果集。视图可以简化复杂的查询操作，提高查询效率，同时也可以保护数据的安全性，隐藏敏感数据。

执行过程

执行过程类似于 select 语句，流程如下

1. 视图展开（预处理器）：将视图名转化为 select 语句
2. 查询优化（优化器）：选择使用索引或者连接算法优化查询效率
3. 执行查询（执行器，存储引擎）：生成优化后的执行计划后，数据库的 存储引擎会根据这个计划执行查询。执行过程中，MySQL 会从底层表中读取数据，并按需执行连接、过滤、排序等操作，最终返回查询结果

为什么要有缓存机制

MySQL 的数据是存储在磁盘里的，但每次访问磁盘开销过大。为此，Innodb 存储引擎设计了一个缓冲池（Buffer Pool），当数据从磁盘中取出后，缓存到Buffer Pool中，下次查询同样的数据的时候，直接从内存中读取，来提高数据库的读写性能。

除了数据的读取保存在缓存中，对数据的修改也不是立即写入磁盘，而是先写到缓存后择机刷盘。所以 Buffer Pool 中包含脏数据（数据页中）和 undo 页

数据库运行期间会发生哪些故障（问题）

事务故障

事务故障指事务未运行到既定的终点（没有commit或显式的rollback），例如对于支付系统若付款失败则需要回滚支付的操作，确保事务的一致性

系统故障

系统故障指需要即时重启系统而造成的数据库故障，现象是修改内存中的修改未写到磁盘，写入磁盘的数据未必是完成的事务

介质故障

介质故障指磁盘损坏造成的故障，需要全量迁移数据库数据

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

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

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

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

动态规划算法框架

确定状态和选择

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

事务并发带来的问题

• 丢失修改（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 锁，直到事务结束才释放（读不加锁）

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

事务并发时遇到的问题

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

问题

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

解决方法

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

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

问题

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

设计原则

依赖倒置原则（DIP）

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

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

开放封闭原则（OCP）

对扩展开放，对更改封闭

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

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

事务（解决方案）

特性（ACID）

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

索引存储结构

存储结构

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

为什么使用B+树

B+树与B树的对比如下

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

执行select的过程

连接器

客户端通过TCP三次握手与数据库建立连接

查询缓存

如果 SQL 是查询语句（select 语句），MySQL 就会先去查询缓存（ Query Cache ）里查找缓存数据，看看之前有没有执行过这一条命令，这个查询缓存是以 key-value 形式保存在内存中的，key 为 SQL 查询语句，value 为 SQL 语句查询的结果。

解析SQL

解析器完成词法分析（根据输入的字符串识别出关键字）和语法分析（判断语句语法）

背景（标准神经网络的局限）

对于序列数据（文本，语音等），使用标准神经网络存在以下问题：

• 对于不同的示例，输入和输出可能有不同的长度，因此输入层和输出层的神经元数量无法固定
• 从输入文本的不同位置学到的同一特征无法共享
• 模型中的参数太多，计算量太大（如果用基于词汇表的one-hot编码）

RNN（循环神经网络）

网络结构

a<n>表示第n时间步最后一层隐藏层的输出，同时也是n+1时间步输入的一部分

y-hat<n>表示第n时间步的输出（通过与a<n>全连接得到）

图的建立

邻接表

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;
}

邻接矩阵

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判断当前访问的结点是否在当前访问列表中，如果在则表示有环

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;
}

判断图是否有环

DFS

使用图的遍历DFS算法，if (on_path[start] == true)时给has_circle赋True

另外，使用了is_visited_list。假设现在以节点 2 为起点遍历所有可达的路径，最终发现没有环。

基础

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

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

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

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} $$

回溯框架

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

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

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

第八章 IO

传统IO

传统IO过程

1. CPU发起IO请求，每次只能请求一个字
2. 磁盘数据写入缓冲区后，通过IO中断通知CPU
3. CPU将缓冲区数据通过寄存器写入内核缓冲区（内存中）
4. CPU将内核缓冲区（内存中）的数据拷贝到用户缓冲区（内存中）

缺点

1. CPU效率低下：CPU需要频繁得处理IO请求
2. 传输效率低下：数据先从磁盘缓冲区拷贝到寄存器后才到拷贝到内存