记录：2022-9-14 回溯算法 组合 MySQL索引 文件访问方法、目录、磁盘结构、文件系统安装 信号量与临界区的关系

学习时间：2022-9-14

学习内容

1、回溯算法初探

回溯算法是一种暴力的递归，他解决的是无法用for循环嵌套完成的题目，他的优化方式是剪枝
回溯法能解决的问题大致如下特征：

1. 组合问题
2. 切割字符串 （子串等）
3. 子集问题
4. 排列问题（强调顺序的组合）
5. 棋盘问题 （N皇后、数独等）

回溯算法思想模板（只是伪代码，写的时候可以往这个方向靠，则可以考虑回溯）

void backtracking(params){
	if(end){
		收集结果
		return;
	}
	for(集合元素集){
		处理节点
		回溯（backtracking(下一个过程)）
		弹栈，撤回上一个操作
	}
}
1
2
3
4
5
6
7
8
9
10
11

2、leetcode 77.组合 使用回溯算法

提供两个解，一个是未剪枝，一个是剪枝

思路如下，当第一次push 元素1后，还有2、3、4可以选择，当选择了2，则满足条件（3、4同理），跳出并收集它
剪枝：当剩余的组合与stack中的长度加起来小于k，说明根本无法构成k那么长的组合，直接返回（节省的不只是一次计算量，还有这一枝上所有的递归）

//剪枝 ac后时间消耗：10ms
class Solution {
    Stack<Integer> path = new Stack<Integer>();
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        backtracing(n,k,1);
        return result;
    }
    public void backtracing(int n,int k,int startIndex){
        if(path.size() == k){
            result.add(new ArrayList(path));
            return;
        }
        for(int i = startIndex;i<=n;i++){
            if(path.size()+n-startIndex < k-1){
                break;//剪枝操作
            }
            path.push(i);
            backtracing(n,k,i+1);
            path.pop();//撤销操作
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//未剪枝，消耗122ms
class Solution {
    Stack<Integer> path = new Stack<Integer>();
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        backtracing(n,k,1);
        return result;
    }
    public void backtracing(int n,int k,int startIndex){
        if(path.size() == k){
            result.add(new ArrayList(path));
            return;
        }
        for(int i = startIndex;i<=n;i++){
            path.push(i);
            backtracing(n,k,i+1);
            path.pop();//撤销操作
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、MySQL索引机制

索引结构

索引可以由多种结构组成，如B+树，Hash表，位图等方式。
并可以维护一个物理上的连续
假设索引为B+树结构，则若column上一个值被设置了索引，则该列的value将会作为B+树上的节点进行排序并维护，下一次搜索时将会按照B+树进行查找，所以可以优化效率

哪些情况适合索引

并不是任何时候都适合建立索引的，首先，对于主键和唯一键值，数据库将会建立唯一索引，这种索引不允许值重复，另外，由于索引需要进行维护，所以更适合写少读多的数据，即经常被用作查询、连接、需要排序的列，适合建立索引。当取值重复率很高的列被用作范围查询，则可以建立聚簇索引（一张表最多建立一个），聚簇索引可以建立在如性别等字段上（所以并不是说，男女就不能建立字段，还是要看具体情况！）

4、操作系统概念 文件访问方法、目录、磁盘结构、文件系统安装

访问方法

顺序访问

读取的时候，读取下一部分，可以跳过n个记录。

直接访问

以任意顺序读取文件位置内容，可以使用一个hash函数实现

其他访问（索引）

类似于索引（数据库）的方式进行访问，一般为数据库使用

目录

目录可以看作一种符号表，将文件名作为条目（所以文件名是不能重复的），这种组织方式允许插入、删除
搜索命名条目以及列出所有条目
目录执行操作如下：

• 搜索文件
• 创建文件
• 删除文件
• 遍历目录
• 重命名文件
• 遍历文件系统

对于目录而已，不能修改文件内容，只能做文件内容上层的操作

磁盘结构

磁盘结构分为以下几种：

单级目录

不对目录分级，所有文件在同一目录中。限制很大，仅代码实现简单

两级目录

这里两级，第一级固定的是用户级，为用户创建单独的一级，形成两级目录，这种方式可以形成用户隔离

树形目录

在两级的基础上，自然而然的扩展。可以让用户创建他的下级目录，并组织文件。
系统内的每一个文件必须拥有唯一的路径名
这里一定要注意，用户级是非常重要的，即使是两级，也是考虑的用户层面，在做文件系统时，必须要把用户级放在第一位

无环图目录

如果文件需要共享，就可以形成图，树结构是无法形成图的，同一文件或子目录可以出现在两个不同的目录中。（不是副本）
实现方式之一：创建一种新的条目：链接，这个条目被搜索时，真实文件的名称包括在了链接信息当中，通过采用该路径名的形式来定位真实文件。实质是一种间接指针，遍历时，操作系统将会忽略这些链接，故对操作系统来说还是在遍历一棵树。

通用图目录

在无环图结构的基础上进行改良，主要针对无环图必须确保没有环的问题。
使用垃圾回收（gc）机制，gc第一次遍历时，标记所有可以访问的文件，第二次遍历收集所有没有被标记的空间，用这种方式来确定何时最后引用被删除并重新分配磁盘空间。
gc的代价比较高，在遍历时避开链接依旧是一个很好的办法。

文件系统安装

这个概念基于文件系统在进程调用它之前，必须要先被挂载（安装），虽然这里翻译是按照，但是我觉得按照mount的英文翻译更加地道。挂在需要两点：

1. 文件名称
2. 挂载点

如/home /users 等，就是挂载点，然后在挂载点上加上文件名称，即可完成挂载
/home/jane /users/jane

若实现10-14到10-15的转换，不同操作系统上的动作是不一样的，有的系统不允许在包含文件的目录上进行安装，或者隐藏原本的文件系统，当现在的系统卸载时，还原原来的文件系统。

5、信号量与临界区的关系

信号量可以保证进程的同步，但是如果没有临界区保护信号量，信号量被多个进程读取时，可能会读到脏值，所以当进程在读取信号量时，需要让信号量处于原子性操作，也就是在内存中有一片区域，这个区域是互斥的，当一个进程进来后，其他进程不能进来，只能自旋等待。
临界区和信号量共同构成了进程锁的功能，临界区如果要可以完成对信号量的保护，必须要有以下三个特点：

1. 互斥
2. 有空让进
3. 有限等待

这三个方面若缺少了一个，临界区就没有保护信号量的功能，首先来看两个例子：

1.仅使用轮转

int turn = 0;
while(turn == 1);
//do something...
turn = 1;
1
2
3
4

int turn = 1;
while(turn == 0);
//do something...
turn = 1;
1
2
3
4

可能出现的问题：当进程2turn变为1后，进程1仍然不会进入执行，不满足有空让进的条件

2.仅使用标记

flag[0] = true;
while(flag[1]);//被另外进程占用
//do something...
flag[0] = false;
1
2
3
4

flag[1] = true;
while(flag[0]);//被另外进程占用
//do something...
flag[1] = false;
1
2
3
4

仅使用标记时，若出现如下顺序：

flag[0] = true;
flag[1] = true;
while(flag[1]);
while(flag[0]);
1
2
3
4

此时将会永远等待，不满足有限等待的条件

这两个例子，都没有满足以上三个条件，所以无法保证原子性。
下面是几种解决方案：

1.非对称标记

让一个进程作为主进程，他需要更加主动的调用，从而保持有空让进
下面以丈夫 妻子买东西留条为例：

2.两个进程（互斥型）：轮转+标记

其中一个进程 如下所示，另一个为对称进程：

flag[0] = true;
turn = i;
while(flag[1]&&turn == i);//此时阻塞
//临界区 do something...
flag[0] = false;
1
2
3
4
5

flag[1] = true;
turn = j;
while(flag[0]&&turn == j);//此时阻塞
//临界区 do something...
flag[1] = false;
1
2
3
4
5

2.多个进程（面包店算法）：轮转+标记

turn 改为 每次值++，选取最小的进行轮转
标记：一个为true，其他为false

choosing[i] = true;
num[i] = max(num[0],...,num[n-1])+1;
choosing[i] = false;for(j=0;j<n;j++){
	while(choosing[j]);
	while((num[j] != 0) && (num[i],i) < (num[j],j));
}
//临界区 do something
num[i] = 0;
1
2
3
4
5
6
7
8