引言

Intel作为作为微处理器的航头老大,一直引导CPU的进步发展,也正是因为Intel是一个有着历史包袱的企业,所以站在现代CPU看起来,有一些非常奇葩的设计遗留下来,这些设计一开始是为了兼容,慢慢的将这种兼容又发展成新的功能,把“包袱”转换成“亮点”,段设计就是其中的一个很重要的代表,要想搞懂这个设计在不同的CPU的如何保持兼容和强化,我们必须要慢慢的把CPU的历史给捋顺。

前言

我们要介绍第一个CPU是8086,虽然Intel前面也生产了4004、8008、8080微处理器,但是8086基本上后面所以现代化CPU始祖,Intel后面生产的CPU都对8086兼容,所以可以说段这个“祸端”就是从8086种下来的

8086作为第一款的16位处理器,由于技术的问题,出现了一个严重问题寄存器只有16位,而地址总线却有20位,要想只通过一个寄存器表达地址的值显示无法实现,所以8086采用了一个段寄存器,segment × 16+offset(CS:IP),采用这个方式就能实现20位地址索引

段设计对程序影响

前面简单的介绍了段设计的原因,现在我们来看看这个设计的对16位程序的影响。

兼容性

由于段的存在,我们设计程序的时候可以更加自由,我们可以假设我们是在任何低16位置的内存上,只有到时切换程序时候切换段就可以

安全性

我们可以用相同的低地址存代码和数据,只需要切换段就行,而且我们也不需要考虑数据要多少空间,代码要多少空间,以便设定跳转地址

可以说段设计是16位程序的一个很优雅的做法,但是到了32位的时候程序不行了

32位处理器的改变

我们知道32位处理器的诞生带来了两件事,第一个就是寄存器有32位了,说明最大内存地址可以到4G了(0x000000-0xffffff),而且总线地址也有32位了。这个时候就很尴尬了,原来的段设计到这里就成鸡肋了。但是为了兼容,我们还是给他一个功能,段选择子,当然现代Unix操作系统没有用这个东西,只是在初始化的时候意思意思一下,具体可以看一下这篇博客GDB

总结

最近学操作系统感觉有很多疑惑,了解很多知识,总想好好总结一下细节,结果发现总有大神们早就写出来了,而且非常详细,我就不班门弄釜了,把下面的lab好好思考,提炼出自己的知识。

引言

本文是基于mit6.828 的lab1对操作系统的思考,网上有不少关于lab1的博客,大部分都是介绍如何完成lab1的问题,介绍的比较详细的有这个博客,在这里我就不从问题出发,建议大家看完上面的博客在看我这篇博文,我这篇博文就是从把我遇到的疑惑提炼出知识点,然后再把这些知识点串起来

实验目的

作为操作系统的第一个实验,在完成lab1我们主要目的就是要了解什么是操作系统,后面的lab都是在这个基础上搭建完善好系统的各种功能,就好像你画一幅画,第一步你先把人物的轮廓外形画出来,接下来你在把人的鼻子耳朵眼睛等等慢慢画出来,所以第一个实验非常重要,如果不把骨架搭好,你的操作系统再怎么豪华强大也是空中楼阁,所以我们在这个lab上一定要花上很多时间,万事开头难,只要攻克了这个,操作系统也就离你不远了

前言

谈操作系统之前必须得谈谈什么是计算机,因为我们的操作系统是运行在计算机上面的,操作系统与计算机关系密切,我们可以用一个很贴切的比方,假如你想了解手套为什么长成那么奇怪,那么你得先举起你的双手看看。

闲话不多说,进入正题,计算机最核心部分就是CPU,记得电脑刚发明出来的时候,编程只能通过穿孔卡片,当然计算机发明这么久,CPU的核心功能基本上没有变,还是只能通过“穿孔卡片”,只不过我们编程语音将我们的使用的语音如C,Python等变成“穿孔卡片”,这里有个非常重要的概念:指令。也就是每个CPU的是每次只能执行一条指令。当然第二个重要的就是内存了,前面说了CPU是必须要通过”穿孔卡片“来编程的,但是随着程序愈来愈大,我们必须要使用一个东西来存贮“卡片”,所以内存孕育而生了,其实很多感叹电脑这个词实在是太贴切了,人脑可以处理问题,电脑也可以处理问题,人脑有短期记忆长期记录,电脑有寄存器(短期记忆)内存(长期记忆)。

简单的谈了谈计算机,我们提出两个重要的前提

  • 计算机通过顺序读取一条一条指令来工作
  • 计算机从内存获取指令

所以操作系统的就是在内存上面运行自己并帮助其他程序的一个大程序,总的来说它就是内存上面的一段程序,当然它的功能就是好好在它一亩三分地上面“分封诸侯”,维护自己的“王位”。

由于一开始它只是待在软盘或者磁盘等存贮设备上的一段程序,接下来我们就看操作系统如何“上位”内存的“宫斗大戏”。

上位篇

在操作系统“上位”之前,其实计算机还进行了一个小操作系统(BIOS)运行,具体的流程可以看这篇文章,如果把电脑看做人的话,BIOS就是我们的脊髓,它控制我们的身体四肢(硬件),但是却无法灵活的操作他们(比如非条件反射的膝跳反射),但是它却不可少,少了它就成植物人了。BIOS的作用总结起来就是感知硬件,调控硬件(比如CPU电压,内存频率)。

BIOS与操作系统最密切的一个地方就是设置启动盘,大家可能大多时候都是听文件文件比较多,但是文件这个概念其实是操作系统的,在没有操作系统之前是没有文件这个概念的,只有盘这个概念,比如一块硬盘、一张软盘、一个U盘,所以BIOS的一个重要工作就是选定一个存储硬盘,然后读取上面的程序运行。

所以我们从这时候可以得到一个结论,安装操作系统,只需要按照BIOS的规定把程序放到某一个存贮设备(磁盘、U盘、软盘)专门位置上(一般是头部开始),开机后然后就静等BIOS把程序加载到内存,就完成了“上位”过程。

我们已经知道操作系统的外部条件,接下来分析一个操作系统到底该有啥

操作系统结构

首先我们要回顾一下操作系统的发家史,刚开始是没有操作系统的这个概念的,随着在电脑上要运行的越来越多,每个程序都要写大量底层代码来操作硬件这样无疑每个程序越来越来臃肿,所以我们需要让操作系统管理来管理硬件,这样不但能够提供程序兼容性(一次编译、到处运行),而且能高效利用硬件(操作系统专供)。所以操作系统也就是程序的分工的产物

接下来我们看看操作系统的发展历史,大家都知道汇编语言是除了机器语言最接近底层的一种语言,第一个Unix系统一开始也就是使用汇编编写的。但是汇编语言不易于维护,所以1973年汤普逊和里奇用C重构了Unix,但是部分与硬件接触太大的地方还是必须使用汇编(in、out端口,操纵指定寄存器等),所以现代操作系统还是用C与汇编混合编写的(C占大部分),当然最后都会编译成机器码,所以我们从机器码角度来看,最后的结果都是相同的,不同的是我们使用不同的工具来生成机器码

前面我们介绍了启动盘,其实BIOS给我们只是从启动盘上面取了一小段数据(第一个扇形区)放到内存上面(512B),然后执行那小段上面的机器码,所以接下来就有一个问题,随着我们的操作系统功能越来越完善,取出来的代码肯定不是全部代码,代码只有放到内存上面才能跑,所以前人就把代码分成两部分,一部分称作引导,另一部分才是核心代码,引导作用就是把核心代码放到内存上面去

所以操作系统被分成两部分

  • 引导
  • 核心

这里比较有意思的地方就是引导和核心如何交换程序控制权,由于要讲解必须要牵扯代码,所以我把这部分分离出来,放到这篇博客上面,要了解细节可以看这篇博客。

现在我们假设你已经知道引导将核心代码加载在了内存上面,现在我们就从这里开始分析,堆栈作为程序的基础,首先我们要提一下堆栈

堆栈

什么是堆栈呢?看下面这张图

堆栈

堆顶为大地址,我们使用的时候只要不断把栈顶往下推,就能将线性内存变成一个数据结构。当然有个问题,我们必须要知道什么地方是栈顶,现在我们想想操作系统必须要放到内存的某一个地方,假如放到低位置,那么我必须要记住操作系统的最高位置,如果不这样做当堆栈顶到操作系统的存贮地址,那么操作系统就被破坏了。所以我们只能把操作系统放到高的内存地址,这样我们既能安全的使用堆栈,而且保证了操作系统的安全

所以我们接下来就谈谈由于这个设定引发的一系列问题

操作系统的高地址

在lab1中,操作系统的起始代码被设定为0xF0100000的高位

从这个地址我们可以分析出来什么0xF0100000,因为我们知道32位操作系统最高只能有4G内存,也就是2的32次方内存,这个地址代表的是系统最后面的255M内存的空间,也就是操作系统给自己留了255M剩余内存,给前面保留了(4G-255M)空间

操作系统这个设计是非常好的,不仅给自己留下扩展空间,也给其他代码带来便利,就是从0-(4G-255M)这部分内存随便用,怎么改都不会出问题

从现在角度来看,个人电脑随便都是2G、4G内存,但是在70\80年代,几M内存都很很大的存在,如果我内存没有4G这么大,那么这个操作系统就无法使用了,而且你留下256M给操作系统,有的时候我整个电脑内存都没有这么大,留下那么多,就是浪费

所以最后他们想出来一个办法,就是现实和理想之间放一个转换器(MMU),也就是动态内存管理。操作系统也不管你机主有多大内存了,我假设你有4G,当你用一块,无论是什么位置,我从空余的地方给你取出来,假如你没有4G,我就把一部分不常用内存值的放到磁盘上面,这样通过这样这样的操作的实现内存的高效利用。

操作系统对内存这种骚操作就相当于在更高的维度上建立了一种抽象,不论底层硬件怎么变(内存大小不同),我高层都不需要变,只需要底层把根据实际情况依次映射,这样无论你换多大内存,我都不需要重装系统。

这种映射不通过代码很难将清楚,所以我这里也不提太多,如果你想知道怎么映射,硬件如何配合,你可以看我这篇博客,详细介绍了内存分页的骚操作。

总结

至处到这里我们的操作系统之旅就结束了,我们成功在引导帮助下上了内存,也使用了提高操作系统的地址保证了堆栈的正常使用,接下来就是操作系统的各种附加功能,我们也会在接下来的lab中继续讲解。

lab1不止介绍了这两个地方,但是在lab1中我觉得最重要的地方就是要知道操作系统是什么,它从哪里来,它要到哪里去,操作系统毕竟牵涉到硬件,很多硬件知识我们不一定能搞懂,比如说要切换哪几个位到保护模式,怎么输出端口才能读取扇形区,但是我们必须要搞懂他这样做的原因,这也是我在这篇里面谈了很多操作系统历史的原因,希望在理解操作系统上面能给大家带来一点启发。

在最后的话,我谈一谈我对入门这门课的感受吧,我算编程基础还算比较扎实,但是在一开始学习的过程中一脸懵逼,C语言的各种骚操作,汇编与C疯狂混合,看惯了脚本语言的我,对这种改一下就编译不过的“硬骨头”异常难受,一开始根本看不下去,有的时候看几行代码,查资料好几个小时,而且资料特别难找,你不知道这种骚操作有啥意思,在这里还得感谢学习过这门课的学长学姐们,在网上无私的把自己的感受分享出来,慢慢的根据他们的资料和自己的调试还有自己找资料,慢慢的把这个代码一行一行搞懂,搞懂之后特别感慨,其实也不是很难,难的是要把你知道的所以知识点串起来,然后你就能搞懂为什么要这么做,所以我推荐大家还是多看代码,多去思考为什么要这么做,必须要自己的思考在里面,如果单纯的知识为了完成实验其实很简单,但是难就难在把这门课琢磨透,搞懂他们为什么要这样考你,毕竟大家最后的目的都是自己做出自己的操作系统,只有了解的透彻,才能“破而后立”搞出自己的创新,而不是复制他们的壳子,所以加油把每一行代码都搞懂,多思考,不要骄傲,毕竟这只是教学类的操作系统,要想自己写出来还得不懈努力。

接下来还有6个lab需要完成,终于迈出的第一步,希望在年前能够完成所有的实验吧!!!加油!!!

引用

“C语言虚拟内存表”

引言

一开始想直接做一个操作系统,但是万事开头难,学习操作系统需要太多基础知识了,所以就按照网上推荐先学习mit6.828的课程,先把xvf6操作系统搞懂,然后在来实现自己的操作系统,下面就是学习这个课程的体会,按照各个lab的顺序,介绍自己的心得体会

课程的地址是: mit6.828
PS:由于mit6.828课程仓库需要翻墙,所以我把clone下来放到我的github仓库,我的仓库里,大家可以clone下来(我会逐渐完成所以的实验)

目录

课程总结

学到一半才发现这是一门研究生课程的学习,的确难度非常大,而且每一个实验都可以拿出来大做研究,但是课程给的资料非常详细,基本上每个硬件细节都给出了链接,但是对于最大的困难还是英语资料实在太多,有点“吸收”不过来。不过一路学习下来,感觉还是收获很大,基本上每个实验都环环相扣,每个实现细节都需要反复思考,为什么要这样做,还能怎么做,最终实现的xvf6还有些许跟不上时代的脚步,但是基本上框架已经有了,就是按照这个骨架完善更多细节,所以这个课程还远远没有结束,期待接下来对这个操作系统的进一步改进!!!

引言

最近逛知乎的时候看到一篇知乎回答很有趣,也给了很深的感触,自己对于操作系统、数据库、HTTP用的都非常熟练,但是也从来没有去想怎么怎么实现或者背后深层次的原理

以前刚开始学习的时候自己也看过很多关于操作系统、数据库的书,但是就像走马观花一样,很多书就是过了一遍脑子,然后就没有了,在2017年下半年自己也开始尝试把自己以前只是了解只是会用的东西拿出来咀嚼咀嚼,并在这个过程中写出一些自己觉得还是有点干货的博文。而且我也比较享受把复杂的问题简单话的过程。

操作系统、计算机、数据库、编程原理在我看来都是非常复杂庞大的东西,在2018年,希望能够将上面这些复杂的东西搞的简单一点,当然在这个同时我也会将我将问题简单话的过程中分享出来。

当然这些东西都太过宽泛,比如操作系统。很多人刚开始学习编程了解了操作系统概念,还有听到很多牛人都说自己写了一个操作系统都会在心里暗暗的立下一个Flag,自己也要做一个操作系统,但是很多人的热情慢慢的被无数的复杂概念慢慢磨掉,最后能坚持到做出一个完整的系统没有几个。作为一个普通人,我们没法一口吃下一个很大的“饼”,当然你如果叫爱因斯坦给你造一个原子弹,它也只能拍拍手跟你说我只能证明它能造出来。所以有效的解决问题的方法是将问题分解,或许最终我们最终造不出操作系统,但是我们对操作系统也能更深一步了解。

操作系统

首先谈谈操作系统,其实我们对操作系统的理解大致都停留在开关机。我们要分解的问题就是我们对这个“黑盒子”的疑问

  • 操作系统如何管理硬件,比如说鼠标移动点击、键盘输入
  • 操作系统如何让多用户使用
  • 操作系统如何在多用户的情况下区分每个用户
  • 操作系统如何分配内存,如何限制用户的内存
  • 操作系统如何管理文件,如何避免文件被同时写入
  • …..

当然我这里只是列举了一些直观的问题,在解答这些问题的时候,我们会逐渐衍生出各种问题,最终我希望所有的问题都能被简单话

数据库

数据库我算使用的比较多了,但是对数据库背后的机制也是懵懵懂懂,只知道他能保证这些功能,比如事务的原子性、一致性、分离性、持久性。

我觉得了解数据库就是要了解它是如何实现这些特性的,当然这个问题也很宽泛,我们可以尝试分解成

  • 数据库如何将输入复杂的查询分解成为数据库的操作
  • 数据库如何避免死锁
  • 数据对于插入删除异常如何解决
  • …..

其实在我看来数据库可以分解成两大块,一个是编程语音解析(SQL),一个是高效的存贮(Database)

所以了解数据库也可以尝试了解编译原理,了解如何实现解析SQL,所以接下来我就不提编译原理了

总结

其实想想自己的这种把复杂问题简单话就是华罗庚先生曾说的一句话:“把书由薄变厚,再把书由厚变薄”,首先我们得把这些看起来很简单的问题复杂话,最后慢慢的把这个复杂的问题简单话,这样你才能真正的把这个问题给搞懂。

对于我来说,从小或许受应试教育的影响,自己只学会了复杂问题给解决,但是不懂得解决后再把复杂问题简单话,所以看起来我懂很多复杂问题,但是其实换一个场景,换一个问题就一知半解了。所以自己慢慢的开始改变自己的方法,不满足于解决问题,而着重于简化问题,希望自己的一点经验也能给后来人一点启发。

本篇博客主要基于这篇博客的扩展,建议阅读前先阅读这篇博文,这篇博文详细介绍AVL树的实现原理,完整代码在githubavl.go文件中

浅谈”树”这种数据结构
Github
可视化页面

引言

AVL树是在对二叉搜索树的一种优化,通过构造一棵高度平衡的二叉搜索树从而实现提高空间利用率,所以在了解如何实现之前,必须了解如何构造一棵二叉搜索树,你可以阅读我的这篇博客了解如何构建一棵二叉搜索树,虽然我是用Go来实现的,但是不必了解太多Go方面的知识,我在博客中尽量使用图片的方式来介绍实现原理

二叉搜索树实现原理

由于AVL树本质上也是一棵二叉搜索树,查找并不会改变树的性质,所以AVL的查找也是同二叉搜索树的查询相同,所以这里就重点介绍如何实现“增”和“删”

树的字段

在开始介绍如何实现“增”、“删”之前,我想提一下AVL树的存贮字段,在wiki上面的AVL和很多资料上面,AVL的树结构分别由下面四个组成: Val、 Left*、Right*、Parent*。

Val代表树存贮的值,Left、Right、Parent代表三个指针,分别指向左子树,右子树,父亲,而在我的实现中,我去掉了父亲指针,对于讲解来说,使用一个父指针能很好的解决从子遍历到父亲的经过,但在实际的应用中,我们完全可以使用一个列表存贮从父亲到儿子之间的值,这样的话,能实现一样的功能,而且能节省存贮空间(每个子树都少了一个父指针),但是相应的程序也变得比较复杂起来。

虽然我在讲解的过程中会直接获取节点的父节点,但是在实际的代码实现中,是通过获取从列表中获取该节点的父节点。

AVL树的“增”

引用

https://en.wikipedia.org/wiki/AVL_tree

本篇博客主要基于这篇博客的扩展,建议阅读前先阅读这篇博文,这篇博文详细介绍二叉搜索树的实现原理,完整代码在githubbinary.go文件中

浅谈”树”这种数据结构
Github
可视化页面

引言

之所以使用Go来实现,个人还是比较喜欢Go的,作为一个基础数据结构,Go用来实现这个速度比Java、C++都快,而且相比Java也能节省内存,而且我也不喜欢换使用冒号。

二叉搜索树的基本功能

作为一个树结构,主要必须实现三个功能,查增删(当然有改,不过改是删和增的结合所以就不算在里面),当然二叉树还能帮我实现一些额外功能,比如寻找最大值最小值等等,实现一颗二叉搜索树必须要保证在“增”和“删”的时候保持树结构不变,也就是保证还是一颗二叉搜索树

什么二叉树是二叉搜索树呢,二叉搜索树只需要保证一点

  • 任何一个节点,它的左子树(不为空)所有值小于这个节点值,它的右子树(不为空)所有值大于这个节点值

所有我们在实现增删的时候必须要牢记这点,而且我们也可以知道在你开始对这颗二叉树进行增删的时候,它一定已经满足了上面这个条件

标准的二叉树

如何在上面这颗标准的二叉树里面查询到我们想要的值呢?我们知道一颗二叉树只需要知道根节点(上面的10)就能通过遍历得到所以的节点的值,所以我们在实现中声明一个二叉搜索树的时候只保存一个root节点,通过这个节点,我们就可以实现所以的增删查改功能了

为了找到每个值a,我们依次要在每个节点上对值进行比较,因为每个节点的值代表已经将这堆数据分成两个部分,一堆比这个值大在右边,一堆比这个值小在左边,这样只要最终能找到一个那个值的最小区间的对应值(找到)或者找到一个为空的叶节点(代表没有找到),

通过最简单的查找,我们可以反推出一个理论,假如我们需要插入一个值,我们只要先尝试去寻找到那个值,假如找到了,因为已经存贮了就不插入,假如没找到就会找到一个为空的叶子节点,那样只要在父节点将这个为空的叶子节点替换成这个值为a的节点,我们就完成了插入

所以查找和插入是相对的,知道怎么查找就知道怎么插入,接下来我们详细介绍如何删除,这个非常关键,因为它是后面要介绍的高级树实现高效的删除的关键

删除

我们还是以上面那种图举例子,删除我们最先想到的是删除12,17那些节点,直接删除掉对二叉树没有什么影响,但是如果我们要删除那些带有节点的呢?我们先简化问题,先看一个只有两个节点的树

双节点树

我们要想删除10,有两种可能

左移

右移

一种是将左边值移过来,一种是将右边值移过来,这两种都不会破坏二叉树的平衡,现在我们假设我们倾向将左边的值移过来,我们再回到上面那棵标准的二叉树,如果我们要删除掉10节点,我们要把那个值移过来,我们直接在可视化界面进行这个操作

删除10后的标准二叉树

我们发现,我们只需要将7和放到10的位置上就完成了一次删除的操作,而7与10的关系是,7是10左边的那堆值最大的,用一个通俗的话来说,完成改朝换代的关键就是要找一个能镇的住手下的人,由于“10”挂了,在左边只有“7”能镇住左边,所以”7”升官直接跑到“10”的位置了

根据这个原则我们将情况分成三种

  1. 左右子树都为空,直接删掉
  2. 左边子树或者右边子树有一个为空,将不为空的子树提上来当做删除的节点
  3. 左右子树不为空,将左边最大的值提上来替换删除的节点

对于第三种情况,为了编程方便,我们考虑一种情况,如果左子树的右节点有没有值(比如说上面的5节点),如果它右节点有值,那么左边的最大值肯定出现在,左子树的右节点上(就像上面左子树出现在5的右节点的7节点上面)。然后我们继续判断“7”节点有没有右子树,这样循环下去,我们总能找到一个节点没有右节点,这样我们就找到左子树的最大值了。

在上面这种情况下,我们将这情况分成两种

  • 如果左子树的右节点有值(循环下去找到一个节点右节点没有值)
  • 如果左子树的右节点没值(那么第一个左子树就是最大值)

具体的代码binary.goDelete(寻找节点)方法和delete(删除节点)方法中

总结

总的来说,二叉搜索树的插入是最容易理解的,但是删除的话要考虑不同四种的情况所以还是稍微需要点时间理解一下的,小小的一个二叉搜索树也花了近200行代码实现,但是相比后面的AVL树、红黑树的近千行代码来说,二叉搜索树还是比较简单的,而且后面实现的高级树结构基本上都是依赖二叉搜索树的实现(必须要按照二叉树的增删满足二叉搜索树的原则),所以我们对二叉搜索树的增删必须理解透彻。

引用:

https://en.wikipedia.org/wiki/Binary_search_tree

一直以来我对树这种数据结构就比较头疼,随便找一个红黑树的博客,大部分都是在谈怎么旋转怎么插入怎么删除,将算法讲的头头是道,但是就算你看懂了也不懂为什么要这样做,所以我们这篇博文就从可视化的角度,慢慢的介绍这些树的来世今生。

引言

首先给大家推荐一个神奇的网站,我们这篇博文很大程度上都是依托这个网站从可视化的角度分析各种树

网站的网址是http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

接下来我们从易到难分别谈谈下面这些树结构

  • 二叉搜索树
  • AVL树
  • 红黑树
  • Splay树
  • Trie树
  • B树
  • B+树

你可以点击下面高亮的标题尝试这种树结构的可视化操作,当然我在谈的过程中默认你已经打开可视化界面网站。

在开始介绍各种树结构之前,我们先谈谈为什么我们需要树这种结构。

假设我们一开始都有一个“柜子”存放东西,当我们东西很少的时候,我找东西的时候只要在柜子里面翻一翻就能找到,当我东西越来越多,在柜子里面找东西消耗的时间越来越多,这时候我就把柜子分类,让每一个柜子的东西都是固定的,这样我们查找时候不会在一个柜子里面寻找很久,这样无论你有多少东西进来,我查找的时间基本不会太长。

所以树这种数据结构就是为了解决当数据量越来越大的时候相比与线性查找时间基本不会太长。对树查找和线性的区别我们可以看一下这个可视化界面

线性搜索与二分查找

通过输入查找344,我们发现线性搜索花了15步才搜索到,而二分查找只需要2步,而且随着数据越来越大,线性搜索花的步数直线上升,而二分查找只会维持用Log(N)的步伐增长。

树的结构基本上都是基于二分查找,但是在维护这个查找树的方法上各种树有各种优化方法,接下来我们就从可视化角度来依次介绍各种树的原理和优缺点。

二叉搜索树

这个树可以称作所以后面变种树的鼻祖,基本上所以后面的树都是基于这个树的不足之处进行改良达到其各自的目的。

我们现在尝试构造一棵二叉树,我们依次插入3,2,4。然后一棵标准的二叉树就出现在我们面前,在我们插入的过程中,我们可以清晰的看到,第一个插入的变成了母节点,而且插入程序实现的非常简单,首先跟母节点进行比较,如果比母节点大,从母节点右边下滑,然后依次找到最后一个为空的节点把自己插入进去。

单调递增二叉搜索树

我们接下来尝试一下如果输入一个连续递增的数组进去,比如1, 2, 3, 4, 5,我们发现这个二叉搜索树会逐渐把所以的值放到右节点上。这时候我们我们尝试搜索一下5,我们发送这个二叉搜索树需要5次查询才能得到最终结果,这个基本上等同与线性搜索。

这里我们就发现二叉搜索树一个致命缺点,它容易造成一种空间的浪费,虽然这个树看起来很“高”,有5层,但是利用率极低,每层只有一个树,这样不但查找的时候效率不高,而且插入的时候效率也不高(很可能需要“爬”很多层)。

二叉树搜索树实现起来非常简单,只要用一个while循环就能完成插入查找等功能,但是由于它结构控制太低,它对数据要求要很高,它时候依次插入那些无序数字,而对那些有序数据来说,二叉搜索树等同与一个数组。

所以我们接下来介绍下面改良树,看看其他树是如何提高的空间利用率的,由于这篇主要是简单的谈一下这些树的优缺点,如果你想了解如何实现这样可以看一下我写的这篇博文,详细介绍了如何使用Go语言实现一个高效的二叉搜索树,如果你想彻底了解下面高级的树的实现,强烈建议一下了解一下二叉搜索树实现的方法,因为后面所以的树实现的前提必须满足是一个二叉搜索树,这点非常重要。

二叉搜索树Go实现

AVL树

1962发明的AVL树现在还生龙活虎的活跃在Windows进程地址空间管理,虽然作为最早的平衡二叉树现在有点干不过后面的年轻的小伙,但是作为前辈,后面小伙很多地方都是借鉴前辈的,所以我们有必要隆重介绍一下这个老前辈。

首先要说明一下什么是平衡二叉树,前面我们也看到了,二叉搜索树有个弊端,它有可能子树高度不一样,比如说1,2,3,4,5那个母节点1的左子树高度为0,右字数高度为5,平衡二叉树就没有这个问题,它规定所以节点子树高度差不能超过1,这样规定的话我们的树空间利用率就能基本上达到100%了。

AVL树就是一颗高度平衡二叉树,它的要求也非常简单,就两个

  • 必须是二叉搜索树
  • 必须是平衡二叉树

成为一个二叉查找树非常容易,但是为了必须满足平衡二叉树条件,这里我们给每颗树定义一个高度,默认空为0,这样就可以计算左右子树的高度差是否在-1和1之间判断是否是平衡树。

了解了这个之后,我们回到web页面,我们输入1,2,3看看AVL树如何避免像二叉搜索树一样过度生长

插入前

插入后

我们从这两幅图可以看到,插入前AVL树高度为3,经过单旋转后,将2旋转到1的位置,然后让树又满足平衡二叉树的条件和二叉搜索树的条件。让我们思考一下旋转的意义。

旋转的意义

第一旋转并没有改变二叉搜索树的特性,我们将二叉树看做一个一个小区间组成的区域,旋转将区间整体移动了,所以我们保持住了区间的稳定,而且我们把旋转的支点看做中心,我们发现通过一次旋转后,支点左右之间的数量发生的变化,其中一方增加一个,其中一个减少一方,通过这种方式,把高度差由2转成0

所以我们在插入和删除的时候造成的高度不平衡可以通过正确的旋转达到一个高度差的减少。而且我们可以很轻松的推断出在插入和删除的时候只需要通过有限的旋转就能实现树的平衡,但是我们也会发现这个平衡是非常严格的,每次插入删除的时候,删除或者增加的那条“路径”(从根节点到修改的节点)的各个节点的高度都会发生变化,所以我们需要检查和更新整条路径上高度差(也称平衡因子)是否满足平衡条件。

直接纪录每个树的高度并且约束高度差的方法能够很好的规避像上面二叉搜索树造成的空间利用率低问题,但是对于增添和删除操作频繁的数据来说,AVL树并不是一个很好的解决方法,因为每次删除和增加都必须检测路径上的高度差,虽然旋转比较高效,但是每次检测和修改高度会让这个算法花费太多时间在这个严格的条件上面。

总的来说,AVL树是比较好理解的一种平衡树算法,通过这个树的各种旋转操作,我们能很清晰的发现二叉树是一种很神奇的数据结构,一方面它可能是混乱的(分支混乱),一方面它又是整齐的,通过“扭动”它的身躯,将数据平均的分摊在根节点上面。我非常推荐你在这个可视化界面上通过一步一步将单独递增或者递减的数据插入AVL树中,你会发现AVL通过一次一次的“扭动”,将数据向根节点另一个方向传输过去。

这里我也不详细介绍AVL树实现的具体原理,如果你想了解更底层的实现,可以看我下面这篇博客

AVL树的实现原理

红黑树

在AVL树发明10年后鲁道夫 贝尔发明了红黑树,直到现在红黑树还依旧在C++的STL、Java的HashMap中发挥着重要作用,只所以要先介绍AVL树再介绍红黑树,因为从我的理解上来看,其实红黑树和AVL树原理都是类似的,只不过红黑树修改了AVL树的缺点并且将AVL的平衡原理进行了抽象话。

从数据结构上来看,红黑树相比于AVL树来说,只是将存贮高度的值换成了存贮颜色的值,从空间的角度上看,红黑树用一个二进制bool值(1Bit)换掉一个存贮int值(4Bit),节省了3Bit的空间,从增删所需要的操做来看,AVL树旋转可能需要lnN 步操作,而红黑树增不超过2次旋转,删不超高3次旋转,在增删效率上远远优于AVL树。所以我们有一个疑问为什么红黑树能用更少的空间实现更高的效率呢?

回答这个问题之前,我们再捋捋AVL它的实现原理,前面介绍了AVL实现平衡的原理的就是使的左右子树高度差维持在[-1,1]之间,高度差这个东西,你想想高度这个东西其实它就是母节点到叶子节点的路径,所以高度差我们翻译一下就是左右子树路径差,现在我们把平衡后的AVL树条件更加严格一点,我们规定左右子树路径差为0,也就是左右子树高度一样。

满二叉树

在上面那个严格的条件下,假如我们要新增一个到树末端,假如它加在像上面这样满二叉树上面,那么左右子树高度就立刻不相同了,但是对于一个AVL树来说,在这颗树上末端插一颗树并不会影响树的平衡,所以我们要想一个办法让插入这个值“不算高度”,这时候我们一想,如果我们把树节点分成两种颜色,一种红色一种黑色,红色不算高度,黑色才算高度,那样虽然我现在条件很苛刻“左右子树高度必须一样”,但是如果插入的是红色,那么就能很轻松的实现上面的条件。

好了我们通过上面的操作成功的将高度变成了黑高(黑色节点的高度),而且满足了一种更加严格的条件“左右子树黑高必须相同),假如说前面AVL树的高度差为[-1,1]之间都能实现高空间利用率的,那么在这种更加严格的条件下也能满足,但是现在又出现一个问题,我们看下面这棵树

不平衡树

当我们插入节点3的时候,由于插入一颗红色你把红色节点不算高度,所以在前面的约束条件下,插入3满足条件,但是实际上这棵树并不是一个平衡AVL树,为了避免这种情况的发生我们必须要做一个约束,我们要约束红色节点不能太多,所以我们就约束红色节点后面只能是黑色节点,这样路径上最少都会有一半都是黑色(红色黑色相同)。

我们现在得到两个约束,现在我们来说思考一下这两个条件的约束到底给我们带来了什么

  • 黑高相同
  • 红后面必须为黑

首先对于黑色节点来说,这棵树是高度平衡的(假设它只能看到黑色节点),高度差为0,但是对于红色节点来说,这棵树有可能是不平衡的(假设有N个黑节点,红色高度差可能有N-1),所以从整体上来看,红黑树牺牲了一定的平衡性换来了插入删除的高效性

这个高效性表现在哪呢?第一它不在需要更新所有的高度差,它只需要对受影响的路径上的有限节点进行染色就能实现再次的平衡,其次由于它不在需要高度的平衡,所以它能容忍树上的红色的不平衡现象,来减少旋转变化的次数。

前面我们分析了AVL树旋转的意义那么对于红黑树来说,旋转的意义是什么呢?

红黑树的旋转意义

前面我们知道了在AVL树中每一棵树都是独立的个体,所以每次旋转都是一次运输,将树按照节点扭动,但是对于红黑树来说,它要处理的情况是黑树高度的不同,当需要搬到的也是黑树,它的目的就是将黑树的高度平衡,对于红色的树来说,它更像一种胶水,它能保证当数据不平衡的时候(所以的树不可能全部变成黑树)还能使黑树保持一种平衡,从而使一棵树变得相对平衡。

所以红黑树的旋转的意义同AVL树是类似的,只不过红黑树在旋转的时候要更加注意,它不但要考虑我们要如何在不平衡的节点上平衡黑高,而且要考虑我们平衡了这个节点的黑高有没有对其父亲的黑高造成影响。

对于红黑树来说,由于颜色是可变的,所以着色(改变颜色)也是一种手段,而对于AVL树来说高度是固定的,只能通过旋转来改变,所以单独讲红黑树的旋转是没有意义的,或许有的时候只需要通过旋转就能实现黑高的统一,或许通过简单着色也能实现黑高的统一,但是只使用一种手段是不能高效的完成所以的条件。所以在我看来着色和旋转是相辅相成的

也正因为我们多了一个着色的手段,所以红黑树比AVL树在某些方面更加高效,随着而来也是更加复杂难懂,但是总体来说AVL和红黑还是类似的,在这里我就不深谈如何实现红黑树,如果你想了解如何实现红黑树,可以看我这篇博客

红黑树的实现原理

剩余的四种树的简析会待代码实现后陆续更新

引用

https://en.wikipedia.org/wiki/Binary_search_tree

https://en.wikipedia.org/wiki/AVL_tree

https://www.cnblogs.com/vamei/archive/2013/03/21/2964092.html

这篇博文是从问题理解动态规划的练习篇,通过几个动态规划的问题剖析进一步理解动态规划

找零钱练习题

  • 给定一个零钱数组比如[1, 2, 5],每个值代表一个面额的纸币,给定一个总数(aim),求换钱有多少种方法(每种面额纸币不限量)

这个问题非常经典,所以我就从最先容易想到的算法出发慢慢推导出动态规划

正向暴力搜索

面前一大堆钱,分成三堆,我们必须要从这三堆中抽取出来所以可能的方案,看看能够凑到总数。

我们第一个想到的就是正向暴力搜索,先从第一堆取出0张、1张、2张….,然后递归下去,让取出0张、1张、2张凑剩下的总数,等到取到最后一个钱堆或者总数正好相同的时候递归停止。

我们可以很轻松的写出下面的代码(Java)

int violenceSearch(int[] level, int index, int aim) {
        if (aim <= 0) {
            return aim == 0 ? 1 : 0;
        }
        if (index >= level.length) {
            return 0;
        }
        int sum = 0;
        for (int i = 0; i <= aim / level[index]; i++) {
            sum = sum + violenceSearch(level, index + 1, aim - i * level[index]);
        }
        return sum;
    }

这个函数接受三个参数,第一个是钱堆的面额数组,第二个是当前是拿第几个钱堆的序号,第三个是剩余要凑的总数

这个算法的核心就是sum = sum + violenceSearch(level, index + 1, aim - i * level[index]);,我们分别从钱堆里面取出想0张、1张…,然后计算剩下的总数和剩下的堆数方法总数和。

这个算法也可以优化成记忆搜索,总共有多少种方法拼钱,主要与indexaim有关,我们只要用map记录一下这个值就可以优化成为记忆搜索。

反向暴力搜索

反向的话比较难想到,但是正向暴力搜索没有办法分解成子函数,也就无法实现动态规划,所以我们必须要反向思考

首先我们假设纸币面额为1, 2, 5, 我们要凑10块钱,我们假设已经得到了所以的次数F(x, y)(x为由多少种纸币组成,y为凑多少钱),所以我们得到这个我们想要的结果F(3, 10) (也就是由3种面额组成10块)

假设我们得到了F(3, 10)所以可能的组成结果结合如下面10种

  • 10张1块
  • 8张1块、1张2块
  • 6张1块、2张2块
  • 5张1块、1张5块
  • 4张1块、3张2块
  • 3张1块、1张2块、1张5块
  • 2张1块、4张2块
  • 1张1块、2张2块、1张5块
  • 2张5块
  • 5张2块

现在我们把这10种可能按照5块的张数分成3份

  • 0张5块
    • 10张1块
    • 8张1块、1张2块
    • 6张1块、2张2块
    • 4张1块、3张2块
    • 2张1块、4张2块
    • 5张2块
  • 1张5块
    • 5张1块、1张5块
    • 3张1块、1张2块、1张5块
    • 1张1块、2张2块、1张5块
  • 2张5块
    • 2张5块

分别为0张5块(6种),1张5块(3种),2张5块(1种),也就是我们成功将F(3, 10)分解成 F(2, 10), F(2, 5), F(2, 0)

通过这种方式我们成功构造出子函数,我们很容易就能写出递归函数

int lowBackVS(int[] level, int index, int aim) {
    if (index == 0)
        return aim % level[index] == 0 ? 1 : 0;

    if (aim < level[index]) return lowBackVS(level, index - 1, aim);
    else {
        int count = 0;
        for (int i = 0; i * level[index] <= aim; i++) {
            count += lowBackVS(level, index - 1, aim - i * level[index]);
        }
        return count;
    }
}

这里我们要看到第二个if,我们判断剩下的余额是否够当前的一张,如果不够,那直接就是前n-1种纸币能够组成的次数。(也就是假如你剩下4块钱要用一张5块来组成,肯定不可能,直接返回前面的n-1种货币能够凑出4块的种数)

这种时间复杂度为O(n) = n X aim X aim, 假如aim比较大还是比较耗时间的,我们看看是否能够优化一下

反向暴力搜索优化

我们还是回到上面那个例子,我们这次按照能够减去一张5块的进行分类,这样我们就分成了两类

  • 无法抽掉一张5块
    • 10张1块
    • 8张1块、1张2块
    • 6张1块、2张2块
    • 4张1块、3张2块
    • 2张1块、4张2块
    • 5张2块
  • 能够抽掉一张5块
    • 5张1块、1张5块
    • 3张1块、1张2块、1张5块
    • 1张1块、2张2块、1张5块
    • 2张5块

一张是无法抽掉一张5块(6种),能够抽到一张5块(4)种
我们回到函数定义,这样我们成功将函数F(n, aim)分解成两个F(n-1, aim) 和F(n, aim - level[index])

我们成功的将子函数进行化简成两项

int backVS(int[] level, int index, int aim) {
    if (index == 0)
        return aim % level[index] == 0 ? 1 : 0;

    if (aim >= level[index])
        return backVS(level, index - 1, aim) + backVS(level, index, aim - level[index]);
    else return backVS(level, index - 1, aim);

}

我们可以看到我们成功将时间复杂度降到了O(n) = n X aim,至此我们写出了比较完美的反向暴力搜索方法,当然我们也能够像正向暴力搜索优化成记忆搜索

动态规划

前面我一直没有怎么提记忆搜索法,因为这个方法基本上等同与动态规划,只不过动态规划使用数组存贮,记忆搜索法用字典存贮。

前面我们知道我们能通过分解函数将问题划分成前面的子问题,所以我们只需要构建一个二维数组,x,y分别代表由几种货币组成(index),组成的总数(aim),这样就能通过慢慢“填”写动态规划表,最后求出由N种货币组成钱数(aim)总数

int dynamic(int[] level, int index, int aim) {
    int n = level.length;
    int[][] dp = new int[n][aim + 1];
    for (int i = 0; i < n; i++) dp[i][0] = 1;
    for (int i = 1; i <= aim; i++) dp[0][i] = i % level[0] == 0 ? 1 : 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= aim; j++) {
            if (j < level[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = dp[i - 1][j] + dp[i][j - level[i]];
        }
    }
    return dp[n - 1][aim];

}

这里要注意的是初值的初始化,默认当钱数为0的时候值为1(比如说前面的2张5块的方法F(2, 0) = 1),当只由一种钱币组成时,只要总数能够整除第一种钱币面额就为1(全部由这种货币组成)

动态规划的优化

当然这个优化可有可无,因为我们观察上面的函数,我们发现其实N层只与前面N-1层一个有关,这样的话,我们如果覆盖掉上一层的值对后面的计算结果也没有影响。所以我们就不使用多维数组,直接使用一维数组,节省了(N-1)* (aim + 1)的空间

int advanceDynamic(int[] level, int index, int aim) {
    int[] f = new int[aim + 1];
    f[0] = 1;
    int n = level.length;
    for (int i = 0; i < n; ++i)
        for (int j = level[i]; j <= aim; ++j)
            f[j] += f[j - level[i]];
    return f[aim];
}

所以我们成功的将代码改的更短,而且更省空间

总结

一开始本来想多讲几道动态规划的问题,但是写着写着发现其实大部分都是大同小异,找到子函数,构建表存贮计算过程,其中最大的挑战就是找到分解子函数,所以我就不介绍其他的问题了,我就把这些问题留在下面,你可以试试挑战一下自己

一个背包有一定的承重cap,有N件物品,每件都有自己的价值,记录在数组v中,也都有自己的重量,记录在数组w中,每件物品只能选择要装入背包还是不装入背包,要求在不超过背包承重的前提下,选出物品的总价值最大。

  • 最优编辑

    对于两个字符串A和B,我们需要进行插入、删除和修改操作将A串变为B串,定义c0,c1,c2分别为三种操作的代价,请设计一个高效算法,求出将A串变为B串所需要的最少代价。

  • LIS

求出序列的最长上升子序列的长度

  • LCS

给定两个字符串A和B,返回两个字符串的最长公共子序列的长度。例如,A=”1A2C3D4B56”,B=”B1D23CA45B6A”,”123456”或者”12C4B6”都是最长公共子序列。

  • 走迷宫问题

有一个矩阵map,它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有的路径中最小的路径和。

网上关于动态规划的资料,大部分直接给结论,所以一开始我一头雾水,搞不懂为什么要这么做,这篇博文就从实际问题出发,简单的剖析动态规划

引言

现实生活中总能找到一些问题你没法给出具体答案,比如给你一堆1块、5块、10块的零钱,要你找出多少种能够拼出100块的方法。还有就是迷宫问题这种。这种问题都有一个特征,我们没有办法立刻给出答案,而且我们对这种问题的想到的第一种解决方法就是暴力搜索,把所以的可能方案列出来然后得到答案。这种暴力搜索最终能够解决问题,但是他们在计算的时候花了很多时间在相同的计算上面。为了节省时间,所以我们使用动态规划“优化”暴力搜索

为什么要使用动态规划?

Example

我们先举一个简单的例子,大家都知道走楼梯问题,这也是教科书一个经典的递归程序

  • 有N阶台阶,一个人一次上两个或者一个,问有多少种走法?

我们拿到这道题,我们首先会想这样想,从第一个台阶开始,我们使用递归让这个人走一步或者两步,这样每次分解成为两种可能,最后直达走到N阶台阶,或者迈过去了,然后计算这种所以迈到N阶台阶的可能路径。

这种正向思维很容易理解,但是最终它直接得到的是所以可能的路径,但是这道题我们需要求的是N阶的走法,所以我们从正向思维必须要反过来思考,假如我们从一个台阶出发有两种可能,那么我们到达第N个的台阶来看,也有两种可能,第一种是N-1(迈了一步到达),第二种是N-2(迈了两步到达),这样我们就很清楚了,假如我们要想得到到达N阶台阶的走法总数,那么我们只需要把到达N-1和到达N-2的次数加起来就可以了

这是一个很重要的思想把一个复杂的问题,分解成为其他的子问题,这也是我们完成动态规划的设计的核心思想

从更好的理解动态规划的优点和源头,我们就从这个简单的例子使用不同的算法来解释为什么要用动态规划

暴力搜索法

我们成功的完成了问题的分解,为了完成计算,但是我们还得计算子问题的结果,上面得到一个很重要的公式F(N) = F(N-1) + F(N-2)

我们可以很轻松的写出代码(Python)

def f(n):
  return f(n-1) + f(n-2) if n > 2 else n

我们只用一行代码就能将这个问题解决掉,而且效果看起来还不错,我们可以试不同的n都能获取正确的结果,但是n大于30之后,当我在我的电脑上运行起来非常慢,需要几秒钟才能返回结果,而且当n越大,消耗的时间也越多。

这是为什么呢?我们现在来思考一下这个暴力算法有什么弊端

  • 暴力搜索的弊端

我们现在假设N=10,那么我们现在就把F(10)转换成为F(9)与F(8)的和,那么F(9)又分成了F(8)和F(7),而F(8)被分成了F(7)和F(6)

从这里可以看到,F(7)在第二次分解的时候计算了两次,而每次计算的结果都是一样的,所以我们相当于重复了一遍耗时的操作,知道这个问题,我们就必须改进了,我们可以用一个东西存贮计算结果,这样就不需要重复计算了

记忆搜索法

我们修改我们算法,加一个参数map

def map_get(map, n):
    v = map.get(n-1)
    if not v:
      v = f(n, map)
      map[n] = v
    return v


def f(n, map):
    if n < 3:
      return n
    if n in map:
      return map[n]
    return map_get(map, n - 1) + map_get(map, n - 2)

我们添加一个辅助的字典存贮我们中间计算过程,虽然让我们的代码臃肿了不少,但是让我们代码速度有了质的变化

我们尝试使用运行让N增大到100多都能迅速返回,但是当我们逐渐增大到1000的时候我们会发现Python直接报了超出最大堆栈限制的错误

  • 堆栈超出最大层数的原因

由于我们使用了递归,递归函数是在递归的时候当前堆栈再次申请一个堆栈待,运行递归函数,为了避免一直无限调用下去耗空堆栈空间(申请也需要一点空间),Python限制了递归层数,由于为了计算超过1000的我们必须至少要递归超过1000次(从1000减一减到小于2),所以我们光荣的被当错程序错乱被误杀了。

动态规划

反观我们这个函数,使用递归,我们很容易理解,但是对于计算机来说,只是为了计算一个数而使用递归是非常不划算的,所以我们要思考这些中间值保留有什么共同点,我们从头开始看,对于第三个来说,它只需要知道第一个和第二个的值就行,而第一个第二个我们知道分别为1和2,对于第四个来说,它只需要知道第三个和第二个,如果我们先把第三个计算下来并保留下来,我们就能知道第四个。

从头开始思考我们知道,我们只需要保留前面计算的结果就能知道后面的值,我们使用一个列表保存这个中间计算过程,我们将函数改写成下面这个

def f(n):
    if n < 3: return n
    values = [1, 2]
    for i in range(2, n):
      values.append(values[i-2]+values[i-1])
    return values[-1]

接下来我们运行这个函数,我们会发现就算N为10000都能迅速返回

来看看我们动态规划的“损失”,我们使用了一个列表存贮中间过程,使用了空间“换回”了速度

总结

我们使用了一个很简单的题目来介绍动态规划,由于这个问题太过于简单,你或许自己在不知道动态规划的时候都能写出来,但是这个从暴力搜索到记忆搜索最后动态规划的算法优化过程中,我们能够清楚的知道设计动态规范其实也非常简单,将大问题分解成小问题,然后思考小问题的如何细分,最后反过来思考从小问题逆向到最终的大问题,这就是动态规划。

当然这道问题并不是很经典的动态规划问题,为了让大家更好的理解动态规划,我在下面这篇的博文中介绍若干中经典的动态规划问题

几个有趣的动态规划