Misaki`s blog

学习是一种态度


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

【Linux】文件IO详解

发表于 2020-03-27 | 分类于 Linux
字数统计: 7.7k

Linux文件结构

文件描述符

  文件描述符已经不陌生了,在一个进程中一个打开的文件就是用一个文件描述符所表征的,可以看作是一个句柄,就是所谓的遥控器。但是这个遥控器到底怎么来控制具体的文件呢?接下来会依此讲解文件描述符背后的在UNIX环境下实现相关的数据结构。

UNIX环境下的文件共享

  文件描述符用来表征一个文件,但是为什么操作系统要用这么一个整数来表征一个文件呢?这就操作系统底层实现有莫大的关系。
  在进程PCB中有着这么一个部分,IO状态信息,说的再具体点,在PCB中存在着一张表,我们可以叫它文件描述符表也可以叫做打开文件描述符表,这张表每个进程都会有且为进程独有,所以它是进程级的。这张表上的每一个表项都有两个部分组成,文件描述符标志以及一个文件指针。其中文件描述符标志也就是我们所使用的文件描述符fd,当然我们也可以将其看做是这张表的下标。这张表长这样。

文件描述符表

  这张表中每一项都有一个文件指针,那么这个指针又指向哪里呢?这就要提到另一张表打开文件表,注意这张表由操作系统管理,且系统中只有唯一一张这样的表,因此这张表是系统级的。这张表中的每一项都存储着一个进程与这个文件相关的一些信息,其中主要分为三个部分:文件状态标志,文件当前偏移量,v-node结点指针。
  文件状态标志就是文件在打开时的状态标志,例如可读,可写,可读写,阻塞等都会记录在其中,这些状态标志也可以使用fcntl函数修改。
  文件当前偏移量就是文件指针当前在文件中指向的位置,我们可以用lseek函数修改。
  v-node结点指针我们稍后再谈,现在我们要详细讲讲这张表的工作过程。这张表属于系统级的,系统中任何进程打开任何文件都会在其中添加一个记录项,按照一般情况下来说两个不同的进程打开相同的文件也会在表中创建两个不同的表项,因此两个进程对同一个文件可以有不同的状态标志以及文件当前偏移量,一个进程中不同的文件描述符所代表的文件描述符表项中的文件指针也该指向不同的打开文件表项,但是在某些情况下文件描述符表中不同表项的指针却又有可能指向系统级打开文件表中的同一个表项。例如我们在fork子进程时,子进程复制父进程PCB中的大部分信息包括IO状态信息时会复制文件描述符表,因此两个不同的进程此时就会打开同一个文件,并且文件指针的指向也不会改变会指向相同的打开文件表表项;在使用dup函数重定向时一个进程中不同文件描述符表项中的文件指针也会指向同一个打开文件表中的表项。
  这张表中的每个表项长这样。
打开文件表

  最后还剩一个问题,这个v-node结点指针干嘛用的?v-node节点指针当然指向v-node节点的啊。那么什么是v-node节点?说到v-node就不得不提起i-node节点,在UNIX操作系统中操作系统管理文件的方式是通过使用v-node和i-node节点的方式进行管理的,每个文件都会有这样的节点用于保存相关的文件信息,例如v-node节点上保存了文件类型,对这个文件进行操作的函数指针以及对应的i-node节点的指针;而i-node节点上保存了文件长度,文件数据存储在磁盘的位置,文件所属者等。这些文件信息平时存储在磁盘上,当一个文件倍打开时系统会将这些信息读入内存,并且相同的文件的i-node及v-node节点在内存中只会存在一份。这两个节点长这样。
v-node

  那么为什么要用两个节点保存这些信息呢?这是为了在一个操作系统上对多文件系统进行支持。把与文件系统无关的文件信息存储在v-node节点上,其余信息存在i-node上,分开存储,这样的系统也叫做虚拟文件系统。而Linux比较特殊,他其中没有v-node节点而是用了两个不同的i-node节点,但是结果而言大同小异。
  综上所述,把以上集中数据结构连接起来就构成了一个进程对文件进行控制的完整脉络,进程也就得到了和文件控制有关的所有信息,可见并不是所有文件信息都保存在PCB中的。

文件系统

  对于两个不同的进程打开同一个文件,他们的文件指针可能指向不同的打开文件表项,但是最终都会指向同一个v-node和i-node节点,正如之前所说,相同文件的有关信息在内存中只会存在一份。如下图。
文件系统

打开关闭文件

open()

  open()函数用于打开一个文件,函数声明如下。

1
2
3
4
5
6
7
int open(const char *pathname, int flags, mode_t mode);
Arguments:
path:打开文件或创建文件的名字,
flags:表示选项,用|连接多个选项
flags选项宏的定义文件在每个系统中有所不同,Linux中定义在fcntl-linux.h文件中
mode参数仅在使用部分选项时才用到,例如O_CREAT在mode中需要给定文件初始权限
Return Value:打开的文件描述符,失败返回-1

  返回的文件描述符符合最小未使用分配原则。
  其中flags选项有几个比较常用选项,介绍如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//以下这五个选项只能五选其一
O_RDONLY:只读
O_WRONLY:只写
O_RDWR:可读可写
O_EXEC:可执行
O_SEARCH:只搜索(应用于目录)
//剩下这些选项可以同时存在多个
O_APPEND:追加写,打开文件时将文件当前偏移量置为文件长度,建议要是要想像文件末尾追加数据都加上这个选项,原因后面解释。
O_CREAT:文件不存在则创建,全线由mode给出
O_CLOEXEC:当前进程如果发生进程替换,自动关闭当前文件
O_DIRECTORY:打开的不是目录则报错
O_EXCL:同时存在O_CREAT时如果文件存在则报错
O_NOFOLLOW:如果打开的是一个符号链接则出错
O_NONBLOCK:非阻塞打开文件
O_SYNC:非延迟写,即同步写,每次都等待物理写磁盘成功后再返回
O_TRUNC:打开文件则截断文件

  以上这些宏定义在fcntl.h中,但是根据操作系统不同具体定义的位置也各不相同。

openat()

  openat()和open()参数及功能和返回值都很类似,其函数声明和主要区别如下:

1
2
3
4
5
6
7
8
9
10
int openat(int dirfd, const char *pathname, int flags);
int openat(int dirfd, const char *pathname, int flags, mode_t mode);
openat函数与open函数功能类似,唯独多出dirfd参数用以区分功能
openat函数解决的主要问题是
1、可以让同一进程下的多个线程之间拥有不同的当前工作目录,从而可以使用同样的相对路径打开绝对路径可能不同的文件
2、解决TOCTTOU(Time Of Check To Time Of Use)。如果两个文件相关的系统调用互相依赖,则这个系统是脆弱的
openat函数主要特性
1、如果pathname是绝对路径,那么此时dirfd参数毫无意义,功能则与open一致
2、如果pathname是相对路径,且dirfd参数不是特殊宏AT_FDCWD,则将dirfd所在的目录作为此时的当前工作目录,以此打开相对路径的文件
3、如果pathname是相对路径,且dirfd参数未特殊宏AT_FDCWD,则就以当前工作目录打开相对路径的文件,功能与open无异

文件名截断

  在我们利用open()函数创建新文件时如果文件名过长会怎样呢?
  在UNIX系统中,有这么一个宏提前定义在系统中即NAME_MAX,它标识了当前系统中一个文件名最大的字符长度。假设一个系统中此值为255但是我们想要创建一个文件名为256长度的文件时操作系统会怎么处理呢?此时有两种做法。
  第一种做法为截断。即既然只支持最长255那么你可以创建新文件,但是我只截取前255个字符作为新文件的文件名,文件照样会创建成功。这种处理方法在DOS系统上十分常见。
  第二种做法为报错返回-1。即文件名超出系统限制,那么文件创建失败返回-1并且修改errno为ENAMETOOLONG,这种做法在BSD系统和Linux上十分常见。
  如果我们想要知道我们当前系统对于这个问题的处理方法是怎样的我们可以使用pathconf()函数或者fpathconf()查看系统系统限制,如果返回为真则表示当前系统的处理为出错返回而不是截断。

1
2
3
4
5
6
7
8
9
10
int main()
{
//测试文件是否截断
//如果使用一个系统调用如open创建一个新文件的文件名大于NAME_MAX,有的系统会选择截断,而有的系统选择返回-1报错
//如果_POSIX_NO_TRUNC值为真则返回-1报错,为假则对文件名进行截断,并且成功创建
std::cout << pathconf(".", _PC_NO_TRUNC) << std::endl;
//Linux操作系统下的处理为报错返回,并将errno置为ENAMETOOLONG
}

1

creat()

  这个函数可以用于创建一个文件,因为在早期版本中open()函数的选项并没有现在这样丰富,无法创建文件,所以出现了这个函数。函数原型及介绍如下:

1
2
3
int creat(const char *pathname, mode_t mode);
用于新建一个文件,功能与open(pathname, O_CREAT | O_WRONLY | O_TRUNC, mode)完全一致
成功返回文件描述符,失败返回-1

close()

  close()用于关闭一个文件,函数介绍及原型如下:

1
2
int close(int fd);
close用于关闭一个文件,成功返回0,失败返回-1

lseek()

文件当前偏移量

  每个文件在打开后都会一个文件当前偏移量的概念存在,也可以叫做文件指针,它指向文件中某一位置,并且之后的读写操作会全部从此处开始,一般来说文件当前偏移量一般来说是一个非负整数,但是在某些情况下我们获取的偏移量有可能为负值或者大于文章长度。每个文件当前偏移量存储在系统级的打开文件表当中。
  当一个文件被打开时文件当前偏移量被置为0,如果使用了O_APPEND选项则置为文章长度,方便追加。

lseek()

基本使用

  lseek()用于修改文件当前偏移量,函数原型及介绍如下:

1
2
3
4
5
6
off_t lseek(int fd, off_t offset, int whence);
Arguments:
fd:操作的文件描述符
whence:可以有三种参数,SEEK_SET,SEEK_CUR,SEEK_END,分别代表相对位置文件开头,当前文件偏移量,文件结尾位置
offset:表示移动距离,offset可正可负
Return Value:成功返回更改后的文件当前偏移量,失败返回-1,如果当前fd是一个管道,套接字等不可修改的会将errno置为ESPIPE

  注意其中的off_t类型,这个类型为偏移量类型,虽然偏移量为非负,但是这里的类型却是个有符号整型,因此它可正可负,并且它也代表了一个文件的最大长度,如果它是32位的,则文章最大长度为2^31 - 1,在Linux操作系统下它是8个字节的即64位,但是否能创建一个大于2G的文件取决于底层文件系统。
  我们也可以使用lseek()获取当前文件偏移量,方式如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PrintOffset()
{
int fd = open("test.txt", O_CREAT | O_TRUNC | O_RDWR, 0664);
if(fd == -1)
{
perror("error:");
return;
}
//通过以下这种方法可以获取当前的偏移量
off_t curOffset = -1;
curOffset = lseek(fd, 0, SEEK_CUR);
//打印0,可知文件默认打开偏移量为0
std::cout << curOffset << std::endl;
}
int main()
{
PrintOffset();
}


0

  以上方法还可以用来检测一个文件支不支持更改偏移量,例如管道套接字等文件不支持更改,则会返回-1,errno置为ESPIPE。
  还要注意一点,lseek()只更改文件当前偏移量,不涉及IO。

lseek()引起空洞

  之前有提到过文件当前偏移量是可以大于当前文件长度的,如果在这种情况下还进行文件写入是允许的,但是会形成文件空洞。空洞的部分用\0代替,但是空洞并不占用磁盘块。

文件读写

read()

  函数声明及介绍如下:

1
2
3
4
5
6
7
8
9
10
11
12
size_t read(int fildes, void *buf, size_t nbyte);
从文件中读取数据
Arguments:
fildes:读取的文件描述符
buf:数据存放的目标缓冲区
nbyte:最多读取的数据长度,16位无符号整型,一次读取最多为65535个字节
Return Value:
返回实际读取的数据长度,大部分情况下目标文件中有多少数据则读取多少数据并且返回读取长度;
如果是管道或者套接字目前暂无数据则会阻塞
如果是普通文件,读到文件结尾返回0
可以设置非阻塞读取,如果暂无数据则不会阻塞而回返回-1并将errno置为EAGAIN
返回值ssize_t是一个带符号整形

  read()函数读取出错返回-1,对于不同类型的文件有着不同的处理。

write()

  函数声明及介绍如下:

1
2
3
4
5
6
7
8
ssize_t write(int fildes, const void *buf, size_t nbyte);
向文件中写入数据
Argumentes:
fildes:文件描述符
buf:写入数据存放的缓冲区
nbyte:写入的最长数据长度
Return Value:
返回实际写入的数据长度,如果数据长度小于nbyte则在后补'\0';如果文件剩余容量小于nbyte则返回能写入的最大数据长度

  同样的,write()函数读取出错返回-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
28
29
30
31
32
33
void Test1()
{
int fd = open("test.txt", O_CREAT | O_RDWR | O_TRUNC, 0664);
if(fd < 0)
{
perror("error:");
return;
}
//末尾补\0
int ret = write(fd, "Misaki", 7);
std::cout << ret << std::endl;
lseek(fd, 0, SEEK_SET);
char buf[1024] = {0};
ret = read(fd, buf, 1024);
std::cout << ret << std::endl;
std::cout << buf << std::endl;
//可以发现末尾确实补了\0
for(int i = 0; i < ret; i++)
{
std::cout << (int)buf[i] << " ";
}
}

int main()
{
Test1();
}


7
7
Misaki
77 105 115 97 107 105 0

IO效率问题

  首先看以下一段读取文件常用的代码:

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
#define BUFSIZE 4096
bool Test2()
{
int n = 0;
char buf[BUFSIZE];
while((n = read(STDIN_FILENO, buf, 4096)) > 0)
{
if(write(STDOUT_FILENO, buf, n) != n)
{
perror("write error:");
return false;
}
}
if(n < 0)
{
perror("read error:");
return false;
}
return true;
}

int main()
{
if(Test2() == false)
{
std::cerr << "copy error" << std::endl;
return -1;
}
}

  这段代码是很普通的一段从标准输入读取数据写入标准输出的文件读取写入代码,但是其中有一个重要的问题,我们在用文件读取的时候往往需要在程序内开辟一块缓冲区用作数据暂存,问题来了,这块buffer开多大呢?
  这里跟文件系统相关了,我们都知道数据在磁盘上是按照扇区读取的,但是操作系统读取磁盘数据的最小单位是磁盘块,也就是说我们每次读取数据最小都要读取一个磁盘块大小的数据,如果读取数据长度小于磁盘块操作系统也要把整个磁盘块数据先读进来然后再拿其中一部分剩下的丢掉,这样就导致一个问题如果我们读取的数据小于一个磁盘块就会导致效率低下,造成性能浪费,而在Linux操作系统上一个磁盘块大小为4K,所以我们一次读取数据大于等于4K并且为4K整数倍的话效率是最高的。不过现在的操作系统为了提高效率使用了预读技术,这使得不带缓冲的文件IO在使用较小缓冲区读取大的连续存储的文件时也能有较高地效率,我们可以从下图看出:

IO效率

原子性操作

  考虑这么一种场景,两个不同的进程同时打开了一个文件,要对文件进行追加写,但是问题来了,两个进程这里都使用了lseek的方式将当前文件偏移量置为文件末尾处再写,这样的操作并不是一个原子性操作,很有可能导致两个进程同时先将偏移量移到末尾,然后一个写文件结束,另一个再继续在之前的偏移量接着写,这时的偏移量并不在文章末尾,会导致将第一个进程写的数据覆盖。举个例子,假设一个文件目前长度为1500,进程都将偏移量置为了1500,然后第一个线程先写400的数据,之后第二个进程接着准备写400数据,但是第二个进程的偏移量还在1500处,并没有更新为1900,此时再写入数据就会把之前进程写入的数据覆盖。
  以上的问题想要解决也很容易,有两个办法,第一个就是使用O_APPEND选项,在打开文件加入这个选项后,每次写入数据都会自动将偏移量置为文件末尾处再写,不用lseek保证了原子性;第二个办法就是使用pread()和pwrite()函数,这两个函数与read()和write()几乎无异,不同的是它多了一个参数,可以原子性的帮助我们在读写之前修改文件偏移量,但是要注意这里的文件偏移量修改只对这一次操作有效,以下是函数声明及介绍:

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
ssize_t pread(int fildes, void *buf, size_t nbyte, off_t offset);
ssize_t pwrite(int fildes, const void *buf, size_t nbyte,off_t offset);
这两个函数与read和write参数功能以及返回值一致,主要区别在第四个参数offset
这两个函数会将偏移量置为offset在进行读写操作,期间是原子性的,并且不可打断。操作完成后也不会修改原有的偏移量的值。


int main()
{
int fd = open("test.txt", O_CREAT | O_RDWR, 0664);
if(fd < 0)
{
perror("open error:");
return -1;
}
char buf[4096];
lseek(fd, 1, SEEK_SET);
//从这里可以看出pread是将偏移量置为offset,而不是加上offset
int ret = pread(fd, buf, 4096, 1);
std::cout << ret << std::endl;
buf[ret] = '\0';
std::cout << buf;
//事实打印出来的当前偏移量并没有发生改变
std::cout << lseek(fd, 0, SEEK_CUR) << std::endl;;
}


7
Misaki
1

重定向

dup()

  dup()函数用于重定向,传入一个描述符,系统会将当前最小未使用的文件描述符中的文件指针指向这个描述符所指向的系统级打开文件表项,因此在重定向后新文件描述符将和旧文件描述符拥有相同的文件状态和当前文件偏移量以及v-node节点指针,因为这些信息都是存储在系统级打开文件表中的。
  函数介绍及声明如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int dup(int oldfd);
Arguments:
oldfd:旧文件描述符
Return Value:成功返回新文件描述符,失败返回-1


int main()
{
//一个进程执行时自动打开0,1,2三个文件描述符,作为标准输入标准输出标准错误
//在这里我们重定向的新文件描述符自动更新为3
//并且文件描述符重定向旧文件描述符依然可以用,且指向文件不变
int newfd = dup(1);
std::cout << newfd << std::endl;
write(newfd, "123\n", 4);
write(STDOUT_FILENO, "123\n", 4);
}


3
123
123

dup2()

  功能比dup()更加强大,传入两个参数,可以指定让新文件描述符中的文件指针拷贝为旧文件描述符的文件指针,也就是在dup()的基础上我们可以指定将哪个文件描述符作为新新文件描述符,而不是最小未使用。如果新文件描述符已经打开文件则将其关闭。
  函数声明及介绍如下:

1
2
3
4
5
6
7
8
int dup2(int oldfd, int newfd);
让文件描述符表中newfd的项中的文件表项指针更改为oldfd项中文件表项指针
若newfd原先有指向文件并且已经打开则关闭,若newfd == oldfd则直接返回newfd
Arguments:
oldfd:旧文件描述符
newfd:新文件描述符
Return Value:成功返回新文件描述符,失败返回-1
dup和dup2都是原子性的,其相当于调用了close函数和fcntl函数

  dup和dup2的功能相当于调用了functl实现,实现方法如下:

1
2
3
4
5
dup:
fcntl(oldfd, F_DUPFD, 0);
dup2:
close(newfd);
fcntl(oldfd, F_DUPFD, newfd);

内核缓冲与同步写

内核缓冲

  即使我们说文件IO是没有缓冲区的,但是其实并不尽然,我们应该说文件IO是不会维护进程缓冲区,但是Unix操作系统为了提高读写效率会在内核中存在一块缓冲区,我们称之为内核缓冲。以写为例,我们每次调用write()写数据到达文件的时候并不是直接将数据写入文件,因为如果要写入的数据非常多则会因为IO占用非常多的时间,导致阻塞严重。系统在这里的处理时先将要写入的数据写入每个文件的内核缓冲区,然后随后再将它们真正写入文件,这样的写入模式称之为延迟写。
  但是这样会导致问题,对一些需要即时写入即时使用的数据来说会导致文件数据与缓冲区的数据不相符,原因是缓冲区中的数据还没来得及更新,于是这里牵扯到了同步写。

sync()

  sync()通常由系统利用守护进程update每隔30秒周期性调用,它的作用是将系统中所有修改过的内核缓冲区加入写队列,从而让其可以更新到真正的文件中,但是这个函数并不等待真正的写入就会返回。

1
void sync(void)

同步写

  因为系统默认是不会等待真正数据写入文件,对于要求立即写入文件的程序来说这样并不靠谱,于是系统也为我们提供了可以同步写的方法。同步写一般应用于数据库文件当中。

fsync()

  fsync()会传入一个文件描述符,并且等待此文件缓冲区中的数据真正写入到磁盘后才会返回,达到同步写。

1
int fsync(int fd);

fdatasync()

  fdatasync()与fsync()类似,唯一不同的是它只等待文件数据更新到磁盘上即可返回,并不文件的属性信息更新,因此调用它返回会更快。

1
int fdatasync(int fd);

修改文件属性

  在打开文件时可以指定文件状态以及一些附加选项,当然既然可以指定那么就可以修改,而fcntl()就向我们提供了这一功能。

fcntl()

  函数声明及介绍:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int fcntl(int fd, int cmd, ...);
fcntl函数可以更改已经打开的文件的属性
Arguments:
fd:文件描述符
cmd:执行命令
...:不定参数,后面有可能会根据cmd的不同有着不同的需要传递的参数
Return Value:返回值根据cmd的不同也不同,但是失败都会返回-1,大部分设置为主的模式成功会返回0
常用cmd:
F_DUPFD:赋值文件描述符,dup底层就是用这个参数进行实现的,它会将第三个参数起最小未使用的描述符复制为fd所指文件
F_DUPFD_CLOEXEC:这里涉及一个文件描述符标志,FD_CLOEXEC,这也是唯一一个文件描述符标志,当被定义了这个文件描述符标志的文件
当当前进程在exec进程替换时会自动关闭这个文件,防止子进程一直占用,多用于只需要父进程可以使用这个文件而子进程关闭这个文件的文件上
FD_CLOEXEC也可以通过F_SETFD模式进行设置,F_DUPFD_CLOEXEC则与F_DUPFD功能以及参数类似,不同的是会自动为newfd设置FD_CLOEXEC标志
F_GETFD:获得对应于fd的文件描述符标志FD_CLOEXEC作为返回值返回
F_SETFD:对于fd设置新的文件描述符标志,新标志作为第三个参数传入
F_GETFL:对于fd获得文件状态标志,例如O_RDWR之类的称为文件状态标志,但是一个文件中的O_RDWR,O_WRONLY,O_RDONLY,O_EXEC,o_SEARCH是互斥的
因此可以使用O_ACCMODE获得访问方式屏蔽位
F_SETFL:对于fd设置文件状态标志

  这里要区分两个概念,文件描述符标志和文件状态标志。目前文件描述符标志最常用的标志就一个FD_CLOEXEC标志,这个标志也可以在打开文件时加上,也可以通过fcntl()的FD_SETFD选项加上这个标志。这个标志的作用就是当前进程在放生进程替换时会自动关闭有这个标志的文件,主要解决的问题是父进程创建子进程,子进程拷贝了父进程文件描述符表因此有着和父进程相同的打开文件以及偏移量,如果子进程发生进程替换,可能会导致文件无意篡改的情况,所以关闭不用的描述符防止数据无意篡改。文件状态标志就是一些文件相关的状态信息及打开时的选项,常见有如下选项:
fcntl

  以下是使用示例:

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
//打印文件状态标志
void GetState(int fd)
{
int flags = fcntl(fd, F_GETFL);
if(flags < 0)
{
perror("fcntl error:");
return;
}
//用屏蔽字获取当前状态标志
switch(flags & O_ACCMODE)
{
case O_WRONLY:
std::cout << "write only" << std::endl;
break;
case O_RDONLY:
std::cout << "read only" << std::endl;
break;
case O_RDWR:
std::cout << "read write" << std::endl;
break;
default:
std::cerr << "unknow mode" << std::endl;
break;
}
if(flags & O_NONBLOCK)
{
std::cout << "nonblock" << std::endl;
}
if(flags & O_APPEND)
{
std::cout << "append" << std::endl;
}
//一个文件描述符就算设置了SYNC同时写系统也不一定一定会按照预期进行同时写,因此程序员有必要调用fsync()函数
if(flags & O_SYNC)
{
std::cout << "sync" << std::endl;
}
}

int main(int argc, char* argv[])
{
if(argc != 2)
{
std::cerr << "use ./main <fd> << std::endl";
return -1;
}
GetState(atoi(argv[1]));
}


[misaki@localhost BaseIO]$ ./main 0 < /dev/tty
read only
[misaki@localhost BaseIO]$ ./main 1 > test.txt
[misaki@localhost BaseIO]$ cat test.txt
write only
[misaki@localhost BaseIO]$ ./main 2 2>>test.txt
write only
append
[misaki@localhost BaseIO]$ ./main 5 5<>test.txt
read write

  这里要注意的一个文件状态是O_SYNC和O_DSYNC同步写状态,这里就算给一个文件加上了这个标志,操作系统为了优化也不一定会同步写,要想百分百同步写还是需要调用fsync()和fdatasync()函数。

dev/fd

  打开dev/fd中的文件描述符意义基本上等同于重新打开一份已经在进程中打开过的文件,基本上和dup(fd)的作用是差不多的,我们可以这样使用:

1
int fd = open("/dev/fd/0", mode);

  这样的写法等同于

1
int fd = dup(0);

  并且要求mode必须是事先打开文件选项的子集,但是Linux平台是个例外,在Linux上打开/dev/fd的文件等同于打开了一份新的文件,与原来打开的文件无关。

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
#include <iostream>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main()
{
int fd = open("test.txt", O_CREAT | O_RDWR, 0664);
if(fd < 0)
{
perror("open error:");
return -1;
}
write(fd, "Misaki0", 7);
dup2(fd, 1);
std::cout << "Misaki1" << std::endl;
int stdOut = open("/dev/fd/1", O_RDWR);
if(stdOut < 0)
{
perror("open stdOut error:");
return -1;
}
dup2(stdOut, 1);
lseek(1, 14, SEEK_DATA);
std::cout << "Misaki2" << std::endl;
close(stdOut);
close(fd);
}


[misaki@localhost BaseIO]$ cat test.txt
Misaki0Misaki1Misaki2

  这个例子可以看出来利用/dev/fd打开的文件有着自己独有的文件偏移量。
  /dev/fd这种用法一般在shell语句中用于获取一个进程的标准输入标准输出比较多。

【操作系统原理】第二章-进程和线程

发表于 2020-02-17 | 分类于 操作系统原理
字数统计: 9.7k

进程和线程

进程

什么是进程

  在操作系统中,操作系统需要对各种资源进行管理,大概可以分为以下几类:内存,文件,磁盘,进程。所谓进程就是操作系统有序管理应用程序的执行的方式,来保证以下几点:
  1、所有资源对多个应用程序是可用的。
  2、物理处理器在多个应用程序中切换,保证所有程序都在执行中。
  3、处理器和I/O设备都能得到充分的利用。
  因此所有现代操作系统都依赖于一个模型,在该模型中,一个应用程序对应一个或多个进程。进程的定义有以下几条:
  1、一个正在执行的程序。
  2、一个正在计算机上执行的程序实例。
  3、能分配给处理器并由处理器执行的实体。
  4、由一组执行的指令、一个当前状态和一组相关的系统资源表征的活动单元。
  简单来说什么是进程,进程就是正在执行中的程序。而在操作系统中,操作系统为了更好的描述一个进程,于是将进程视为一些元素组成的实体,而其中最重要的两个元素是程序代码和数据集。一般来说一个程序有了程序代码和数据集就可以顺利执行了,但是操作系统说还不够,为了满足操作系统对进程的控制,例如调度,中断,执行等操作,操作系统将每个进程描述为一个叫做进程控制块(PCB) 的数据结构,在PCB中存储着操作系统对控制一个进程所需要的全部信息,可以根据PCB找到程序代码,找到程序的数据,程序获得的资源等等。所以一个进程对于操作系统来说就是一个PCB。PCB中所存储的信息我们在下文中有详细介绍。
  知道了操作系统是通过PCB管理进程的后接下来讨论进程的状态。

进程状态

两状态模型

  在多道操作系统中,我们假设现在的处理器都是单核的即同时只能有一个进程正在处理器中执行,但是操作系统为了让用户看上去所有进程都在“同时”运行于是他在操作系统中设置了时间片,即一个进程可以连续执行的最大时间,并且按照调度算法快速在不同进程间进行切换执行,执行中的进程状态为运行态,而未执行的则成为非运行态,其中关系如下图。

两状态模型

  同时我们可以把非运行态的进程组织到队列中,每次切换进程从队列中调出一个进程开始运行,而切换下来的进程要么重新加入队列要么执行完毕退出,如下图。
两状态模型

  这里提一下可能导致创建新进程的事件和可能导致进程退出的事件。
  进程创建由以下4种事件触发:
  1、新的批处理作业。新的批处理作业进入操作系统肯定会创建新的进程来执行批处理作业。
  2、用户登录。用户登录往往也会创建新进程来执行用户指令,之所以使用进程是为了将用户与操作系统隔离,一个用户指令的崩溃不会影响到其他用户乃至操作系统。
  3、为提供服务由操作系统创建。有时操作系统为了提供一个服务也会创建新的进程,例如用户进程请求打印一个文件,系统可以创建一个管理打印的进程,进而使请求进程可以继续执行。
  4、由现有进程派生。当现有进程引发另一个进程的创建时,操作系统也会创建新的进程,这就是进程派生,这往往很有用,派生出的进程可以帮助主进程处理数据,组织数据等等。
  进程的终止由以下14种事件触发:
  1、正常完成。正常结束运行。
  2、超过时限。进程运行超过规定的时限。
  3、无内存可用。系统无法满足进程需要的内存。
  4、超出范围。进程试图访问非法的内存单元。
  5、保护错误。进程试图使用不允许使用的资源或文件。
  6、算术错误。进程试图进行被禁止的运算。
  7、时间超出。进程等待某一事件发生的时间超过了规定的时间。
  8、I/O失败。在输入输出期间发生错误。
  9、无效指令。进程试图执行一个不存在的指令。
  10、特权指令。进程试图使用为操作系统保留的指令。
  11、数据误用。错误类型或未初始化的一块数据。
  12、操作员或操作系统干涉。操作员或操作系统终止进程。
  13、父进程终止。在某些操作系统中,父进程终止时操作系统会自动终止该进程的所有子进程。
  14、父进程请求。父进程要求终止其子进程。

五状态模型

  如果所有进程都做好了准备,操作系统会从未运行队列中以轮转的方式调度每个进程。但是这里有个问题,如果并非所有进程都做好了准备呢?也许未运行的进程中有些进程正在等待某一事件的发生,也就是处于阻塞,因此单纯的对所有未运行的进程进行轮转是不科学的,应该对所有已经就绪的进程进行调度。解决这种问题的最好方法就是将未执行进程队列拆分为两个队列分别是就绪队列和阻塞队列,由此进程的状态由2状态变为了3状态,此外还要增加新建和退出态,这十分有必要。改进后的状态模型如下图所示。

五状态模型

  运行态:进程正在执行。
  就绪态:进程做好了准备,随时接收调度。
  阻塞态:进程在等待某些事件的发生,在事件发生前不能执行,如I/O操作。
  新建态:刚刚新建的进程,操作系统还未将其加载至内存,通常是PCB已经创建但是还并未加载到内存中的新程序。
  退出态:操作系统从可执行进程组中释放的进程。
  新建态与推出态十分有必要。在一个进程被新建时它并非绝对会被调入内存,通常是分两步,首先创建该进程的PCB,并与之关联,但是此时可能面临内存不足或者操作系统限制了最大进程数导致这个进程还无法被调入进程,因此该进程被暂时留在新建态,在这个状态的进程PCB已经创建并且加载进内存,但是进程的代码和数据往往还留在外村中等待加载。
  退出态也和新建态同理。当进程因为某些人原因要被终止时,此时并不直接将其调出内存,首先操作系统会停止执行该进程的代码,但是暂时让其留在内存中,因为某些辅助程序或是支持程序会来记录该进程相关数据和信息,此时进程停留在退出态。等相关程序收集完所需信息后,再将其所有数据从内存中移除。
  关于阻塞,就绪和运行三种状态的转换更为普遍和便于理解。操作系统从就绪队列中调度某个进程进入运行态运行,当时间片结束后操作系统将其放回就绪态执行其他进程,如果在执行期间进程必须等待某些事件,便将其放入阻塞态,然后调度其他进程执行。当该进程等待的事件完成后操作系统则将其放回就绪态等待调度。
  但是此时又有一个问题,如果所有阻塞进程放在同一个阻塞队列中,当一个事件完成后操作系统不得不扫描整个队列找到那些等待该事件的进程然后将其放进就绪队列中,这样的效率十分低下,因此通常是为每一个事件创建一个阻塞队列。同理当按照优先级进行调度时,也会将优先级相同的进程放进一个就绪队列,避免扫描等低效的做法,这是典型的用空间换时间的做法。
五状态模型

七状态模型

  在介绍七状态模型前,我们思考一个问题,三个基本状态(就绪,运行和阻塞)的所有进程都必须存储在内存中,此时就可能出现一种情况,即所有进程都处于阻塞态,没有就绪状态的进程,此时又开始了处理器的空转,处理器没办法执行进程只能开始等待进程从阻塞态恢复就绪态,并且加入此时又有新的进程处于新建态,由于内存不足,处于新建态的进程也没办法进入内存无法执行,这是一个十分致命的处理器空转问题,解决这个问题有两个方法:扩大内存,很显然成本太高了;将阻塞态的进程暂时调出内存放回磁盘,来让新建态的进程有足够内存进入就绪态开始处理器的调度和运行。
  但是在将一个阻塞态进程挂起后,操作系统可以选择接纳一个新建态进程进入就绪队列,也可以选择将一个之前挂起的进程恢复就绪态,并且为了减少操作系统的负载操作系统更倾向于后者。但是处于挂起的进程也可能还并未接触阻塞,将一个阻塞进程放回内存没有任何意义,于是更好的方法是将挂起区分为两个状态即就绪/挂起态和阻塞/挂起态,这样每次操作系统就只需要考虑是否应该把进程从就绪/挂起态换回就绪态即可。完整的七状态模型如下:

七状态模型

  阻塞/挂起态:进程在外存中并等待一个事件。
  就绪/挂起态:进程在外存中,但只要载入内存即可开始运行。
  并且操作系统允许进程从就绪变为就绪/挂起态,或从阻塞/挂起态变更为阻塞态,只是这样做的意义不大,因此并不会这样做。
  导致进程被挂起的事件有以下几种:
  1、交换。为了释放内存空间。
  2、其他OS原因。操作系统可能会挂起后台进程或者工具进程,或挂起可能会导致问题的进程。
  3、交互式用户请求。用户希望挂起一个进程来进行调试。
  4、定时。进程可被周期性的执行,并在等待下一个时间间隔时挂起。
  5、父进程请求。父进程可能希望挂起后代进程的执行,以检查或修改挂起的进程。

进程描述

进程在操作系统中的描述方式

  操作系统可以管理计算机内的任何资源,包括内存、设备、文件和进程但是操作系统是如何管理的呢?对于操作系统来说,所有的资源都被组织成对应的数据结构,内存对应内存表,设备对应设备表,文件对应文件表,进程自然也有进程表,如下图。接下来我们将详细介绍操作系统如何描述操作系统中的所有进程,也就是进程表的结构。

进程描述

  如上图所示,进程表中存放着一个一个进程,而每个进程项都指向一个进程映像,什么是进程映像呢?我们说一个进程最基本的元素是用户代码以及元素集,初次之外还有若干操作系统控制进程所需的信息,这些信息都存放在进程映像中,并且还有一个进程用于存储临时数据的栈,因此进程映像中的典型元素可以概括如下:
  1、用户数据。用户空间中的可修改部分,包括程序数据、用户栈区域和可修改的程序。
  2、用户程序。待执行的程序。
  3、栈。每个进程有一个或多个后进先出栈,栈用于保存参数、过程调用地址和系统调用地址。
  4、进程描述块。操作系统控制进程所需的数据。
  有了以上信息就有了一个进程调度,运行所需的全部数据,这些数据在内存中有可能是连续的也有可能是不连续的,这根据操作系统内存管理的方式来决定,但是但从操作系统描述管理进程方式来看,操作系统通过在内存中的主进程表,每一表项都至少包含一个指向进程映像的指针,通过进程表操作系统可以找到控制进程所需的全部数据。

进程属性

  我们知道了操作系统通过进程表和进程映像描述进程,进程映像中的用户数据和用户程序都是根据用户所写的程序而定的,栈也只是用来保存参数调用地址所用的临时储存空间,但是其中我们要尤为重要介绍PCB(进程描述块)。正如之前所说进程描述块中储存了操作系统控制进程所需的一切信息,对于操作系统来说拿到进程控制块就可以控制进程进行调度等操作,那么进程控制块中到底存放了进程哪些信息呢?
  不同操作系统的PCB中组织的信息是不同的,但是PCB中所有操作系统都需要的共用基础信息一共8种:
  1、标识符:PID,与进程相关的唯一标识符。
  2、状态:进程状态,状态的划分是接下来介绍的重点。
  3、优先级:与进程调度有关的优先级。
  4、程序计数器:程序中即将执行的下一条指令的地址。
  5、上下文数据:进程执行时处理器的寄存器中的数据。
  6、内存指针:包括程序代码及相关数据的指针,以及与其他进程共享内存的指针。
  7、I/O状态信息:进程的I/O请求,分配给进程的I/O设备和进程使用文件
  8、记账信息:包括处理器时间综合、使用的时钟数综合、时间限制、记帐号等。
  这些信息一共可以分为三类进程标识信息、处理器状态信息、进程控制信息。进程标识信息典型的就是标识符,他是一个操作系统中唯一标识一个进程的基本索引。处理器状态信息由处理器寄存器的内容组成,中断进程时,必须保存寄存器中的所有信息,以便进程恢复时使用,这些信息就保存在PCB中,典型的有上下文数据。进程控制信息是操作系统控制和协调各种活动进程所需的额外信息,例如进程优先级。
  根据以上的介绍,进程映像在虚存中的结构基本如下图所示,但是具体情况还得视操作系统的具体管理方案而定。

进程描述

进程控制

执行模式

  操作系统必须保证自己的安全性,因此再让用户进程运行时并不能将所有的权限交给用户,这样操作系统很可能会被进程搞到崩溃,最好的方式是操作系统将一些特权指令不进行公开,用户进程不能直接执行这些指令,但是操作系统允许进程发起使用特权指令的请求,然后再有操作系统自己代替用户执行指令,这样可以大大增强操作系统的健壮性,同时内存也并不会让用户进程都可以访问到,如果修改了操作系统即内核可能会发生致命错误,于是这中间操作系统加入了种种限制,先从一个进程的执行上来说,操作系统将其分为了两种模式用户模式(用户态/目态)和内核模式(内核态/管态)。
  用户进程默认是在用户模式下运行,在用户模式下进程的权限受到控制,而如果发生了一些特殊事件,例如请求系统调用模式会从用户模式转换为内核模式。说白了用户模式即处理器在执行用户代码,内核模式即处理器目前在执行内核代码。那么这样有出现两个问题,处理器如何知道它正在什么模式下执行?一般情况下,程序转太子中通常存在一个只是执行模式的位,该位会因模式的变化而变化,也就是说在处理器的一个寄存器中存储了当前处理器处于什么模式下的信息。例如Intel Itanium处理器中就有一个包含2位CPL(当前特权级别)字段的处理器状态寄存器用于存储模式信息。

进程创建

  操作系统在创建一个进程的时候会进行哪些工作呢?当操作系统决定创建一个进程时会执行以下操作:
  1、为新进程分配一个唯一的进程描述符。
  2、为进程分配空间。
  3、初始化PCB。
  4、设置正确的链接。例如将进程放到就绪队列中,而就绪队列是一个链表,此时就需要在数据结构上进行连接。
  5、创建或扩充其他数据结构。例如创建账单和评估性能。

进程切换和模式切换

进程切换

  进程切换在什么时候发生呢?理论上在任何时刻只要操作系统拿到控制权就可以进行进程切换,那么什么时候操作系统会重新拿到控制权呢?
  这里首先考虑中断的情况,而中断又可分为两种:中断和陷阱。中断一般是与当前正运行进程无关的某种外部事件相关,例如完成了一次I/O操作,中断处理器完成一些基本的辅助操作后将控制权转给与已发生的终端相关的操作系统历程,简单来说中断的发生属于正常的事件,不过是操作系统暂时停止执行当前进程转为处理另外一件更加紧急的事情。例如以下三种中断:
  1、时钟中断。当前进程时间片到期,转为从就绪队列中调度新的进程开始运行。
  2、I/O中断。某一I/O完成,操作系统判断是否有正在等待该I/O的进程,如果有将其放回就绪态,随后操作系统根据调度算法调度合适的进程继续运行。
  3、缺页中断。处理器遇到一个引用不存在内存中的虚存地址时,此时会发生缺页中断,然后操作系统要根据算法将访问的页调入内存,这块的处理与操作系统对内存管理有很大关系。
  除了中断,陷阱也有可能会导致进程状态的切换。所谓陷阱就是异常或者错误。即发生在程序内部的不可预期的非法错误。如果错误致命则将当前进程改为退出态,不致命时操作系统的行为决定于操作系统的设计,有可能是简单的通知用户,也有可能是尝试恢复。
  还有一种可能会导致进程切换的事件,就是系统调用。当用户进程发起一个特权指令(系统调用)时,操作系统会将当前用户进程设置为阻塞态,然后会调用系统例程执行系统调用指令,当执行完毕会在此调度用户进程开始执行。
  综上所述,可能造成进程状态切换的事件有三种中断,陷阱(异常),系统调用。

模式切换

  操作系统为了安全设置了不同的执行模式,那么操作系统何时进行模式切换呢?我们知道内核模式就是处理器在执行内核中的系统代码,那么不难得出,只要发生状态转换的事件一定会造成模式转换。例如中断,不管时哪一种中断,都少不了操作系统要根据调度算法重新调度进程开始运行,更不用说缺页中断中操作系统还需要进入内核状态执行内存置换算法换页等等;异常也是需要操作系统判断如何进行下一步处理也需要进行模式切换;系统调用就是在执行系统历程,更需要模式的切换,因此我们可以得出进程模式切换的基本事件就是中断,陷阱(异常),系统调用。
  但是要注意的时,并非模式切换一定会导致运行态进程切换,例如在中断后操作系统根据调度算法决定继续执行当前用户进程,那么当前用户进程就完全不需要改变状态,相比切换运行态进程单单切换模式,操作系统所要做的操作可要少多了。所以进程切换一定会导致模式切换,但进程模式切换并不一定会发生进程状态切换。

操作系统的组织形式

  我们之前的介绍都基于操作系统是在所有进程独立外的一个大型程序,是一组进程,那么操作系统到底是进程么?如果是进程的话又要怎么控制它?
  以下是几种操作系统内核的设计方式。

无进程内核

  这种设计方式在许多老操作系统中都十分常用,是一种相当传统的设计方式。这种设计方式的原则是将操作系统视为独立于每个用户进程外执行的一个大的系统内核。我们每次要执行操作系统代码例如发生中断,陷阱,系统调用时,都需要进行代码及及数据的切换,将用户代码及数据暂时保存然后执行操作系统内核代码,执行完毕后恢复调度用户进程或是调度其他进程。在这种设计方法下,进程这一概念仅适用于用户程序,操作系统代码则是在内核模式下单独运行的实体。下图为这种设计方法的示意图:
进程描述

在用户进程内运行

  较小的计算机操作系统通常采用这种设计方式,这种方式是将系统内核代码放到每个进程虚存中的共享区,这样做的好处是如果要执行系统代码不需要像无进程内核那样切换代码及数据以切换系统历程,这种方式仍然是在每个用户及进程内部执行操作系统代码,不需要切换进程,只用在同一进程中切换模式即可,所带来的系统开销更小,更加快捷。并且在一个进程内用户程序和操作系统程序都可执行,而在不同用户进程中执行的操作系统程序是相同的,这也是为什么要将系统内核放到共享地址空间的原因,在这种方式下一个进程在虚存中的映像如下:
进程描述

  这种设计方式的示意图如下:
进程描述

基于进程的操作系统

  这种设计方式是把操作系统作为一组系统进程来实现。和其他方法一样同样是在内核模式下运行系统代码,但是在这种情况下是吧内核功能都组织为独立的进程,但同时往往也将一些进行进程切换工作的代码独立出来。这种方式的好处是使用模块化系统设计的原理,可以将一些操作系统功能作为独立进程来实现,同时这种方式在多处理或多继环境中很有用。这种设计方式的示意图如下:

进程描述

线程

线程和进程

  现代的大多数操作系统都支持线程的使用,因为进程所具有的两个特点资源所有权和调度,但是操作系统更希望将这两个特点分开进行处理,于是便诞生了线程,我们将进程视为资源分配的基本单位,将线程视为处理器调度的基本单位,线程也可以视为一个轻量级进程。

多线程

  多线程是指操作系统允许在单个进程内有多个并发执行路径,一个并发执行路径又被成为一个线程。早期各个版本的操作系统他们支持多用户进程,即允许一个任务内拥有多个进程进行并发处理,但是每个进程内部只允许有一条执行路径,也就是只允许拥有一个线程,而如今的现代操作系统中绝大多数操作系统支持多线程方法,其中的差别可用下图表示:

多线程

  在多线程的基础上程序并发将会更容易实现,因为线程是一个轻量级进程因此切换和调度的消耗会更少,并且同一进程内的线程之间共享虚拟地址空间,因此通讯会更加方便。在多线程环境中,进程定义为资源分配基本单位和一个保护单位,一个进程内部有:
  1、容纳进程映像的地址空间。
  2、对处理器、其他进程(进程间通讯)、文件和I/O资源(设备和通道)的受保护访问。
  一个进程中可能有一个或多个进程,每个线程都有:
  1、一个线程执行状态。
  2、未运行时保存的线程上下文。
  3、一个执行栈。
  4、每个线程用于局部变量的一些静态存储空间。
  5、与线程内其他线程共享的内存和资源的访问。
  在多线程环境下,每个进程依然有自己的进程控制块以及进程映像,但是进程中的每个线程也拥有属于自己的独立的栈以及线程控制块,控制块中存储着线程状态,调度优先级,上下文数据等,这些是每个线程独立的信息,除此之外进程内的代码段用户数据段包括进程控制块中的信息在进程内各个线程间共享,因此才可以做到进程内各个线程之间都驻留在同一地址空间中可以做到除独立信息外的数据及代码共享。但是每个操作系统对多线程环境的实现方法都不尽相同,具体实现方法视具体环境而定,但是都应该满足进程和线程各自的基本特点。模式如下:

多线程

进程和线程之间的区别

  这是十分常见的问题,在此做同一归纳和梳理:
  1、进程是资源分配的基本单位,线程是处理器调度的基本单位。
  2、同一进程内线程共享进程状态和资源,例如数据段,代码段,I/O信息等。但是每个线程内也有独立的数据,每个线程都拥有属于自己的栈,线程属性信息存在线程控制块中,例如上下文数据,线程状态,调度信息等。
  3、线程是轻量级进程,因此创建和销毁所消耗的系统资源更少,更快。
  4、同一进程内线程切换所消耗的资源相比进程切换更少且更快。
  5、同一进程内线程共享大部分数据因此通信起来更加方便,无需借助内核。

线程分类

  在讨论线程分类前我们先思考这么几个问题:如果进程中的一个线程因为请求资源而被阻塞那么这整个进程是否应该被阻塞?在多核操作系统中统一进程中的线程是否应该允许并行执行?
  根据以上两个特点,我们将线程可以分为内核级线程(KLT)和用户级线程(ULT)。它们二者之间各有优点各有特色,当然这都却决于操作系统的具体实现方式的基础上。示意图如下:

多线程

用户级线程

  在纯ULT操作系统上,对于操作系统来说线程是不可见的,操作系统依然只负责维护进程的相关控制和管理工作,而进程内线程之间的调度以及管理包括通信全部由应用程序自行完成,内核并意识不到现成的存在。用户可以使用线程库来将任何一个程序设计成多线程的,并用线程库完成多线程的管理和控制。
  在这样的实现方式下由于操作系统并无法意识到线程的存在所以除非用户自己主动调度线程,操作系统并无法完成进程内线程间的切换,并且如果此时进程内一个线程发生阻塞,例如进行了一次系统调用,系统会将整个进程置为阻塞态,包括进程内其他线程也会一起阻塞,这是十分不灵活的设计。
  例如假设进程B中有着线程1线程2两个线程,它们的状态如(a)所示,现在有可能发生如下情况:
  1、线程2进行了一次系统调用,由于操作系统无视线程的存在,因此它认为是进程B进行了系统调用,因此将整个进程B进行了阻塞。在此之后线程2依然处于运行态,但是对于操作系统来说线程2实际上并不处于运行态。直到进程B取消阻塞,线程2继续恢复运行。此时状态如(b)所示。
  2、时钟中断使整个进程B停止运行态转为就绪态,此时调度其他进程执行,此时将进程B置为就绪态,线程2依然处于运行态,直到下次再此调度进程B恢复线程2的运行。如图(c)所示。
  3、线程2运行到需要线程1执行某些动作的一个点,应用程序内部将线程2置于阻塞态,开始运行线程1。如图(d)所示。

多线程

  使用ULT有以下优点:
  1、所有线程管理数据结构都在进程内的用户地址空间中,线程之间调度不需要内核的参与,因此就不需要模式的转换,效率更高。
  2、不同的调度程序可以设置不同的线程调度算法,灵活性高。
  3、ULT可在任何操作系统上运行,不需要对系统内核代码修改以支持ULT。
  但ULT也有着以下缺点:
  1、一个线程的进行了系统调用导致阻塞会阻塞整个进程,影响其他所有线程。
  2、多线程应用程序无法利用多处理技术,即内核一次只能把一个进程交给处理器,因此一个进程中只有一个线程可以执行,这相当于再一个进程内实现了多道程序设计,并无法使一个进程内的线程并行执行。
  当然以上两种缺点是有办法弥补的。如果希望程序并行执行就将程序设计为多进程而非多线程;系统调用使进程阻塞可以使用套管技术解决,即将一个可能会产生阻塞的系统调用转换为一个非阻塞系统调用,当然这样的处理更加繁琐一些。

内核级线程

  内核级进程就是将进程的管理全权交给内核来处理,用户使用内核提供的API来控制线程,Windows就是使用这样的方式来实现线程的。
  KLT的优点就是ULT的缺点,KLT的缺点就是ULT的优点。其中最大的缺点就是每次线程之间的切换都需要内核模式的切换,消耗更大,但是可以肯定的是哪怕KLT线程的消耗再大也是远远小于进程之间切换的,因此为了方便管理目前常用的操作系统都是基于内核级线程来实现的。

混合方法

  在混合方法中,内核级线程会被映射到一些由内核管理的内核级线程上,内核级线程是小于或等于用户级线程的。当用户级线程和内核级线程相等时此时等价于使用了纯KLT方式。
  这种混合方法在设计合理时可以完美结合KLT和ULT的优点,并克服它们的缺点。目前Solaris就是使用了这种混合线程的方法。

Linux的进程和线程管理

进程管理

  Linux属于类UNIX操作系统,实现的原理与UNIX进程的实现方法类似,其实大部分的操作系统都要遵循系统设计的基本原理,但是实现细节上会有所不同。在Linux上进程状态转换如下图:

多线程

  在Linux系统实现中最大的变化就是将阻塞态变为了可中断和不可中断两个状态,并且加入了停止态。
  1、可中断:这是一个阻塞态,进程正在等待一个事件的结束。
  2、不可中断:这是一个阻塞态,与可中断的区别是,此时进程正在等待一个硬件条件,因此屏蔽任何信号。
  3、停止:进程收到信号要求被其他进程暂停执行,并且只能由另一个进程的主动动作恢复运行。

线程管理

  Linux使用一种十分特殊的线程处理方式,它内核中并没有独立的线程控制块,Linux选择使用PCB模拟实现线程,因此在Linux中PCB其实就相当于是一个线程。
  那么Linux又是如何实现进程间数据独立线程间数据共享的呢?Linux将用户级线程映射到内核级进程上,组成一个用户级进程的用户级线程则映射到共享一个组ID的多个Linux内核级进程上,使得同一个组内部的进程共享文件和内存等资源,就像一个进程内部的线程共享资源一样。也就是说用进程模拟实现线程,通过给进程分组的方式来实现数据的共享和独立。
  同时Linux在内部又通过命名空间来管理进程的数据。命名空间可使一个进程拥有与其他不同命名空间的进程不同的系统视图,因此可以获得不同资源。典型的命名空间有:
  1、Mount命名空间。为进程提供文件系统层次的特定试图。
  2、UTS命名空间。与系统配置有关。
  3、IPC命名空间。隔离进程间IPC资源,如信号量。
  4、PID命名空间。隔离进程ID空间。
  5、网络命名空间。隔离与网络相关的系统资源。
  6、用户命名空间。提供容器使其与父进程隔离。

【操作系统原理】第一章-操作系统概述

发表于 2020-02-07 | 分类于 操作系统原理
字数统计: 5.2k

操作系统概述

操作系统设计的目标和功能

  在最早期的计算机中,并没有能够称得上是操作系统的服务管理程序,例如早期的串行处理计算机,就是人们把程序一个一个输入进计算机,设定好预计时间,然后让操作系统进行执行。这样的串行处理存在着调度不合理,准备时间长的问题,并不便于使用。
  于是人们想方设法希望可以设计出便于使用的操作系统,而到现代,计算机已经普及,大众对于操作系统的要求更加严格,企业和实验室对操作系统的研究需要从交互性,容错性,安全性等各个方面考虑,这也是操作系统逐渐进步走向智能的道路。但是操作系统的设计一共可以总结为三个大目标:方便,有效,易扩展。

操作系统概述

  如上图,操作系统是连接计算机硬件与用户的桥梁,发展至今其在计算机体系中起着至关重要的作用,我们可以将操作系统视作一个普通的软件,面向普通用户,用户往往不关心计算机硬件,操作系统需要让计算机底层细节对用户透明,提供用户方便的使用体验,包括基本的程序创建,文件管理,I/O控制,内存管理等功能;而对程序员,操作系统需要像程序员隐藏硬件细节,开发通用开发工具、服务、库、接口等。因此操作系统的功能可以列举如下:程序开发,程序运行,I/O设备访问,文件访问控制,系统访问,错误检测和响应,记账。
  对于操作系统的扩展性,有着高度要求,因为操作系统需要不断进步,不断扩展以应对新的服务,新的硬件,或者错误纠正等情况的发生,因此操作系统一般多使用模块化的结构,各个模块组件之间相互配合共同完成工作。

操作系统的发展

串行处理

  最早期的计算机就是利用普通的串行处理完成工作,就是人们把程序一个一个输入进计算机,设定好预计时间,然后让操作系统进行执行,这样的方式有以下两个问题。
  1、调度不合理。如果程序没有在预计时间内运行成功则会强制停止,而如果超预期提前执行完毕,用户也不得不等待预计时间结束才可以放入下一个程序。
  2、准备时间长。这样的串行处理操作系统需要人们自己加载编译器,源程序,加载目标程序进行连接,在此期间需要安装或拆卸磁带,十分麻烦,一旦失败只能重新来过,因此在程序运行的前期准备阶段要花费大量时间。

批处理系统

  批处理操作系统内部使用了一个监控程序,人们将想要执行的程序放入输入设备,监控程序则负责依次自动从输入设备中调入程序进入内存,指挥处理器进行执行,当执行完毕或遇到错误时都会停止当前程序执行,进而调入下一个程序进行执行,执行结果将会放入输出设备。
  监控程序此时充当了操作系统的角色,当调入程序时指挥权暂时交给程序,当执行结束或者出错指挥权将重新换回监控程序。这里指挥权仅仅代表当前情况下处理器从哪个程序中读取代码进行执行。
  批处理系统已经有了些操作系统的雏形,但是此时的操作系统一次只能读入一个程序放入内存,调度模式也只是简单的顺序调入,因此内存管理以及调度方式相对来说十分简单。但是此时的操作系统已经有了现代操作系统的雏形功能。
  1、内存保护。程序读入内存不得访问监控程序的内存区域,如果尝试这样做则将控制权转交监控程序停止当前运行程序,报错。这样的模式类似于如今操作系统的用户态(目态)以及内核态(管态)。用户程序运行在目态,在用户态情况下拥有着对内核态内存的绝对保护,当发生中断、异常、系统调用时系统会从用户态切换为内核态进行系统级处理,可以理解为用户态是普通用户,而内核态则是系统管理员,拥有最高权限。
  2、定时器。当一个程序开始运行时即开始计时,当时间到程序还未运行成功则会报错终止。
  3、特权指令。当程序想要执行一些特殊指令时,例如I/O指令,此时将会发生错误,管理权移交监控程序,由监控程序代替普通程序执行特权指令。当用户想要执行特权指令时只能请求监控程序代替进行执行。这一点十分类似如今操作系统的系统调用库函数的执行方法,也需要由用户态向内核态的切换。

多道批处理操作系统

  上述操作系统同一时间内只能将一个程序读入内存进行执行,但是如果当前程序正在进行I/O操作则处理器只能等待程序I/O结束,因此会有大量的处理器空转时间。那么如果我们可以同时向内存中读入多个程序,在一个程序进行I/O时处理器执行另一个程序岂不是会大大提高处理器利用率。因此多道批处理操作系统诞生了。
  这种可以同时向内存中读入多个程序的处理称为多道程序设计也称为多任务处理,是现代操作系统的主要方案。
  由于多道操作系统需要向内存中读入多个程序因此其对内存的管理,以及作业调度会更加复杂。

分时系统

  分时系统也是多道程序设计的一种,它旨在可以同时完成处理多个交互作业。在这种系统中,多个用户可以通过不同终端登入同一个系统,同时为计算机安排任务,因此可以看作多个用户共享处理器时间,因此称为分时。
  在分时系统中每个用户的程序在很多的时间内交替执行,若不计系统开销则每个用户平均只能得到计算机有效速度的1/n。第一个分时系统是麻省理工学院开发的兼容分时系统(CTSS)。CTSS的工作方式十分简单这里不做过多介绍,但是现代操作系统中的Linux就是典型的分时系统,它允许多个用户通过不同终端连入系统,同时与系统进行交互,但是Windows则不是分时系统。
  分时及多道程序设计引发了操作系统中的许多新问题,例如内存管理,进程保护,权限控制资源分配等。

现代操作系统

特征

  操作系统的设计是一门综合性极高的学科,经过几十年的发展,操作系统主要在以下四个方面有了理论进展:进程,内存管理,信息保护与安全,调度及资源管理。
  在过去数年中操作系统的结构和功能逐步发展,但几年来新一代操作系统引入许多新的设计要素,使得操作系统有了本质的变化,可以分为以下几点。

微内核体系结构

  内核是一个操作系统的核心,它负责完成操作系统内控制管理计算机资源的核心功能,例如进程,调度,内存管理,文件,资源管理等,我们常说的Linux操作系统有很多发行版本,但是他们的内核都是Linux内核,Android操作系统它的内核也是Linux内核不过在其基础上进行了改进和优化使其可以进入移动端。
  内核是一个操作系统的核心,大多数操作系统都是单体内核,及操作系统绝大部分核心功能都由这一个大内核提供,典型情况下这个内核是一个进程。而微内核体系结构只给内核分配一些最基本的功能,例如地址空间,进程间通讯,调度。其他的功能都在用户态运行并和普通程序没有什么区别,因此这些进程可以更具特定需要和环境进行定制,这些进程也被成为服务器。微内核结构的设计分离了内核和服务程序的开发,使得操作系统的结构设计更加简单、灵活,因此多用于分布式操作系统。

分布式操作系统

  在一个分布式系统中,一组独立的计算机展现给用户的是一个统一的整体,就好像是一个系统似的。系统拥
有多种通用的物理和逻辑资源,可以动态的分配任务,分散的物理和逻辑资源通过计算机网络实现信息交换。系统中存在一个以全局的方式管理计算机资源的分布式操作系统。
  分布式操作系统需要在各个独立计算机之间进行信息交互,但是由于在不同的计算机系统中,因此基于处理机之间的通信技术都无法被使用,因此使用分布式消息传递以及远程过程调用来进行信息交互。

多线程

  线程是处理器调度的最小单位,在Linux中可以看作是一个轻量化进程,进程则可以看作是若干个线程的集合。在同一进程的不同线程中共享代码段,数据段,I/O状态信息等,但也有自己独立的部分例如栈,errno,调度优先级。
  多线程对于许多本质上独立不需要串行处理的应用程序很有用,相比多进程其进行调度和切换所造成的开销也会更小。

对称多处理

  对称多处理(SMP),是指在一个计算机体系中有多个处理器,并且内核可以在任何一个处理器上执行,系统也可以调度任何一个进程或线程到任何一个处理器上执行。相比单处理器体系结构,SMP系统可以让多个线程达到并行执行的特点,因此对SMP系统与多线程结合可以大大提高计算机的运行效率。现在的计算机操作系统大部分都是采用对称多处理的体系结构,因为我们现在所使用的处理器一般都拥有多个核心,也就是拥有多个处理器共同为我们工作。
  但是对称多处理的产生也使得操作系统的设计要考虑更多的因素。因为此时操作系统所要管理的绝不仅仅是一个核心。举个例子相比单处理器体系结构对称多处理操作系统可能会面临两个处理器同时调度同一个进程的情况,为了避免这种情况的发生就需要使用更加高级的调度算法进行调度,当然也可能存在多个处理器同时竞争同一资源的情况,而对于内核来说内核也应该设计成可重入的,保证内核可以同时被多个处理器执行。
  而良好的使用多核处理器和多线程可以大大提高计算机工作效率,而其中又有几种可以潜在提高并行方式的方法。我们正在进入一个众核时代。

面向对象设计

  面向对象技术在操作系统开发方面可以是操作系统开发更具模块化,使得程序员可以定制操作系统,而不会破坏操作系统的完整性,典型的Windows就极大程度的采用了面向对象技术进行开发。

Windows

  Windos操作系统起源于微软应用于个人计算机上的MS-DOS操作系统,在1985年改名为Windows,之后通过不断革新到现在已经推出了Windows10的版本,在每一代操作系统的更新背后都是对操作系统内核结构的改变。

体系结构

操作系统概述

  上图显示了Windows8的总体结构。Windows分开了面向应用的软件和操作系统核心软件。在内核组件中包括以下类型:执行体,内核,硬件抽象层,设备驱动,窗口和图形系统,其中执行体包括操作系统核心服务,如I/O管理器,高速缓存管理器,对象管理器,即插即用管理器,电源管理器,安全访问监控程序,虚存管理器,进程/线程管理器,配置管理器,本地过程调用。在用户模式中可以运行4中基本用户模式进程特殊系统进程,服务进程,环境子系统,用户应用程序。

客户-服务器模型

  这种模型广泛用于分布式计算。但是在Windows中也使用了这种模型进行构建,环境子系统和Windows用户模式服务都已通过RPC与客户端进行通信的进程来实现。客户-服务器体系结构的优点可以简化执行体,提高可靠性,灵活性高,为分布式计算提供基础。

线程和SMP

  毫无疑问Windows是典型的支持线程和SMP的操作系统。

Windows对象

  Windows内核使用C进行编写,但是其采用的设计原理却与面向对象设计密切相关,拥有面向对象设计的基本特征。因此我们可以将内核中的任何东西看成对象,执行体中的对象也叫内核对象,只能被内核访问,这体现了面向对象的封装特征,将限制对象的访问进行了应用。

UNIX

早期UNIX系统

操作系统概述

  UNIX由贝尔实验室进行开发,是Multics的微缩版,吸收了其很多思想。无疑UNIX有很多发行版本,其中有商业销售UNIX System Ⅲ
后台这一曹祖西欧i同由进行多次升级变成了UNIX System V。
  早期UNIX操作系统体系结构如上图。它被设计成只能在单易处理器上运行,缺乏保护数据结构免受多个处理器同时访问的能力;它的内核不通用,只支持一种文件系统、进程调度策略和可执行文件格式;传统UNIX内核不可扩展,不能重用代码,内核设计巨大,且不是模块化的。

现代UNIX系统

  随着UNIX的不断进步升级,现代的UNIX内核有着如下所示的结构,其已经逐渐开始向模块化进展。

操作系统概述

  System V Release 4(SVR4)是一个经过几乎完全重写System V的内核后而形成的新版本操作系统,这也是最最重要的UNIX变体。BSD广泛应用于高效,是许多商业UNIX产品的基础,应用最广且文档最好的BSD版本是FreeBSD,常用于互联网的服务器,防火墙和嵌入式系统中。Solaris是基于SVR4的UNIX版本,最新版是10,也是使用最为广泛且最成功的商用UNIX版本。

Linux

  Linux都不陌生,它最初是IBM PC上所应用的一个UNIX变体,它由芬兰的计算机科学专业学生Linus Torvalds编写。Linux成功的一大部分原因在于其由免费软件基金FSF赞助,Linus在开发内核时使用了GNU工具,后来他在GPL下发布了这个内核,因此今天所有的Linux的发行版都是FSF的GNU项目、Linus的个人努力以及全世界各地很多合作者共同开发的产品。

模块结构

  Linux是单体内核,这样的缺点是一大块代码中包含所有的操作系统功能,并作为单个进程运行。这也就使得对操作系统任何部分的修改都要重新连接、重新安装,再重新启动系统,因此任何修改都十分困难,Linux中的这个问题更加尖锐。
  但是尽管Linux是单体的,但由于其特殊的模块结构使得这些模块可用由命令自动加载和卸载,这些相对独立的模块称为可加载模块。Linux的可加载模块是可以动态链接的,并且其也是可堆叠的,按照层次有序排列。例如一个文件系统就是一个模块。

内核组件

操作系统概述

  如图给出了Linux内核的主要组件。所有内核组件都在CPU上执行,其中包含很多内核组件例如信号,系统调用,进程和调度器,虚存,文件系统,网络协议,字符设备驱动,块驱动设备,网络设备驱动,陷阱和错误,物理内存,中断。
  顺带一提Linux是典型的分时多用户操作系统,因此十分适合作为服务器进行使用,方便程序员合作开发,现在绝大部分服务器都是采用Linux作为操作系统,但是由于Linux对于用户的交互体验不是很好(应该说并没有Windows的好),无论是从内核设计还是设计理念来看都是Windows操作起来更加方便因此广泛应用于家用机,如果不是有特殊情况并不建议使用Linux作为家用操作系统。

Android

  Android操作系统广泛应用于触屏移动设备,其也是基于此目的进行设计和开发的,其早期由Android公司开发,该公司随后被Google收购,

软件体系结构

  Android是一个包括操作系统内核、中间件和关键应用的软件栈。其因该算是一种嵌入式Linux,基本框架如图所示。

操作系统概述

系统体系结构

  体系结构如上图所示,在进行开发时,开发者最关心应用及框架,他们通常使用Java进行开发,在这一层有着访问底层服务的API。对于Android系统服务,框架中大部分能够调用系统服务的接口都已经向开发者开放,而系统服务分为两部分,媒体服务以及系统服务。
  对于Android的内核是对原生Linux进行了裁剪,并且针对移动设备提高了内核的功能,可以说Android有着一颗Mini Linux内核。

总结

  综上我们通过操作系统设计目标,设计重点,操作系统发展历史,以及现代操作系统中新加入的设计元素以及常用现代操作系统对操作系统进行了概述,当然这只是粗略了,甚至只能说是大体上进行了了解,本系列会重点对操作系统原理进行进一步梳理和归纳。参考资料及图均来自《操作系统-精髓与设计原理(第八版)》。

【DS】第五章-排序

发表于 2020-01-08 | 分类于 数据结构
字数统计: 3.1k

排序

基本概念

  本章会介绍并且实现,常用的几种排序算法及其思想,但是关于排序除了时间复杂度和空间复杂度这两个衡量算法的基本标准外,还引入了稳定的概念。

稳定

  如果一个排序算法排序结束后,表中相同大小的元素依然可用保持和排序前一样的相对顺序则称该排序是稳定的,反之是不稳定的。
  举个例子,以下这个序列中,出现了相同的元素3,为了便于区分,我将其中一个用红色标记出来。
稳定度

  如果我们进行了某种排序算法将其进行了排序,并且排序结果如下。
稳定度

  我们发现结果中红色的3与黑色的3相比排序前的序列依然保持着黑色在前红色在后的相对顺序,此时我们则称这个排序是稳定的,但是如果排序后有可能会使任意一组相同元素的相对顺序出现了改变,则称其是不稳定的。
  注意稳定度是一个排序的基本性质,一次结果是稳定的不能说排序是稳定的,必须保证每次都是稳定的才可以说这个排序是稳定的,这就需要根据排序的思想来判断其是否稳定。

冒泡排序

  冒泡排序属于交换排序的一种,以升序排序为例,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。这样的过程十分类似于水泡上浮冒泡的过程,所以成为冒泡排序。

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
#include <iostream>
#include <vector>
void BubbleSort(std::vector<int>& arr)
{
int n = arr.size();
bool flag = true;
for(int i = 0; i < n - 1; i++)
{
if(flag == false)
{
break;
}
flag = false;
for(int j = 0; j < n - i - 1; j++)
{
if(arr[j] > arr[j + 1])
{
flag = true;
std::swap(arr[j], arr[j + 1]);
}
}
}
}

int main()
{
std::vector<int> arr = {1, 1, 2, 2, 99, 3, 3, 4, 5, 88, 2};
BubbleSort(arr);
for(const auto& e : arr)
{
std::cout << e << " ";
}
}


1 1 2 2 2 3 3 4 5 88 99

  冒泡排序十分容易理解,但它是一种十分低效的算法,其时间复杂度为ON^2,空间复杂度为O1,但是该算法是稳定的。

直接插入排序

  直接插入排序属于插入排序的一种,插入排序是将序列分为两部分,一部分为已经有序部分,一部分为未有序部分。遍历未有序部分将该部分第一个元素插入到有序序列中的合适位置,遍历完毕则完成了排序。
  但是在实际实现时为了简化操作,具体流程为将未有序部分与有序部分最后一个比较,如果不满足排序要求则交换,继续与倒数第二个元素比较以此类推,直到满足排序顺序为止。

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
#include <iostream>
#include <vector>

void InsertSort(std::vector<int>& arr)
{
if(arr.size() <= 1)
{
return;
}
int n = arr.size();
for(int i = 1; i < n; i++)
{
int j = i - 1;
while(arr[j] > arr[j + 1] && j >= 0)
{
std::swap(arr[j], arr[j + 1]);
j--;
}
}
}
int main()
{
std::vector<int> arr = {1, 1, 99, 23, 32, 2, 2, 4, 5};
InsertSort(arr);
for(const auto& e : arr)
{
std::cout << e << " ";
}
}


1 1 2 2 4 5 23 32 99

  直接插入排序也是十分容易理解的排序,但是同样的效率十分低下,其时间复杂度为ON^2,空间复杂度为O1,但是它同样是稳定的。

选择排序

  选择排序同样是将序列分为两个部分,一个部分为有序部分,一个为无序部分,以升序为例,选择排序每次都从无序部分中选一个最小的放到有序序列的末尾,当无序部分全部变为有序部分则排序结束。

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
#include <iostream>
#include <vector>

void SelectSort(std::vector<int>& arr)
{
int n = arr.size();
for(int i = 0; i < n - 1; i++)
{
int min = i;
for(int j = i + 1; j < n; j++)
{
if(arr[j] < arr[min])
{
min = j;
}
}
if(min != i)
{
std::swap(arr[i], arr[min]);
}
}
}
int main()
{
std::vector<int> arr = {1, 2, 3, 19, 10, 5, 2, 5, 7};
SelectSort(arr);
for(const auto& e : arr)
{
std::cout << e << " ";
}
}


1 2 2 3 5 5 7 10 19

  选择排序也是十分容易理解但是效率较低的排序方式,其时间复杂度为ON^2,空间复杂度为O1,但是它也是稳定的。

希尔排序

  希尔排序是插入排序的升级版本。因为插入排序对于越有序的序列所用排序时间越短,时间复杂度越低的特性,希尔排序旨在使用插入排序使每次排序的序列要么足够短,要么就几乎已经有序,来极大程度节省时间,提高效率。
  希尔排序思想是将序列通过间隔分为若干子序列,对这些子序列先进行排序,每次减小间隔直到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
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>

void InsertSort(int gap, std::vector<int>& arr)
{
int n = arr.size();
for(int i = gap; i < n; i++)
{
for(int j = i - gap; j >= 0; j -= gap)
{
if(arr[j + gap] >= arr[j])
{
break;
}
else
{
std::swap(arr[j + gap], arr[j]);
}
}
}
}
void ShellSort(std::vector<int>& arr)
{
for(int i = arr.size() / 2; i >= 1; i /= 2)
{
InsertSort(i, arr);
}
}
int main()
{
std::vector<int> arr = {1, 2, 10, 3, 4, 7, 2, 9, 3, 4, 99, 5};
ShellSort(arr);
for(const auto& e : arr)
{
std::cout << e << " ";
}
}


1 2 2 3 3 4 4 5 7 9 10 99

  希尔排序是直接插入排序的升级版本,因此它利用自己本身的特性提高了插入排序的效率,平均情况下,它的时间复杂度可用达到ONlogN~ON^2,空间复杂度为O1,但是希尔排序是不稳定的。

堆排序

  堆排序时利用二叉树的顺序结构建成二叉堆,利用堆进行排序的排序算法,算法分为两个部分。
  首先要对序列建堆,建堆思路及从最后一个父结点开始向下调整,直到第一个父结点为止。
  建好堆后将堆顶元素弹出,即将堆顶元素与最后一个元素交换,然后弹出最后一个元素,然后对堆顶进行一次向下调整,此为一次排序,不断重复进行排序,直到堆为空为止,则排序完成。

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
#include <iostream>
#include <vector>

//堆排序最简单的实现方法就是使用STL中的优先级队列
//优先级队列内部自动维护了一个堆,可用很轻松的帮助我们完成堆排序
//但是为了更好的了解算法思想这里我们手动维护这个堆
void AdjustDown(int start, int end, std::vector<int>& arr)
{
int parent = start;
int child = parent * 2 + 1;
while(child < end)
{
if(child + 1 < end && arr[child + 1] > arr[child])
{
child += 1;
}
if(arr[child] <= arr[parent])
{
break;
}
else
{
std::swap(arr[child], arr[parent]);
parent = child;
child = parent * 2 + 1;
}
}
}
void HeapSort(std::vector<int>& arr)
{
//建堆
int n = arr.size();
for(int i = (n / 2 - 1); i >= 0; i--)
{
AdjustDown(i, n, arr);
}
//排序
while(n > 0)
{
std::swap(arr[0], arr[n - 1]);
n--;
AdjustDown(0, n, arr);
}
}
int main()
{
std::vector<int> arr = {1, 4, 5, 3, 4, 22, 33, 5, 2};
HeapSort(arr);
for(const auto& e : arr)
{
std::cout << e << " ";
}
}


1 2 3 4 4 5 5 22 33

  堆排序的效率较高,并且序列越无序则效率越高,它的时间复杂度为ONlogN,空间复杂度为O1,但它是不稳定的。

归并排序

  归并排序的思想是将序列首先拆分成若干不可再分的子序列,然后再将它们一一合并达到有序的效果。

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
#include <iostream>
#include <vector>

//左闭右开区间
void Merge(std::vector<int>& arr, int start, int mid, int end)
{
std::vector<int> arr1, arr2;
for(int i = start; i < mid; i++)
{
arr1.push_back(arr[i]);
}
for(int i = mid; i < end; i++)
{
arr2.push_back(arr[i]);
}
int i = 0, j = 0, k = start;
while(i < arr1.size() && j < arr2.size())
{
if(arr1[i] <= arr2[j])
{
arr[k] = arr1[i];
i++;
k++;
}
else
{
arr[k] = arr2[j];
j++;
k++;
}
}
while(i < arr1.size())
{
arr[k] = arr1[i];
i++;
k++;
}
while(j < arr2.size())
{
arr[k] = arr2[j];
j++;
k++;
}
}
void MergeSort(std::vector<int>& arr, int start, int end)
{
if(end - start > 1)
{
int mid = (start + end) >> 1;
MergeSort(arr, start, mid);
MergeSort(arr, mid, end);
Merge(arr, start, mid, end);
}
}
int main()
{
std::vector<int> arr = {1, 2, 22, 1, 5, 4, 55, 44, 3};
MergeSort(arr, 0, arr.size());
for(const auto& e : arr)
{
std::cout << e << " ";
}
}


1 1 2 3 4 5 22 44 55

  对其进行改进可以写成以下的样子。

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
#include <iostream>
#include <vector>

//左闭右开区间
void Merge(std::vector<int>& arr, int start, int mid, int end)
{
std::vector<int> arr1, arr2;
for(int i = start; i < mid; i++)
{
arr1.push_back(arr[i]);
}
//for(int i = mid; i < end; i++)
//{
// arr2.push_back(arr[i]);
//}
int i = 0, j = mid, k = start;
while(i < arr1.size() && j < end)
{
if(arr1[i] <= arr[j])
{
arr[k] = arr1[i];
i++;
k++;
}
else
{
arr[k] = arr[j];
j++;
k++;
}
}
while(i < arr1.size())
{
arr[k] = arr1[i];
i++;
k++;
}
//while(j < arr2.size())
//{
// arr[k] = arr2[j];
// j++;
// k++;
//}
}
void MergeSort(std::vector<int>& arr, int start, int end)
{
if(end - start > 1)
{
int mid = (start + end) >> 1;
MergeSort(arr, start, mid);
MergeSort(arr, mid, end);
Merge(arr, start, mid, end);
}
}
int main()
{
std::vector<int> arr = {1, 2, 22, 1, 5, 4, 55, 44, 3};
MergeSort(arr, 0, arr.size());
for(const auto& e : arr)
{
std::cout << e << " ";
}
}


1 1 2 3 4 5 22 44 55

  归并排序相比内排序更广泛适用于外排序中,在需要有大量数据进行排序的时候需要使用外排序局部读入内存再进行合并的方式进行排序。它的时间复杂度为ONlogN,空间复杂度为ON,并且它是稳定的。

快速排序

  快速排序是基本排序算法中最快的排序,他和归并算法一样用了分治的思想。它的思路是每次将序列的第一个元素排到合适的位置,使该元素前面的元素都不大于它,后面的元素都不小于它,然后递归整理前面的元素和后面的元素,使所有元素前面的元素都不大于它,后面的元素都不小于它即完成有序。

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
#include <iostream>
#include <vector>

//左闭右开区间
void QuickSort(std::vector<int>& arr, int start, int end)
{
if(end - start <= 1)
{
return;
}
int temp = arr[start];
int ptr1 = start;
int ptr2 = end - 1;
while(ptr1 < ptr2)
{
while(arr[ptr2] >= temp && ptr1 < ptr2)
{
ptr2--;
}
if(ptr1 >= ptr2)
{
break;
}
arr[ptr1] = arr[ptr2];
while(arr[ptr1] <= temp && ptr1 < ptr2)
{
ptr1++;
}
if(ptr1 >= ptr2)
{
break;
}
arr[ptr2] = arr[ptr1];
}
arr[ptr1] = temp;
QuickSort(arr, start, ptr1);
QuickSort(arr, ptr1 + 1, end);
}

int main()
{
std::vector<int> arr = {3, 1, 2, 55, 2, 4, 88, 22, 1, 3};
QuickSort(arr, 0, arr.size());
for(const auto& e : arr)
{
std::cout << e << " ";
}
}


1 1 2 2 3 3 4 22 55 88

  快排使最快的基本排序算法,并且同样的是越有序则排序越快。它的时间复杂度为ONlogN,空间复杂度为OlogN~ON,但它是不稳定的。

【DS】第四章-二叉树

发表于 2019-12-15 | 分类于 数据结构
字数统计: 3.1k

树的概念及结构

什么是树

  树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:每个结点有零个或多 个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结 点可以分为多个不相交的子树。
  下图就是一棵常见的树。

树

树的常用名词

  节点的度:一个节点含有的子树的个数称为该节点的度;
  叶节点或终端节点:度为0的节点称为叶节点;
  非终端节点或分支节点:度不为0的节点;   如上图:D、E、F、G…等节点为分支节点 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;   孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
  兄弟节点:具有相同父节点的节点互称为兄弟节点;
  树的度:一棵树中,最大的节点的度称为树的度;
  节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;   树的高度或深度:树中节点的最大层次;   堂兄弟节点:双亲在同一层的节点互为堂兄弟;
  节点的祖先:从根到该节点所经分支上的所有节点;
  子孙:以某节点为根的子树中任一节点都称为该节点的子孙;   森林:由m(m>=0)棵互不相交的树的集合称为森林;

树的表示

  树的表示相比线性结构就要复杂一些,因为其是层次结构的,其的下一个结点可能有多个,也可能只有一个,因此十分难以在逻辑结构上进行表示。于是伟大的人类提出了一种方法可以很简单的表示任意一棵二叉树,这种表示方法称之为孩子兄弟表示法。
孩子兄弟表示法

  所谓孩子兄弟表示法就是让任何一个结点仅指向它的第一个孩子结点和右边相邻的兄弟结点(如果没有孩子或兄弟指向空),由此任意一棵树上的任何一个节点都可以变成一个度最大仅为2结点,由此我们可以将任何一棵树都变成一棵二叉树。

二叉树

什么是二叉树

  二叉树是一棵所有节点的度最大为2的树。任何一棵树都可以通过孩子兄弟表示法转换为二叉树,因此我们接下来的所有研究都是围绕二叉树进行的。下图就是一棵二叉树。

孩子兄弟表示法

二叉树的特点

  1. 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。
  2. 二叉树的子树有左右之分,其子树的次序不能颠倒。
  3.若二叉树的层次从0开始,则在二叉树的第i层至多有2^i个结点(i>=0)。
  4.高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)。 (空树的高度为-1)
  5.对任何一棵二叉树,如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。

特殊的二叉树

完美二叉树(满二叉树)

  一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。意思是说这棵深度为k的二叉树任意一行的结点都已经是满的了。

完美二叉树法

完全二叉树

  完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。

完全二叉树法

完满二叉树

  所有非叶子结点的度都是2
换句话说就是只要你有孩子,你就必然是有两个孩子。

完满二叉树法

二叉树的存储

顺序存储

  顺序存储指的是利用链表在连续的地址空间上进行存储。但是顺序存储只适用于完全二叉树,因为这样才不会有空间的浪费,所以顺序的存储方式一般用来存储堆。

顺序存储

链式存储

  链式的二叉树存储方式是最为常用的二叉树存储形式,用一个二叉链(或三叉链)的形式来构成二叉树。

二叉链

  如下是一个二叉链的存储形式。

二叉链

  二叉链结构:

1
2
3
4
5
6
struct BinaryTreeNode
{
T _data;
BinaryTreeNode<T>* _left;
BinartTreeNode<T>* _right;
};

三叉链

  如下是一个三叉链的存储形式。

三叉链

  二叉链解雇:

1
2
3
4
5
6
7
8
template<class T>
struct BinaryTreeNode
{
T _data;
BinaryTreeNode<T>* _left;
BinartTreeNode<T>* _right;
BinartTreeNode<T>* _parent;//多了一个指向父亲的指针
};

堆

堆的概念

  堆是典型的通过使用顺序方式存储二叉树来实现的数据结构,因为堆可以保证其必然是一棵完全二叉树。
  如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
  堆有两点性质:
  1、其保证其一定是一棵完全二叉树。
  2、堆中任意一个孩子结点必不大于(大根堆)或者不小于(小根堆)其父结点。
  下图是一个小根堆:

小根堆

  下图是一个大根堆:

大根堆

堆的实现

  堆的实现中有三个基础操作,向上调整,向下调整以及建堆,他们三个共同构成了堆的所有基础操作。STL中的优先级队列底层就是一个堆,所以平时要使用堆的时候我们不必自己写一个,可以借助优先级队列来实现。

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
//T为数据类型,Compare为比较方法,less创建大根堆,greater创建大根堆
template<class T, class Compare>
class Heap
{
public:
Heap()
:_arr()
,_size(0)
{}
Heap(const std::vector<T>& arr)
:_arr(arr)
,_size(arr.size())
{
//根据已有数组建堆
//建堆思路即从最后一个开始进行向下调整,一直向下调整到根
for(int i = (_size - 2) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}
void Pop()
{
//弹出根节点
//思路是将根与最后一个元素交换,然后向下调整,之后弹出最后一个结点
std::swap(_arr[0], _arr[_size - 1]);
_arr.pop_back();
_size--;
AdjustDown(0);
}
void Push(const T& data)
{
_arr.push_back(data);
//新插入元素要向上调整保证依然是一个堆
_size++;
AdjustUp(_size - 1);
}
void Print()
{
for(const auto& e : _arr)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
const T& Top()
{
assert(_size > 0);
return _arr[0];
}
bool Empty()
{
assert(_size > 0);
return _size == 0;
}
size_t Size()
{
return _size;
}
void HeapSort(std::vector<int>& arr)
{
//堆排序的思想即建堆将根持续弹出放到尾部
//升序建大根堆
//降序建小根堆
Heap<T, Compare> tempHeap(_arr);
int tempSize = tempHeap.Size();
arr.resize(tempSize);
while(!tempHeap.Empty())
{
T top = tempHeap.Top();
arr[tempSize - 1] = top;
tempSize--;
tempHeap.Pop();
}
}
private:
//向下调整
//向下调整是堆操作中十分常用的基础操作
//即我们从一个指定结点开始向下调整直到不需要调整为止,
//保证调整过的路径满足堆的要求
void AdjustDown(size_t pos)
{
Compare cmp;
//孩子节点下标为 根节点下标 * 2 + 1 和 根结点下标 * 2 + 2
size_t child = pos * 2 + 1;
while(child < _size)
{
if((child + 1) < _size && cmp(_arr[child], _arr[child + 1]))
{
child += 1;
}
//如果调整了还需要继续向下调整
if(cmp(_arr[pos], _arr[child]))
{
std::swap(_arr[pos], _arr[child]);
}
else
{
break;
}
pos = child;
child = pos * 2 + 1;
}
}
//向上调整与向下调整类似
void AdjustUp(size_t pos)
{
Compare cmp;
//父结点下标为 (孩子结点下表 - 1) / 2
size_t parent = (pos - 1) / 2;
while(pos > 0)
{
//如果调整了需要继续向上迭代调整
if(cmp(_arr[parent], _arr[pos]))
{
std::swap(_arr[parent], _arr[pos]);
}
else
{
break;
}
pos = parent;
parent = (pos - 1) / 2;
}
}
private:
std::vector<T> _arr;
size_t _size;
};

int main()
{
std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7};
Heap<int, std::less<int>> heap(arr);
heap.Print();
heap.Pop();
heap.Print();
std::vector<int> arr2;
heap.HeapSort(arr2);
for(const auto& e : arr2)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << heap.Size() << std::endl;
heap.Push(7);
heap.Print();
}



7 5 6 4 2 1 3
6 5 3 4 2 1
1 2 3 4 5 6
6
7 5 6 4 2 1 3

二叉链实现二叉树

  二叉树的顺序存储代表为堆,那么链式存储典型就是使用二叉链实现二叉树。
  二叉链没什么基础知识了,这里要重点关注的是我们如何在二叉链存储结构下前序,中序,后序以及层序遍历二叉树,这里简单的方法要用到递归。

实现

  直接上代码:

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <queue>

//二叉链结构
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode(const T& data = T())
:_data(data)
,_left(nullptr)
,_right(nullptr)
{}
T _data;
BinaryTreeNode<T>* _left;
BinaryTreeNode<T>* _right;
};

template<class T>
class BinaryTree
{
public:
BinaryTree()
:_head(nullptr)
,_size(0)
{}
BinaryTree(const std::string& preOrder)
{
int i = 0;
_head = CreateByPreOrder(preOrder, i);
}
//前序遍历
void PreOrder()
{
PreOrderCore(_head);
}
//中序遍历
void InOrder()
{
InOrderCore(_head);
}
//后序遍历
void PostOrder()
{
PostOrderCore(_head);
}
//层序遍历
void LevelOrder()
{
std::queue<BinaryTreeNode<T>*> que;
que.push(_head);
while(!que.empty())
{
BinaryTreeNode<T>*temp = que.front();
que.pop();
if(temp == nullptr)
{
std::cout << "#";
}
else
{
std::cout << (char)(temp->_data + 'A');
que.push(temp->_left);
que.push(temp->_right);
}
}
}
//判断是不是一棵完全二叉树
//层序遍历二叉树,遍历到第一个nullptr结点,
//就遍历整个队列,如果全为空则是完全二叉树
//否则就不是
bool IsComplateTree()
{
std::queue<BinaryTreeNode<T>*> que;
que.push(_head);
while(!que.empty())
{
BinaryTreeNode<T>* temp = que.front();
que.pop();
if(temp == nullptr)
{
break;
}
else
{
que.push(temp->_left);
que.push(temp->_right);
}
}
while(!que.empty())
{

BinaryTreeNode<T>* temp = que.front();
que.pop();
if(temp != nullptr)
{
return false;
}
}
return true;
}
private:
void InOrderCore(BinaryTreeNode<T>* root)
{
if(root == nullptr)
{
std::cout << "#";
return;
}
InOrderCore(root->_left);
std::cout << (char)(root->_data + 'A');
InOrderCore(root->_right);
}
void PreOrderCore(BinaryTreeNode<T>* root)
{
if(root == nullptr)
{
std::cout << "#";
return;
}
std::cout << (char)('A' + root->_data);
PreOrderCore(root->_left);
PreOrderCore(root->_right);
}
void PostOrderCore(BinaryTreeNode<T>* root)
{
if(root == nullptr)
{
std::cout << "#";
return;
}
PostOrderCore(root->_left);
PostOrderCore(root->_right);
std::cout << (char)('A' + root->_data);
}
BinaryTreeNode<T>* CreateByPreOrder(const std::string& preOrder, int& i)
{
if(preOrder[i] != '#')
{
BinaryTreeNode<T>* root = new BinaryTreeNode<T>(preOrder[i] - 'A');
root->_left = CreateByPreOrder(preOrder, ++i);
root->_right = CreateByPreOrder(preOrder, ++i);
return root;
}
else
{
return nullptr;
}
}
private:
BinaryTreeNode<T>* _head; //与链表一样存储一个头结点即可
size_t _size; //节点个数
};


int main()
{
BinaryTree<int> tree("ABD##E##CF##G##");
tree.PreOrder();
std::cout << std::endl;
tree.InOrder();
std::cout << std::endl;
tree.PostOrder();
std::cout << std::endl;
tree.LevelOrder();
std::cout << std::endl;
std::cout << "Is Complate Tree: " << tree.IsComplateTree() << std::endl;;
}

【DS】第三章-栈和队列

发表于 2019-12-14 | 分类于 数据结构
字数统计: 1.7k

第三章 栈和队列

栈

栈的特性

  栈是一种线性结构,这种特殊的线性结构有着最大的特点——后进先出(Last In First Out)。最后压入栈的元素会最先被弹出。
  由于栈只用在同一端进行插入和删除,因此我们优先选择使用顺序表,因为在顺序表的末尾插入和删除的时间复杂度都是O(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
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
#include <iostream>
#include <assert.h>
template<class T>
class Stack
{
public:
//构造函数
Stack()
:_stack(nullptr)
,_size(0)
,_capacity(0)
{
}
//析构函数
~Stack()
{
if(_stack != nullptr)
{
delete[] _stack;
}
}
//入栈
void Push(const T& temp)
{
//尾插
//容量检查
if(_size == _capacity)//满了
{
size_t newCapacity = (_capacity == 0 ? 5 : 2 * _capacity);
T* stackTemp = new T[newCapacity];
for(int i = 0; i < _size; i++)
{
stackTemp[i] = _stack[i];
}
//delete空指针是完全安全的
delete[] _stack;
_stack = stackTemp;
_capacity = newCapacity;
std::cout << "Expend new capacity:" << _capacity << std::endl;
}
_stack[_size] = temp;
_size++;
}
//出栈
void Pop()
{
if(_size <= 0)
{
return;
}
_size--;
}
//栈顶元素
const T& Top()
{
assert(_size > 0);
return _stack[_size - 1];
}
//元素个数
size_t Size()
{
return _size;
}
//是否为空
bool IsEmpty()
{
return (_size <= 0 ? true : false);
}
private:
T* _stack;//顺序表
size_t _size;//长度
size_t _capacity;//容量
};

如何判断一个序列是否为出栈序列

  一个入栈序列有很多种出栈顺序,例如入栈1 2 3 4 5,他的出栈序列可以是5 4 3 2 1也可也是3 2 1 4 5,那么如何判断一个序列是否是一个入栈序列的出栈序列呢?
  这道题的思路很简单,我们需要利用一个栈和两个分别指向入栈序列和出栈序列的指针。当栈为空或栈顶元素不等于当前出栈序列指针所指元素时,将入栈序列指针所指元素压入栈,并且入栈序列指针后移;如果相同则将栈顶元素弹出并将出栈序列指针后移。如果在演算过程中还需要向栈中压入元素而入栈序列已经被全部遍历指针指向队尾则可以怕判断当前序列不是入栈序列的出栈序列;如果可以同时遍历完入栈序列和出栈序列并且栈为空则当前序列时一个入栈序列的出栈序列。

https://misakifx.github.io/2019/10/25/%E3%80%90DS%E3%80%91%E6%A0%88%E7%9A%84%E5%8E%8B%E5%85%A5%E3%80%81%E5%BC%B9%E5%87%BA%E5%BA%8F%E5%88%97/

  

栈的应用

  栈有以下几种应用:判断括号匹配,后缀表达式,迷宫的暴力破解法等。

队列

队列的特点

  队列也是一种线性结构,这种线性结构的特点为先进先出(First in First out)。由于队列需要在队列两端进行插入或删除,因此我们优先选择链表来进行实现。当然使用数组实现也可以,只是数组在头部插入和删除元素需要ON的时间复杂度,因此选择链表更优。

实现

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
#include <iostream>
#include <assert.h>
template<class T>
struct QueueNode
{
QueueNode()
:_data(T())
,_next(nullptr)
{}
QueueNode(const T& data, QueueNode* next)
:_data(data)
,_next(next)
{}
T _data;
QueueNode* _next;
};

//用单向带头不循环链表实现队列
template<class T>
class Queue
{
public:
Queue()
:_head(nullptr)
,_rear(nullptr)
,_size(0)
{
_head = new QueueNode<T>;
_rear = _head;
}
~Queue()
{
while(!Empty())
{
Pop();
}
delete _head;
_head = nullptr;
_rear = nullptr;
}
void Push(const T& data)
{
QueueNode<T>* newNode = new QueueNode<T>(data, nullptr);
_rear->_next = newNode;
_rear = newNode;
_size++;
}
bool Empty()
{
return _rear == _head;
}
void Pop()
{
QueueNode<T>* temp = _head->_next;
_head->_next = _head->_next->_next;
//队列中只有一个元素
if(temp == _rear)
{
_rear = _head;
}
delete temp;
temp = nullptr;
_size--;
}
const T& Front()
{
assert(_head->_next != nullptr);
return _head->_next->_data;
}
const T& Back()
{
assert(_rear != _head);
return _rear->_data;
}
size_t Size()
{
return _size;
}
private:
QueueNode<T>* _head; //指向头部结点
QueueNode<T>* _rear; //指向最后一个元素
size_t _size;
};

int main()
{
Queue<int> que;
que.Push(1);
que.Push(2);
que.Push(3);
que.Push(4);
while(!que.Empty())
{
std::cout << "size = " << que.Size() << std::endl;
std::cout << que.Front() << std::endl;
que.Pop();
}
}



size = 4
1
size = 3
2
size = 2
3
size = 1
4

  以上代码完成了队列的基本功能。

环形队列

环形队列实现思路

  环形队列是一种特殊的队列,队列依然保证先进先出的特点,但是在逻辑结构上队列呈一个环状,可以保证在给定的有限空间内利用数组实现操作达到O1的队列。其需要用到两个指针,一个指针head指向向队头,一个指针rear指向队尾的后一个位置用来标记当前队列空间的使用情况,如果队满则禁止继续插入。
  当插入元素时,将元素插入到队尾指针指向的位置,然后将rear指针后移;当弹出元素时只需将head指针后移即可。但是要注意由于是环形队列,因此当两个指针走到数组末尾时需要做特殊处理让他们重新指回到数组头部。
  但是环形队列两个指针的位置都是不固定的,我们又该如何判断队满和队空以及计算数组元素呢?

环形队列

实现

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
#include <iostream>
#include <assert.h>

template<class T>
class CircleQueue
{
public:
CircleQueue(size_t capacity)
:_arr(nullptr)
,_head(0)
,_rear(0)
,_capacity(capacity)
{
assert(capacity >= 2);
_arr = new T[_capacity];
}
~CircleQueue()
{
delete _arr;
_arr = nullptr;
}
//判断满
bool IsFull()
{
if((_rear + 1) % _capacity == _head)
{
return true;
}
return false;
}
///判断空
bool IsEmpty()
{
if(_head == _rear)
{
return true;
}
return false;
}
bool Push(const T& data)
{
if(IsFull())
{
return false;
}
_arr[_rear] = data;
_rear = (_rear + 1) % _capacity;
return true;
}
bool Pop()
{
if(IsEmpty())
{
return false;
}
_head = (_head + 1) % _capacity;
return true;
}
const T& Front()
{
assert(!IsEmpty());
return _arr[_head];
}
const T& Back()
{
assert(!IsEmpty());
size_t temp = (_rear + _capacity - 1) % _capacity;
return _arr[temp];
}
size_t Capacity()
{
return _capacity;
}
size_t Size()
{
return (_rear + _capacity - _head) % _capacity;
}
private:
T* _arr; //存储环形队列的数组
size_t _head; //指向队头
size_t _rear; //指向队尾
size_t _capacity; //环形队列的总容量,一旦确定不可再改变
};

int main()
{
CircleQueue<int> circleQueue(5);
circleQueue.Push(1);
circleQueue.Push(2);
circleQueue.Push(3);
circleQueue.Push(4);
circleQueue.Push(5);
while(!circleQueue.IsEmpty())
{
std::cout << "size = " << circleQueue.Size() << std::endl;
std::cout << circleQueue.Front() << std::endl;
circleQueue.Pop();
}
//std::cout << circleQueue.Front() << std::endl;
}


size = 4
1
size = 3
2
size = 2
3
size = 1
4

  以上实现了环形队列的基本功能。

【项目】文章相似度检索工具

发表于 2019-12-02 | 分类于 项目
字数统计: 2.2k

文章相似度检索工具

开发环境

  基于Windows操作系统,使用vs进行开发。

项目介绍

功能介绍

  本项目实现的是一个根据词频获取两篇文章相似度的工具。文本相似度检索经常使用在文本聚类,文本分类,文本挖掘,信息检索上,像是常见的论文查重工具也都是基于文本相似度进行检索分析的。
  本项目分别利用相对词频,tf-idf计算两篇文章的相似度,计算结果较为可靠。

检索原理

  基于词频进行文本相似度的检索需要统计词频,构建词频特征向量,利用特征向量夹角余弦来表示文本相似度。步骤可以概括为:分词->统计词频->词频向量->相似度计算。
  分词是中文检索要加上的特殊的环节,中文不像英文词之间有空格作为间隔,中文是连贯的,为了词频统计我们需要将其按照语义进行分词。
  分词的原理也较为复杂,这里给出一篇讲解分词原理的博客。
https://www.cnblogs.com/BaiYiShaoNian/p/5071802.html
  接下来统计词频。但在统计次品的时候要注意不计算停用词的词频。停用词是指没有什么实际含义的词,例如:数字,标点,代词,语气助词,副词,介词,连接词等。我们要先去除文章中的停用词,再统计词频。词频即为单词在文章中出现的次数,词频越大一般可认为该词越重要。
  构建词频向量需要对词进行编码,确定统计出来的向量的每一维都该表示相同的词的词频,这样构建出来的向量才有意义。把两个文本中的所有有效词全部编码,对于长文本可以按词频从大到小排序,取前n个关键词,再按照编码构建词频向量。
  最后计算向量相似度。这里可以使用欧几里得距离,余弦相似度,曼哈顿距离等来计算。我这里通过余弦相似度来进行计算。公式为:cos(θ) = (A * B) / (||A|| * ||B||)。
  计算文本相似度过程举例:

1
2
文本1:今天有事,没办法去学校上课了。
文本2:真想去学校上课,但是今天有事,去不了学校了。

  分词后:

1
2
文本1:今天/有事/,/没办法/去/学校/上课/了。
文本2:真想/去/学校/上课/,/但是/今天/有事/,/去不了/学校/了。

  去掉停用词后统计有效词的词频:

1
2
文本1:有事:1,没办法:1,去:1,学校:1,上课:1
文本2:真想:1,去:1,学校:2,上课:1,有事:1,去不了:1

  提取所有有效词:

1
学校,去,真想,上课,有事,去不了,没办法

  对有效词进行编码:

1
学校:0,去:1,真想:2,上课:3,有事:4,去不了:5,没办法:6

  根据编码构建两个文本的词频向量:

1
2
3
4
文档1的词频:{[0 : 1], [1 : 1], [2, 0], [3 : 1], [4 : 1], [5 : 0], [6 : 1]}
文档2的词频:{[0 : 2], [1 : 1], [2 : 1], [3 : 1], [4 : 1], [5 : 1], [6 : 0]}
文档1词频向量:{1, 1, 0, 1, 1, 0, 1}
文档2词频向量:{2, 1, 1, 1, 1, 1, 0}

  最后计算向量相似度即可。

功能模块

分词模块

  分词模块主要利用github上的开源工具结巴分词完成分词工作,其可以将文本内容按照词义分成词组放到vector中。但是要注意结巴分词只支持UTF8编码,而Windows上默认使用GBK编码因此中间我们要想对读取到的文本进行一次转码操作。

词频获取模块

  词频获取即遍历分词后的vector统计词语出现次数即可,注意这里还要过滤掉没有用的停用词。但是这样统计出的词频知识绝对词频,在两篇长度差距较大的文章中可信度角度,因此在这个模块中我将绝对词频 / 总词数 = 相对词频得出相对词频,相对词频可以提高词频可靠性。同时为了进一步提高可靠度我利用tf-idf算法二次统计词频。tf-idf = tf * idf,其中idf为逆文档率,它表示每一个词重要性的权重,一个词越少见它的值越大,反之越小。这样的词频统计方法是经过大数据分析后的产物,因此可靠程度更高。

排序编码模块

  要获取词频向量要先对其进行编码,但是我们不能将文章中所有此都作为编码构建向量,因为那样的向量太长了且没有针对性,因此我选择对两篇文章中出现频率最高的前n个词进行提取,最后根据去重后的n个词进行编码再构建词频向量。
  这里需要先对每篇文章中统计好的词频根据词频大小进行排序,得出前n个出现频率最高的词,再将其放到一个容器中进行去重,去重我们可以选择使用set容器,去重后set中词就是我们需要构建词频向量的码值。

构建词频向量及计算相似度模块

  对两种的两种词频分别构建好码值后,对两篇文章依次利用码值和统计好的词频构建词频向量,构建好词频向量后分别计算两种词频向量的余弦相似度,得出结果。

文件配置模块

  检索工具有两种使用模式,我们可以在命令行通过参数直接给入字典位置,两个文章路径直接使用,也可以通过编写配置文件的方式进行使用,配置文件的路径需要在参数中提交。
  配置文件中可以配置两篇文章获取码值的大小,字典路径,文件路径等。

项目效果预览

  文章相似度检索。

相似度检索

相似度检索

相似度检索

项目中遇到的问题

编码转换

  在使用分词工具时发现分词工具无法达到满意的效果,无法将词合理的提取,在网上看了官方说明后发现其仅支持UTF8编码,而Windows默认GBK编码,因此其之间必须进行转码才能协同工作。而转码工作需要用的系统函数,并不能直接从GBK转换至UTF8,需要用宽字符也就是UTF16作为桥梁才能进行转换。转码的编写让我了解了Windows下转码的接口以及宽字符和多字节编码转换的应用。

相对词频

  一开始项目利用绝对词频作为词频统计,但是发现如果两篇文章长度有极大差别的情况下,相似度的计算并不准确,于是我考虑计算出相对词频作为依据再进行统计。
  为了进一步提高准确率我又在网上学习了idf逆文档率的作用,从而通过相对词频和tf-idf两种依据计算文章相似度,提高准确率。

项目扩展方向

文章查重

  目前工具仅可以比较两篇文章之间的相似度,而在实际应用中我们往往要比较多篇文章之间的相似度,例如在文章查重的使用上。接下来项目可以进一步扩展为可以查取多篇文章之间的重复度,并且反馈给用户,为了查取效率我们可以开启多线程进行并行查取。在查重后我们还可以显示相似度较高的几组文章,对用户进行提醒,也可以筛选出相似度最高的两篇文章。

文章归纳

  对所给文章依次比较得出相似度,相似度较高的文章可以归纳为一类文章,同时我们还可以通过idf得出文章的关键字,以此为依据对文章进行归纳整理,从而可以将其扩展为一个文章归纳工具。

项目发布

  GitHub:https://github.com/MisakiFx/ASS-Tool

【Cpp】第十九章-Cpp11新特性

发表于 2019-11-10 | 分类于 Cpp
字数统计: 4.7k

Cpp11新特性

  Cpp11中新增了很多新的语法,很多之前我们都已经有介绍过

初始化列表

如何使用

  在Cpp11中允许使用初始化列表初始化任何类型,不论是内置类型还是自定义类型都可以使用初始化列表进行初始化,而在Cpp98的版本中是不能初始化自定义类型的。

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
#include <iostream>
#include <vector>
class Test
{
public:
Test(int a, int b)
:_a(a)
,_b(b)
{
}
void Print()
{
std::cout << _a << " " << _b << std::endl;
}
private:
int _a;
int _b;
};
int main()
{
//内置类型的初始化列表初始化
int a = {10};
int b = {3 + 4};
std::cout << a << " " << b << std::endl;
int arr[] = {1, 2, 3, 4};
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
std::cout << arr[i] << " ";
}
std::cout << std::endl;
//自定义类型初始化列表初始化
std::vector<int> arr2 = {4, 3, 2, 1};
for(auto e : arr2)
{
std::cout << e << " ";
}
std::cout << std::endl;
Test test = {7, 8};
test.Print();
}



10 7
1 2 3 4
4 3 2 1
7 8

initializer_list

  但是自定义类型想要支持像vector这样的初始化列表并不是天然就支持的,而是在Cpp11中新增了一个容器叫initializer_list,初始化列表,借助这个容器我们可以实现vector这样的初始化。

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 <iostream>
#include <vector>
class Test
{
public:
Test(int a, int b)
:_a(a)
,_b(b)
{
}
void Print()
{
std::cout << _a << " " << _b << std::endl;
}
private:
int _a;
int _b;
};
template<class T>
class Vector
{
public:
Vector(size_t n = 0)
:_start(new T[n])
,_finish(_start + n)
,_endOfStorge(_start + n)
{
}
//我们想要使用初始化列表初始化vector多亏下面这样的构造函数
Vector(const std::initializer_list<T>& list)//初始化列表容器
:_start(new T[list.size()])
,_finish(_start + list.size())
,_endOfStorge(_start + list.size())
{
//std::initializer_list容器有三个公有接口,start(), end()提供遍历,size()提供大小
int index = 0;
for(auto e : list)
{
_start[index] = e;
index++;
}
}
void Print()
{
T* start = _start;
while(start != _finish)
{
std::cout << *start << " ";
start++;
}
std::cout << std::endl;
}
private:
T* _start;
T* _finish;
T* _endOfStorge;
};
int main()
{
Vector<int> vec = {1, 2, 3, 4, 5};
vec.Print();
}


1 2 3 4 5

  因此如果我们在自己今后写自定义类型时,想要在初始化时利用初始化列表进行不定长参数的初始化时,就可以借助initializer_list来实现。
  如果我们想让一个自定义类型不再支持初始化列表进行初始化我们也可以通过加explicit关键字来禁用。

变量类型推导

  变量类型推导其中的典型代表就是我们一直在使用的auto关键字,它可以帮助我们简化代码书写,一些很复杂的类型一个auto即可代替,但是auto是编译时类型识别,除此之外还有一个关键字这里要提一下,即decltype,这个关键字我们之前并没有使用过,不过这个关键字是RTTI的,它可以在运行时进行类型识别。
  auto和decltype之间最显著的差别就是,auto在编译时就将变量类型确定下来,因此如果我们声明一个变量而不去定义它那么编译器此时就无法识别它的变量类型,因此这是不合法的书写方式,但是decltype却有办法去识别类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

int fun()
{
return 10;
}
int main()
{
//auto a;//这是不合法的,因为编译器此时无法判断它的类型
decltype(3 + 1) b;//decltype可以通过推导括号中表达式的类型来定义变量
std::cout << typeid(b).name() << std::endl;//typeid可以识别变量类型,它也以RTTI的思想来实现的
decltype(fun()) c;
std::cout << typeid(c).name() << std::endl;//typeid可以识别变量类型,它也以RTTI的思想来实现的
}


i
i

委派构造函数

  委派构造函数即在一个类的构造函数中可以调用这个类的其它构造函数。Cpp11之前是不允许这样的语法的,但是在Cpp11中加入了这样的新特性,但是却也带来了问题,就像是下面这样的情况。

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>

class A
{
public:
A()
:A(10, 20)//无参构造中调用带参构造
{

}
A(int a, int b)
:A()//带参构造中调用无参构造
{
_a = a;
_b = b;
}
private:
int _a;
int _b;
};
int main()
{
A a;
std::cout << "finish" << std::endl;//这里调用就会出现死递归调用,从而崩掉
}


崩溃

默认函数控制

  默认函数控制可以帮助我们很好的管理一个类中的默认成员函数,控制其是否应该自动生成。我们之前想要禁用拷贝构造,赋值运算符重载往往是将他们的声明放在private中,但是在Cpp11中我们可以这样写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

class A
{
public:
A(int a)
:_a(a)
{
}
A(const A& a) = delete;
A& operator=(const A& a) = delete;
private:
int _a;
};
int main()
{
A a(1);
//A b(a);//禁用拷贝
}

  同时我们也可也让编译器自动帮我们生成默认构造函数。

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

class A
{
public:
A(int a)
:_a(a)
{
}
A() = default;//生成默认构造
A(const A& a) = delete;
A& operator=(const A& a) = delete;
private:
int _a;
};
int main()
{
A a(1);
A b;//合法
//A b(a);//禁用拷贝
}

右值引用

左值和右值

  什么是右值呢?在C语言中就有左值和右值的概念,这里简单总结下可以理解为:
  1、左值就是可以出现在复制运算符左右两边的值,左值往往是可以取地址的。
  2、右值就是只可以出现在赋值运算符右边的值,右值往往不可以取地址。
  常见的右值有常量,临时变量和将亡值(即将销毁的值)。

左值引用和右值引用

  我们之前所使用的引用都是左值引用,左值引用既可以引用左值,也可也引用右值,因为我们可以使用指向常量的引用去引用常量,例如const int& ra = 10;这条语句是合法的。
  而右值引用只可以引用右值。例如int&& rra = 10;,此时不需要加const就可以直接引用右值,这就是一条典型的右值引用。,当然右值引用也可也引用临时变量和将亡值。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

int fun(int a)
{
return a;
}
int main()
{
int a = 10;
fun(a);
const int & ra = fun(a);//这里fun(a)返回的是一个临时变量,我们不可以直接使用引用指向它,但是左值引用加上const就可以指向右值
int&& rra = fun(a);//但是我们如果使用右值引用就可以直接引用临时变量
}

移动语义

  如果我想要右值引用去引用左值可以么?在Cpp中移动语义可以帮助我们完成将一个左值变为右值,从而可以让右值引用去引用它。我们可以通过调用std::move()完成移动语义。

1
2
3
4
5
6
7
8
#include <iostream>

int main()
{
int a = 10;
int && ra = std::move(a);//移动语义,将左值改为右值
const int& rra = std::move(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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <string.h>

//实现一个简单的string类
class String
{
friend std::ostream& operator<<(std::ostream& out, const String& str);
public:
String(const char* str = "")
:_str(new char[strlen(str) + 1])
{
strcpy(_str, str);
std::cout << "String(char* str = )" << std::endl;
}
String(const String& s)
:_str(new char[strlen(s._str) + 1])
{
strcpy(_str, s._str);
std::cout << "String(const String& s)" << std::endl;
}
String& operator=(const String& s)
{
if (this != &s)
{
char* temp = _str;
_str = new char[strlen(s._str) + 1];
strcpy(_str, s._str);
delete[] temp;
}
return *this;
}
~String()
{
delete[] _str;
}
private:
char* _str;
};
std::ostream& operator<<(std::ostream& out, const String& str)
{
out << str._str;
return out;
}
String getString(const char* str)
{
String temp(str);
return temp;
}
void test()
{
String str = getString("Misaki");
std::cout << str << std::endl;
}
int main()
{
test();
}


String(char* str = )
String(const String& s)
Misaki

  这个例子中细心的同学会发现,在这个例子中其实会生成三个对象。首先有参构造一个,然后由于我们的函数返回值返回对象,于是拷贝构造临时对象,然后再用临时对象拷贝构造最终我们需要的str对象,于是会发生依次构造,两次拷贝构造,但是由于编译器的优化会帮我们减少为一次构造一次拷贝构造(如果是更厉害的编译器会直接优化成一次构造,比如MinGW,为此为了演示我换上了vs),但是仍然有多余的损耗,因为我们为了构造str而构造了temp,temp构造后是一个将亡值,随后很快会进行释放,紧接着我们用它构造str又开辟了新的空间,为了构造str我们先释放了temp的空间又重新为str开辟了空间,尽管他们空间中的内容应该是一样的。所以这是多次一举的行为,十分低效。
  那么有没有一种办法可以让我们的str直接利用temp开辟好的空间,而不再多此一举自己重新开辟空间呢?这样的做法明显是更加高效的,答案是有的。在Cpp11中由于右值引用的出现,于是出现了移动构造,即利用右值引用进行构造。这里右值引用的多是一个将亡值,即即将释放资源的值,既然他们的资源即将要释放,而我们构造新对象所需要的资源刚好和他们要释放的资源一样,那不如直接把他们的资源拿来用。

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
#include <iostream>
#include <string.h>

//实现一个简单的string类
class String
{
friend std::ostream& operator<<(std::ostream& out, const String& str);
public:
String(const char* str = "")
:_str(new char[strlen(str) + 1])
{
strcpy(_str, str);
std::cout << "String(char* str = )" << std::endl;
}
String(const String& s)
:_str(new char[strlen(s._str) + 1])
{
strcpy(_str, s._str);
std::cout << "String(const String& s)" << std::endl;
}
//移动构造
String(String&& s)
:_str(s._str)
{
s._str = nullptr;//这里一定要记着将将亡值的原本指针置空,否则会把我们拿来用的资源释放了
std::cout << "String(String&& s)" << std::endl;
}
String& operator=(const String& s)
{
if (this != &s)
{
char* temp = _str;
_str = new char[strlen(s._str) + 1];
strcpy(_str, s._str);
delete[] temp;
}
return *this;
}
~String()
{
delete[] _str;
}
private:
char* _str;
};
std::ostream& operator<<(std::ostream& out, const String& str)
{
out << str._str;
return out;
}
String getString(const char* str)
{
String temp(str);
return temp;
}
void test()
{
String str = getString("Misaki");
std::cout << str << std::endl;
}
int main()
{
test();
}


String(char* str = )
String(String&& s)
Misaki

  这里编译器判断temp是一个右值,自动调用了移动构造,移动构造中所做的事情就是将即将释放的资源直接拿来给新创建的对象使用,于是省掉了一次先释放空间再申请空间的过程。移动构造可以提升代码效率,减少拷贝。

移动赋值

  有移动构造就有移动赋值。

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
#include <iostream>
#include <string.h>

//实现一个简单的string类
class String
{
friend std::ostream& operator<<(std::ostream& out, const String& str);
public:
String(const char* str = "")
:_str(new char[strlen(str) + 1])
{
strcpy(_str, str);
std::cout << "String(char* str = )" << std::endl;
}
String(const String& s)
:_str(new char[strlen(s._str) + 1])
{
strcpy(_str, s._str);
std::cout << "String(const String& s)" << std::endl;
}
//移动构造
String(String&& s)
:_str(s._str)
{
s._str = nullptr;//这里一定要记着将将亡值的原本指针置空,否则会把我们拿来用的资源释放了
std::cout << "String(String&& s)" << std::endl;
}
String& operator=(const String& s)
{
if (this != &s)
{
char* temp = _str;
_str = new char[strlen(s._str) + 1];
strcpy(_str, s._str);
delete[] temp;
}
return *this;
}
//移动赋值
String& operator=(String&& s)
{
if (this != &s)
{
char* temp = _str;
_str = s._str;
s._str = temp;
std::cout << "String& operator=(String&&)" << std::endl;
}
return *this;
}
~String()
{
delete[] _str;
}
private:
char* _str;
};
std::ostream& operator<<(std::ostream& out, const String& str)
{
out << str._str;
return out;
}
String getString(const char* str)
{
String temp(str);
return temp;
}
void test()
{
String str = getString("Misaki");
str = String("misaki");
std::cout << str << std::endl;
}
int main()
{
test();
}


String(char* str = )
String(String&& s)
String(char* str = )
String& operator=(String&&)
misaki

  我们在写移动构造和移动赋值的时候要注意如果一个类中有自定义类型成员,我们也应该让他们进行移动构造或移动赋值,可以通过移动语义将内部成员从左值转换为右值从而调用他们的移动构造或移动赋值。

完美转发

  我们看下面一段代码。

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>

void Fun(int& x)
{
std::cout << "lvalue ref" << std::endl;
}
void Fun(const int& x)
{
std::cout << "const lvalue ref" << std::endl;
}
void Fun(int&& x)
{
std::cout << "rvalue ref" << std::endl;
}
void Fun(const int&& x)
{
std::cout << "const rvalue ref" << std::endl;
}
template<class T>
void PerfectForward(T t)
{
Fun(t);
}
int main()
{
PerfectForward(10);//rvalue ref
int a = 10;
PerfectForward(a);//lvalue refj
PerfectForward(std::move(a));//rvalue ref
const int b = 8;
PerfectForward(b);//const lvalue ref
PerfectForward(std::move(b));//const rvalue ref
}


lvalue ref
lvalue ref
lvalue ref
lvalue ref
lvalue ref

  我们明明传入了不同的类型进入函数模板,本应该产生不同的结果,为什么进到函数模板中就全部变成了左值引用呢?
  这里就是在我们把值传递进函数模板时编译器会将所有值的属性全部更改为左值。那么有没有办法让值在传递过程中属性不发生改变呢?这里就要用到完美转发,来让值的属性不变。在使用完美转发之前我们还要直到一点,在模板中,自定义类型加&&表示未定义类型,表示传入模板的是什么类型参数,此时就使用什么类型的参数,例如下面这样。

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>

void Fun(int& x)
{
std::cout << "lvalue ref" << std::endl;
}
void Fun(const int& x)
{
std::cout << "const lvalue ref" << std::endl;
}
void Fun(int&& x)
{
std::cout << "rvalue ref" << std::endl;
}
void Fun(const int&& x)
{
std::cout << "const rvalue ref" << std::endl;
}
template<class T>
void PerfectForward(T&& t)//在模板中这里不是右值引用,代表未定义类型
{
Fun(t);
}
int main()
{
PerfectForward(10);//rvalue ref
int a = 10;
PerfectForward(a);//lvalue refj
PerfectForward(std::move(a));//rvalue ref
const int b = 8;
PerfectForward(b);//const lvalue ref
PerfectForward(std::move(b));//const rvalue ref
}


lvalue ref
lvalue ref
lvalue ref
const lvalue ref
const lvalue ref

  但是至此结果还是不对,于是我们再加上完美转发。

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>

void Fun(int& x)
{
std::cout << "lvalue ref" << std::endl;
}
void Fun(const int& x)
{
std::cout << "const lvalue ref" << std::endl;
}
void Fun(int&& x)
{
std::cout << "rvalue ref" << std::endl;
}
void Fun(const int&& x)
{
std::cout << "const rvalue ref" << std::endl;
}
template<class T>
void PerfectForward(T&& t)//在模板中这里不是右值引用,代表未定义类型
{
Fun(std::forward<T>(t));
}
int main()
{
PerfectForward(10);//rvalue ref
int a = 10;
PerfectForward(a);//lvalue refj
PerfectForward(std::move(a));//rvalue ref
const int b = 8;
PerfectForward(b);//const lvalue ref
PerfectForward(std::move(b));//const rvalue ref
}


rvalue ref
lvalue ref
rvalue ref
const lvalue ref
const rvalue ref

  至此结果就正确了,完美转发可以帮助我们保证值在参数传递过程中属性不会改变。

lambda表达式

  lambda表达式是为了方便我们传入回调函数的语法。之前我们在传入回调函数时往往是利用仿函数,传入一个对象,随后在方法内通过调用对象的operator()来回调函数,但是在Cpp11中为了更加方便我们书写回调函数,加入了lambda表达式。

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
#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
std::vector<int> arr = {1, 10, 3, 4, 5, 2, 5, 7};
std::sort(arr.begin(), arr.end(), std::less<int>());//通过仿函数的方式传入,从小到大排序
for(auto e : arr)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::sort(arr.begin(), arr.end(), //lambda表达式传入
[](int a, int b)->bool
{
return a > b;
}
);
for(auto e : arr)
{
std::cout << e << " ";
}
std::cout << std::endl;
}



1 2 3 4 5 5 7 10
10 7 5 5 4 3 2 1

  lambda表达式就是一个匿名函数,可以分为以下几个部分:

1
2
3
4
[]:捕捉列表
():参数列表
->:返回值
{}:函数体

  捕捉列表或许是比较特殊的一个部分,我们可以通过它来捕捉外层作用域内的变量。[=]表示以值得形式捕捉外部作用域内所有变量;[a, b]表示以值的形式捕捉a,b变量;[&]表示以引用的形式获取外部所有变量;[this]表示获取成员变量的this指针,只能在成员函数内部使用。捕捉到的变量可以直接在函数内部使用。
  我们默认从外部捕捉的变量都是const的,不可修改,要想修改外部捕获进来的值,需要在参数列表后面加mutable关键字。
  lambda表达式的返回值和参数部分都可以省略掉,因此[]{}也可以看作是一个lambda表达式。

【Cpp】第十八章-空间配置器

发表于 2019-11-06 | 分类于 Cpp
字数统计: 1.5k

空间配置器

什么是空间配置器

  空间配置器是为各个容器高效管理空间的工具,负责空间的申请与回收,虽然一般情况下我们用不到它,但是研究空间配置器可以让我们对STL有更深的理解。

为什么需要空间配置器

  我们之前在实现各个容器的时候,需要申请空间大的地方都是通过new申请的,但是这样的申请方式有着很大的缺陷:
  1、空间申请和释放需要自己管理,容易造成内存泄露。
  2、频繁向系统申请小块内存,造成内存碎片。
  3、频繁向系统申请内存,影响程序效率。
  4、无法应对申请空间失败的情况。
  5、代码复用度不高。
  6、代码韧性较差。
  7、没有考虑线程安全的问题。

空间配置器实现原理

  以上所说的不足,主要原因就是程序频繁向操作系统申请小块内存导致的。在SGI-STL中以128字节作为小块内存和大块内存的分界线,同时也将空间配置器分为两级结构。一级空间配置器处理大块内存,二级空间配置器处理小块内存。

一级空间配置器

  以及空间配置器的实现较为简单,它主要是对malloc和free进行了一层封装,和我们曾经说过的new和delete的实现类似,其封装具体添加的内容主要是用来处理异常的。并且向其中添加了一个回调函数handler,当空间申请失败时会执行其中的处理操作,我们可以选择抛异常,中断或是其他行为都可以自定义。

二级空间配置器

  二级空间配置器所作的事情会更多一些,因为为了避免频繁向系统申请小内存空间,每次我们在释放小内存的时候空间配置器其实并不会将其让系统回收,而是自己进行了回收,等到用户重新想要申请小空间的时候,再从自己回收的内存中拿出一部分交给用户。
  二级空间配置器在内部实现了一个内存池,空间配置器通过维护这个内存池来给用户分配空间。
  当用户想要申请一小块内存的时候,空间配置器会先从内存池中拉出一份交给用户,当用户释放这块空间的时候,空间配置器并不会将这块内存还给内存池,而是当用户想要申请新的小空间时,优先使用这块已经从内存池中分配出来的空间。
  当内存池中的所有空间都用完时,空间配置器才会重新去向操作系统申请一块大空间来补充内存池。
  空间配置器中是通过哈希桶来向用户分配小块内存空间的,空间配置器将哈希桶分为一共16个桶,每个桶下面管理一部分小块字节的空间,此时的哈希函数为申请空间大小 / 8,例如我们要申请8字节空间,则会到一号桶下面拿到它下面的内存空间,因为对应桶会保证当前下面所挂内存空间至少为桶号 * 8的大小,例如1号桶下面的内存空间大小都是8字节,2号桶都是16字节的,以此类推,因此一共16个桶16号桶下面的空间都是128字节的,刚好以8字节为单位平分小内存空间。一开始所有内存都是在内存池中的,当有内存从内存池中分配出去,或者要回收回来时就会有新的空间挂到哈希桶对应的桶下面,方便下次我们继续分配。也正是因为这样的哈希关系,我们获取的内存空间一般都会向上取整为8的整数倍字节。
  当拿到要分配的空间的大小n时(这里假设<=128byte使用二级空间配置器)会进行以下操作:
  1、向上对其为8字节的整数倍。
  2、计算桶的位置,这里的哈希函数即为n / 16。
  3、查看桶中是否有内存块,如果有内存块则取出一块内存,如果没有,则向内存池索要。此时会调用chunk_alloc(size_t n, size_t& nobj),n为一块空间大小,nobj为一共申请多少块,默认nobj = 20,共向内存池申请total = n * nobj的空间。
  4、如果内存池剩余空间大于total,则直接分配,并且把一块交给用户,其他块交给哈希桶挂起;如果内存池剩余空间小于total,但是至少有一块的空间,则会重新计算nobj的大小,nobj = 剩余空间 / n,然后将能分配的空间交给用户,多余的挂到哈希桶上;如果内存池目前剩余空间已经不足一块要申请的空间,则会向系统申请大内存空间,并将剩余的一部分空间挂到对应的哈希桶上。
  5、向系统申请新内存也会出现两种情况,如果申请成功,则放入内存池,递归chunk_alloc,如果申请失败则去搜索哈希桶,取出桶中尚未使用的内存放入内存池,再调用chunk_alloc。
  6、如果连哈希桶中也没有多余空间,则会调用一级空间配置器,这里又出现两种情况,如果一级空间配置器申请内存成功则放入内存池,递归chunk_alloc,如果申请失败则会抛异常,处理异常。

【Cpp】哈希的应用

发表于 2019-11-06 | 分类于 Cpp
字数统计: 1.9k

哈希的应用

  哈希思想在算法中的应用繁多其重要性是不言而喻的,这里简单介绍两种哈希在大数据中的应用。

位图

算法思路

  假如说有这么一种情景:给40亿个不重复的无符号整数,没排过序,判断一个无符号整数是否在这40亿个数中。
  首先我们从时间考虑,假如说我们遍历40亿个数,事件复杂度是On的,如果我们先排序再用二分查找,排序要ONlogN二分查找要OlogN也还是不够快。不过这道题最重要的不是它的时间,而是空间,如果我们把40亿个整形全放到内存中需要4G * 4 = 16G内存,40亿字节 == 4G,不难发现我们根本存不下,那么怎么办呢?这里就需要用到位图。
  我们标记一个数是否存在根本不需要存储完整整数,我们只需要用存在或者不存在两种状态对其进行标记即可,而两种状态的标记,只需要1位数据即可,由此我们可以用40亿比特位来标记40亿个数是否存在。并且无符号整形的上限差不多也就在42亿,我们就算标记完全部数字用到40亿位也只需要4 G / 8 = 500M内存,由此我们使用位图进行标记差不多相当于将空间压缩了32倍。
  标记思路就是40多亿位分表标识40多亿无符号整型,一个数如果存在则它对应位标记为1,否则为0。假如说0存在,则第0位标记为1,32不存在则第32位标记为0,而无符号整形也是有上限的,40多亿位完全可以标记所有无符合整形。

实现

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
#include <iostream>
#include <vector>
class BitSet
{
public:
//要保证每一个数据都能映射到一个唯一的位置,位图的大小与最大映射数据上限有关
//因此这里的range代表的是映射的最大数据
BitSet(size_t range)
{
_bs.resize((range >> 5) + 1);
}
//存储
void Set(int num)
{
int index = num >> 5;
int bitIdx = num % 32;
_bs[index] |= (1 << bitIdx);
}
bool Find(int num)
{
int index = num >> 5;
int bitIdx = num % 32;
return 1 & (_bs[index] >> bitIdx);
}
void ReSet(int num)
{
int index = num >> 5;
int bitIdx = num % 32;
_bs[index] &= (~(1 << bitIdx));
}
private:
std::vector<int> _bs;
};
int main()
{
BitSet bs(64);
bs.Set(1);
bs.Set(64);
bs.Set(4);
std::cout << bs.Find(1) << std::endl;
std::cout << bs.Find(64) << std::endl;
std::cout << bs.Find(4) << std::endl;
std::cout << bs.Find(3) << std::endl;
bs.ReSet(4);
std::cout << bs.Find(4) << std::endl;
}


1
1
1
0
0

  但是使用位图有一个缺陷,就是我们无法解决哈希冲突,如果我们想要判断字符串,当字符串转换为整数时就有可能会造成哈希冲突,因为算法的原因两个不同的字符串可能会最终会转换为相同的整数,所以在判断字符串等其他需要转换并且可能会造成哈希冲突的类型时不能直接使用位图,于是一种进化版的位图诞生了。

布隆过滤器

思想

  布隆过滤器是专门为了解决为途中转换会造成哈希冲突的情况。例如我们现在要用位图标记字符串,我们两个不相同的字符串经过哈希函数转换后可能会出现最终一样的转换结果于是便出现了哈希冲突,例如str1哈希转换后为24于是我们将第24位置1表示str1存在,但是此时我们在判断str2是否存在的时候发现str2哈希后的值也为24,但是str2并不存在,于是这里就出现了哈希冲突,进行了误判。
  为了解决它,布隆过滤器会选择利用多个不同的哈希函数对一个字符串进行哈希,并将所有哈希结果的对应位全部置1,这里与位图的思想无异。当我们查找一个字符串是否存在时再用同样的多个哈希函数对其进行哈希,然后依次查找每一位哈希结果,如果全为1则可大几率认定为这个字符串是存在的。例如str1存储利用三个哈希函数得到结果为24, 26, 28,于是我们将这3位置,我们在查找str2时利用同样三个哈希函数转换得到结果24, 25, 27,虽然24造成了冲突,但是由于25, 26并不为1,所以也并不会误判str2存在,只有str1三次哈希后结果在位图中全都为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
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
#include <iostream>
#include <vector>
#include <string>
#include "BitSet.hpp"
struct HFun1
{
size_t operator()(const std::string& str)
{
size_t hash = 0;
for(auto& ch : str)
{
hash = hash * 131 + ch;
}
return hash;
}
};
struct HFun2
{
size_t operator()(const std::string& str)
{
size_t hash = 0;
for(auto& ch : str)
{
hash = hash * 65599 + ch;
}
return hash;
}
};
struct HFun3
{
size_t operator()(const std::string& str)
{
size_t hash = 0;
size_t magic = 63689;
for(auto& ch : str)
{
hash = hash * magic + ch;
magic *= 378551;
}
return hash;
}
};
//HFun为3个自定义的哈希函数
template<class T, class HFun1, class HFun2, class HFun3>
class BloomFilter
{
public:
//k = (m / n) * ln2
//k:哈希函数数量
//m:位图大小
//n:元素个数
//m = k * n / ln2
//number表示元素个数,布隆这里不用元素最大上限作为位图的大小,因为可能会造成大量数据浪费
//这里利用二次哈希,节省空间
BloomFilter(size_t number)
:_bitCount(5 * number)
,_bs(_bitCount)
{
}
void Set(const T& data)
{
int index1 = HFun1()(data) % _bitCount;
int index2 = HFun2()(data) % _bitCount;
int index3 = HFun3()(data) % _bitCount;
_bs.Set(index1);
_bs.Set(index2);
_bs.Set(index3);
}
bool Find(const T& data)
{
int index1 = HFun1()(data) % _bitCount;
int index2 = HFun2()(data) % _bitCount;
int index3 = HFun3()(data) % _bitCount;
if(!_bs.Find(index1) || !_bs.Find(index2) || !_bs.Find(index3))
{
return false;
}
return true;//可能会有误判
}
//布隆为了防止误判不提供删除操作

private:
BitSet _bs;
size_t _bitCount;
};
int main()
{
BloomFilter<std::string, HFun1, HFun2, HFun3> bf(1000);
std::string str1 = "https://misakifx.github.io/";
std::string str2 = "https://blog.csdn.net/qq_41669298";
std::string str3 = "https://space.bilibili.com/14406161/#/fans/follow";
std::string str4 = "https://space.bilibili.com/#/fans/follow";
std::string str5 = "https://space.bilibili.com/4406161/#/fans/follow";
std::string str6 = "https://space.bilibili.com/146161/#/fans/follow";
bf.Set(str1);
bf.Set(str2);
bf.Set(str3);
bool ret = bf.Find(str1);
std::cout << ret << std::endl;
ret = bf.Find(str2);
std::cout << ret << std::endl;
ret = bf.Find(str3);
std::cout << ret << std::endl;
ret = bf.Find(str4);
std::cout << ret << std::endl;
ret = bf.Find(str5);
std::cout << ret << std::endl;
ret = bf.Find(str6);
std::cout << ret << std::endl;
}



1
1
1
0
0
0

  布隆过滤器一般来说不提供删除操作,但是其实是可以实现的,但是这里就需要借助引用计数,如果借用引用计数那么一个位肯定解决不了,就需要用多个位,那么就需要开辟更多空间,这里就需要根据需求来设计。

12…9
MisakiFx

MisakiFx

Hard working or giving up!!!

86 日志
10 分类
64 标签
GitHub E-Mail 网易云音乐 CSDN

© 2020 MisakiFx
我的网站的访客数:
|
主题 — NexT.Pisces v5.1.4
博客全站共273.4k字