00:01
这节课我们来学习diff算法的子节点更新策略。那么可以说第步算法最美的啊,就是它的一个子节点更新策略了,就是咱们之前课程当中五角星那部分的内容啊,五角星那部分的内容啊。好,那其实这部分内容呢,还是挺简单的啊啊,咱们还是举例说明,但是呢,老师呢,先去把他的一个最终的一个结果啊告诉大家。递算法当中呢,提出了这样的四个指针啊,叫四种命中方式啊,四种命中方式,四种命中或者叫命中查找。哎,命中查找啊,这不叫命中查找,叫命中查找,第一个呢,咱们叫做新钱与旧钱。啊,新前与旧前好,第二个呢,我们就管它叫做新后与旧后。
01:02
哎,第三个我们管它叫做新后与旧前。好,第四个呢,我们管它叫做新前与旧后。啊,这样子的,那什么叫新钱呢?新钱就是咱们新的虚拟节点当中的啊,啊,所有没有处理的开头的节点啊,什么叫没有处理,咱们的前面一个视频已经讲过了,那么先后呢,就顾名思义,就是所有新的虚拟节点当中的子节点当中没有处理的节点的最后一个节点,对吧?哎,那么就前就后呢,是一个意思。可以这么说,这种命中查找方式呢,并不是拿包的独创,它是DF算法啊的一个呃,一个非常非常的一个古典,或者说叫做经典的一个地啊算法的一个呃,优化策略。啊,因为大家知道。
02:00
包括咱们的git,大家知道G吧,是不是都要比对咱们前后文件的区别呀,A文件和B文件有什么区别呀,那么实际上都是在进行diff。啊,包括咱们的这次的这个虚拟节点的地方。那实际上这个dif算法呢,并不是sna bottom啊,再去给你进行的,不是那bottom在进行的啊,而是什么呢?而是dif传统的这个优化策略,所以呢,面试的时候呢,面试官经常会问你这个大家一定要把这个顺序记住,这个顺序是从前往后,呃,测试命中的,命中的一个就不带测试了啊,命中没有命中一就测试二,没有命中二,测试三,没有命中三就测试四,然后四也没有命中,最后就循环啊,什么意思,咱们一会通过案例来找啊,案例给你演示。那这种算法为什么优秀呢?因为它符合咱们人类经常的编程习惯。啊,咱们比如说新的。啊,可能就在对尾增加了一些东西。
03:03
你看A和A命中了,B和B命中了,C和C是不是就就相同啊。对吧,然后就在对尾就经常。对吧,还有的时候会怎么样呢?对待对手会增加一些东西。啊,对手会增加一些东西,看见没有好,然后咱们这个例子,咱们不光在对手增加一个E,也得对尾增加一个D。看见了吧,哎,然后把这个新的,咱们现在用更淡一点的灰色啊,更淡一点的灰色,咱们给他告诉你这是新的,或者咱们把这新的加上边框。咱们把语速放慢,好好的给大家讲讲啊,好好的给你们讲清楚啊,这是。呃,因为大家可能上网也看了一些视频,但是呢都不是特别清楚,所以这个时候呢,咱们老师啊,哎,还是有责任给你讲的更清楚一点啊,就这样子的。那么现在这个问题来了,就说为什么这个算法好,因为这个算法呢,他能把咱们人类经常出现的这种情况对吧?哎,然后给他考虑到,并且呢,不经常出现的,他也能够包圆,那什么叫新钱旧钱什么的,咱们别卖关子了,咱们开始给大家讲啊。
04:13
就是咱们现在呢,要去准备四个指针。啊,这个呢,就叫做就钱。哎,四个指针啊,四个指针你没有听错,然后面试的时候呢,经常会有面试官呀,考你这四个指针。知道吧,哎,所以大家一定要会啊,这个叫救后。好,那么同样的这边呢。哎,这叫心钱。好,然后这个呢,叫做新后。四个指针啊,四个指针。那现在的话呢,我们来看到底什么意思啊,咱们先看这种情况啊,就是新增的情况,哎,这两种都是新增的情况,怎么玩呢,特别有意思啊。就是我们要用新钱与旧钱啊,这两个节点呢来进行对比。
05:05
对比新钱和旧钱呢?是不是同一个节点?啊,是不是same的,如果是同一个节点呢,那就说明我们是不是就已经找准了,它不是新增,他也不是删除,它是不是就是更新啊。对吧,那更新的话,我们之前是不是已经讲解过那个patch v no的还记得吗?就是pat vno的本身不就能更新吗。对吧,哎,咱们先把这删除掉啊,咱们刚才这个if语句,这其实就是尝试写的啊,尝试写的话我们就可以删除掉。哎,就尝试写的啊,等于说现在我们这个按钮一点又没用了。啊,又没用了,对吧。哎,那怎么回事呢?那现在的话就是研究研究它怎么办,就是新签与旧钱位置相同,好,那这个时候呢,我就不需要执行节点移动操作。对吧,我这个时候就只需要更新这个节点就行。
06:01
那只需要更新这个节点就行啊,那这个时候就命中一了。明白吧,哎,命中一的话我们就不再说了,命中一的话大家注意听啊,我们就不再呃,不再判断二了啊,大家一定要记住,就是命中一就不在命中二。啊,命中一就不在命中二。那么这个时候呢,你看新钱和新钱,呃,旧钱和新钱是同一个节点,那我们就要更新他们,当然更新的时候,他会发现文字也一样,就什么都不用动,对吧?那这个时候呢,它指针就会移动,它不会比较二啊,咱们说了命中一种就不再继续命中判断了啊,这个一定要记住哦,咱们把这写上就是命中一种就不再啊进行命中判断了啊,就对于这个节点就不再进行命中判断了,如果命中不了就顺序判断啊,所以这个时候旧前指针会往下移,新前指针呢也会往下移。
07:02
前指针只会下移,后指针呢会上移,但是这里后指针不上移啊,因为这时候咱们是一号命中对吧,就是命中这个一号了。啊,那这样的话呢,你看就要开始比较这个和这个啊,那一看这俩K都相同对吧,选择器也相同,那么就说明他俩是同一个节点。那么这个时候呢,他就不再判断二了,这种情况他就会诶往下移,它呢也会往下移,好,它是不是也是相同的呀。发现没有,是不是也相同,所以这个时候旧钱呢就会往下移,新钱也会往下移,好那这个时候的话,注意循环就会结束了,为什么呢?因为咱们的循环执行条件呢,是新钱啊,就钱永远是在钱啊,就两个钱都要在钱的情况,是且的情况。也就是说循环它的条件会这么写啊,就是当咱们的心前小于心后。啊,然后且就钱。
08:04
小鱼就后。哎,小于等于啊。就等于说相同的时候,它也会判断一次。啊,直到抄下来了,这是循环。那这个时候循环就结束了,那你说老师不对呀,循环怎么结束了呀,循环结束了,你这俩还没有判断出它新增呢,对,这就是咱们这个算法的牛逼之处。就是只要是你的旧节点,先循环完毕了。那么这个时候就说明你新的children准当中的啊,就新的节点当中的children准当中是有剩余的节点没有被变历的。那不就说明这两个节,这两个指针之间的节点是所有需要被新增的节点吗?这大家能听懂吗?对吧?不就是说明这两个节点之间的节点是需要新增的节点吗?那直接把这个节点这些节点插到DOM当中不就可以了吗?
09:02
能明白吗?不就是这个意思吗?对吧。所以说我们把把这句话给大家写上就是。如果是咱们的就啊旧的节点先循环完毕,循环完毕,所以说循环里头我要判断。啊,就这个循环结束之后,我要判断啊,先循环完毕,那这个时候什么呀,就说明我们的是不是新的这个节点中是不是有要插入的这个节点啊,所以这两个指针当中呢,就是要插入的。明白了吗?好,那你说老师,那如果是删除的情况呢。咱们来看删除的情况啊,咱们比如说一开始是abcd。对吧,好,那最后变成。啊,最后变成这个abcd啊,然后最后变成abd了。C、没了。咱们来看看这样的情况会怎么样。注意看啊,注意看啊。删除的情况。对不起,这个是金钱。
10:02
首先前前比。是不是命中?哎,指针下移。好,然后前前比是不是又命中啊。哎,然后指针加一。看见没有,哎,然后这个时候前前笔是不是没有命中。啊,因为前和前比一个C一个D也没命中啊,但是这个时候他就开始用后后比。一定记住啊,新前旧前新后旧后新后旧前新前旧后,一定记住这顺序啊,这前后是好背,然后这个是先新后旧前啊,哎,这个要刻意背一下,然后新前与旧后。啊,所以这个时候前前比完之后,他这个时候让后后比。那后和后比是不是命中?对吧,那厚厚比命中的话后就会往上走。啊,命中了后节点就会往上走,后节点就会往上走,能理解吧,好,往上走了。啊往上走,那这个时候就破坏这个循环规则了,那这个时候是不是咱们就知道了,就是谁先循环完毕的,对谁先循环完毕,是不是新节点先循环完毕啊,就是如果新节点先循环完毕,那么时候就说明什么,就是如果你的老节点中。
11:15
老节点中啊。对吧,哎,还有还有剩余节点,还有剩余节点还有啊还有。还有。啊,这个剩余节点,剩余节点就指的是他俩之间的,那他俩之间不就是它吗。对吧,那只不过很巧,咱们删了一个,一会删除多个项你就知道了。明白吗?哎,就需要他们是要被删除的节点啊,就说明他们是要被删除的节点。看懂了吗?哎,他们是要被删除的节点,就这么简单。发现了吗?那你说老师你这个是特例啊,你这个是特例,那特别复杂的情况呢。特别复杂的情况,那比如说咱们现在说是是呃多删除情况咱们来看。
12:01
比如现在是abcd啊,然后咱们再拿一个E。好吧,哎,Abcde啊。好,然后abcde,我们现在呢,还是变成了abd,好吧,哎,就是把C和E删了。好,那咱们现在把这个指针摆好,我们先来研究研究到底会发生什么事啊。咱们琢磨琢磨呀。心前心后命中。所以下一。对吧,哎,下移了。好诶,对不起对不起,就开始瞎讲了啊,这样啊,新钱旧钱命中,所以下一行。旧钱新钱,命中所以下矣。没问题吧?是吧,没问题吧。然后旧钱新钱没有命中。没有命中的话,不是下移也不是上移,而是命中二啊,开始尝试二号命中。能不能理解开始长号尝试二号命中,所以这个时候呢,他就要尝试旧后与新后是不是命中,是不是没命中。
13:05
没命中也不是上移啊,而是尝试三号命中啊。这个大家能理解吧,哎,而是尝试三号命中,三号命中就是新后与旧前啊,这个页面我先删掉这个,呃,这页面先删掉啊,新后与旧前。那新后是什么?新后是不是就是他,旧前是不是,他是不是也没命中好没命中的话,我们来看新前与旧后。啊,那就是新前与旧后是不是也没命中啊,那注意啊,四个如果都不命中,不意味着就崩了,不意味着循环结束,而是此时要用循环来寻找。懂了吧,哎,如果都没命中,那么就需要用循环来寻找,就是如果都没有命中。啊,那么就需要用循环啊来寻找了。哎,就就是为什么为什么都没有命中,因为你现在删的他是他把你看啊,你现在正经的是把C和E删了,其实这在实际工作中很少很少见,他删的不是头像,也不是尾像。
14:05
他他尝试了四次命中,已经尽力了,那这个时候就需要用循环来去啊寻找了。好,那这个时候呢,就会去循环旧节点对吧,我们在旧节点当中看看有没有D啊,那发现了有D啊,有D的话呢,它就会把这个D移动到新的位置,就这个D现在就会被移动到新的位置,实际上在呃咱们的呃这个呃就还有view view的源码当中呢,就会给他设成安D范了。明白吧,哎,就会就是你发现这个D和这个D找到了,那那好就说明你这个D现在发生了移动位置。对吧,那你说老师不就是删除吗?怎么是移动位置,实际上他现在会先判断成移动位置。啊,会判断成移动位置,因为你现在这个D找到了一个D对吧,然后这个D它是位于第零项,它是位于下标为0123的项,它是会给它判断成移个移动位置。啊,移动位置就等于说浪费了一步操作,但是呢,这是没有办法,哎,然后他就会在这里呢,会去给他标记成一个安迪范的,我们在这里打一个标记。
15:06
哎,就是真实盗墓就会给他移动位置,但是虚拟盗墓呢,就会给他打上一个安迪范的标记一下,就标记一下它啊,把这个东西给标记一下安迪范的了,就是把这个力啊,咱们这样拿一个长长的小点字给它盖住。居中对吧。哎,再小一点啊,就给他给他蒙住啊,就告诉你他变成安迪绊子了,然后这个时候的话,这个呃,这个这这这这个这就相当于没了,然后这个时候他这个因为我们不是在这里寻找了嘛,对吧,所以这个前指针就会往后移。啊,那这个时候是不是循环条件就终止了,不符合循环条件了。对吧,那不符合循环条件的时候,我们刚才说过,是不是前旧的前后节点中间如果还有节点,是不是就要被删除的节点。发现了吗?C和E是不是就被删除的节点?啊,因为安迪范已经安迪范了,不用管他。所以C和E就要被删除的节点。
16:02
发现了吗?很神奇吧,哎,很神奇,就老真的还有剩余点,剩余点点什么意思,就是就是咱们的旧前和新后指针卡住的节点,就是旧前和新后指针对吧?哎,卡住的节点啊,就是中间的。节点。他们就要被删除,多神奇啊,那其实你仔细一想,他也不神奇。啊,你仔细想不审计为什么,因为他这种优化策略实际上不是不是。一个什么特别,就是不是什么唯一的那种优化策略。啊,它只是一种按照咱们人类平时想的。啊,想的就是容易发生的那种更新,然后提出的这种四种优化策略。但是呢,他这种四个指针的思路是非常好的。四个指针的思路是非常好的。对吧,因为你如果没有四个指针的话,你这块会很乱,而四个指针的话,你看没看见它这个指针只往后移,这个指针只往前移,这个指针只往后移,这个指针只往前移,它就只需要变利,就两个同时变利,对吧,它就特别的美,特别的大方。
17:08
好,我们再来看呃,比较复杂的情况啊,比较复杂的情况呢,就是我们这回啊,刻意营造一下,让新后与旧前,还有新前与旧后啊也能命中一下是吧,然后来看看这里头有什么啊门道啊,这头有什么门道,好,咱们来看这个abcde啊,要变成ecm。对吧,哎,咱们故意营造一下一个一个一个感觉啊。首先你看前前匹配啊,没有民众。然后是厚厚匹配。是不是也没有命中啊,好,然后接下来呢,是谁呀,一定要看好顺序啊,是不是新后与旧前呀。就是新后与旧前,哎,也没有命中,然后是不是旧后与新前。对吧。哎,就是新前与旧后,那这个时候有没有有命中了吧,对吧,新前与旧后是不是命中了,那么大家一定要记住啊,当新前与命中的时候呢,新前与旧后命中的时候啊,那这个时候呢,他一定一定要记住这个就是啊圈四命中的时候,这个时候要移动节点。
18:13
因为他俩要他俩命中了呀,要移动节点。对吧,那当新前与旧后命中的时候啊,就是当。四这个规则。啊当四就是新前与旧后。哎,命中的时候,那么此时呢,要移动节点。就移动我们这个心啊,心前指向的这个节点,指向的这个节点干什么呢?移动到哪里啊。到老节点没有处理的啊,老节点没有处理的,节点的最前面。啊,老节点的,也就是说就前的前面。懂了吗?啊,我这时候需要移动它。所以这个时候这个E这个节点呢,它在咱们这个虚拟的这个这个上面啊,虚拟的这个。
19:03
上面上它就没有了。对吧,他就没有了。哎,咱把这个安迪范啊给它遮住,那就相当于虚拟节点没有了,但是呢,真正的盗墓节点被移动上来了,这个E啊就移,诶对不起,它没有了啊,哎,E就移动上来了,移动到就前的最前面。啊,这是这样子的。那咱们现在先先不讲,先不继续讲啊,咱们先讲讲一会咱们要说的一个更复杂的情况,就是abcde和这个啊,他倒过来了,那一会那个老师要给你讲一个圈三,就是当。三的时候啊,所以这算法特别精妙,就是当新后语旧前的时候,命中的时候,先后语之前不是圈三吗。那么此时要移动新钱指向的节点,到老节点旧节点的啊,到老节点,所有没处理节点的最后面。啊,就是他这块是变了的。他这是变的,要到O的初准中所有未处理节点的最后边啊,也就是说要到最后的就后的后面。
20:07
看见没有?所以他俩是不一样的啊,所以说你千万不要以为,呃,这个这个。很简单,它是不一样的,懂了吧,哎,它是不一样的,这样子的一个情况。明白吧,哎,是这样子的。所以这个时候就是说当圈四新前与旧后命中的时候,此时就要移动节点,那现在不就命中了吗?对吧,那就给他放到所有啊老节点的旧前的前面好,然后这个时候由于咱们是啊,就是新前与旧后命中,所以他呢就要诶往后移,他呢就要往前移,因为他俩都处理过了。然后这个时候继续前前。没命中后后没命中,然后是什么?然后第三个一定记住是新后与旧前啊,然后就是新后与旧前。没命中,然后是新啊,新前与旧后。对吧,新前语句后又没命中,那都没命中的时候,此时怎么办?对他就会用循环语句进行查找。
21:06
啊,他就会用循环语句进行查找,循环语句这个时候就会找啊找什么找这个C啊,哎,就找到C了,所以就会给这个C加上一个这个按半标记。明白吗?然后这个时候会把C插入到什么?对,插入到所有没有啊,就前节点之前一定记住,而不是他之前是插入到旧钱指针之前,所以这不是不卡了个地儿吗,就进来了。看见了吗?是这样子的,然后他就处理完了,向后移这边指针,这边指针不用移,因为这边指针没有命中啊,就这个C命中了呀。看见了吗?哎,C就命中就行了。所以这样的话,你就会发现M,然后他就会比前前没命中,后后没命中,然后是新后对吧?诶确认一下啊,新后与旧前没命中,然后新前与旧后,新前与旧后也没命中,那就需要找。
22:00
对吧,找的话发现M没有,这边没有M没有M吧。没有M,对呀,所以他就会把M插入到所有旧节点之前。看见了吗?M插入到M旧节点之前啊,插入到所有的这个旧前所有新节点之前吗?对吧,这样子,然后新钱就处理完了,它处理完这M了。处理完M之后就结束循环了,结束循环之后,我们刚才不是说过吗?就是如果新节点先循环完毕,老节点中还有剩余节点。对吧,那么这个时候就说明他们是要被删除的节点,所以abd就要被删除掉。这个安迪范的不用管,安迪范的已经死了,就是安迪范,什么意思?安迪范是指的是在虚拟节点中它变成安迪范了,但是在真实盗墓节点中呢,他已经被插入到前面去了。看见了吧,哎,就是他已经被插入到这个前边去了,是这样子的,所以这块我就给他糊上了一层绿布,安迪范的啊,他死了,哎,死的死得其所是吧,哎就就死了,是这样子的,所以这块大家一定要看懂,所以abd呢就被删除掉了。
23:04
对吧,那咱们再来讲这个复杂的例子,这个复杂例子讲完之后我们就不讲了,就不举例了,就基本够了啊,你只要把老师上课PPT这几个情况看懂,你就明白了。对吧,哎,那咱们总结一下,先把这个三总结一下,一定记住啊,当这个三的情况就是此种情况发生啊,四这种情况发生了,此种情况发生,哎发生了,那么要怎么样?对,是不是要让咱们新钱指向的那个节点,新指向的节点移动到就前之前。明白吗?哎,旧前之前啊,那这个情况发生了,是要干嘛呀,把新指新前指向的节点移动到旧后之后。我先把结论告诉你,然后咱们告诉怎么回事啊,然后咱们给大家讲解怎么回事,咱们拿这个例子来讲解,这个例子特别极端,Abcde这边变成了abcde。
24:00
啊,咱们要给大家讲讲三这种情况好了。首先前前没命中,然后后后也没命中,然后这个时候是不是就是新后与旧前呀。对吧,新后与旧前命中了。新后语旧前命中的时候一定记住。他这个时候会移动节点啊,同时给原节点设一个安迪万的,就给他设了一个迪万的。哎,它会移动节点,但移动节点不是瞎移,它这种情况是移动到老节点的后面。就他这个时候A呢,就跑到这了,看见没有A就跑到这儿了。A就跑到这儿了。这样的。对吧,然后不是他俩命中的嘛,所以他也会移动,它也会移中懂了吧,然后接下来就是前前没命中,后后没命中对吧?然后是这边的前和后没命中啊,哎,不对,然后是什么,然后是是什么来着啊,然后新后与旧前咱别串啊,然后新后与旧前没命。啊,命中了,C后语命中了,谁说没命中,命中了命中之后怎么办?对他发现又移动节点,他就把它给设成安迪半了,就移走了,移走之后他在所有没处理的后面。
25:05
看见没有,所有没处理的后面那是不是就这啊,让个位置不是这儿。所有没处理后边就是旧后的后边这个A是在那stand by呢,在那就位呢,他是不是给在这个人的后边腾一个位啊。懂了吧,哎,然后这个节点就上去了,这个节点下来了,看懂了吗?然后接下来又是那种圈三匹配。那就给他糊上了。对吧,然后。他俩前头对不对,哎,又来个C。看见没有,哎这样子的,然后他就弄了,他就这个了。那就再去诶啊,这个前是往后移的对吧,这个再往上移啊,就别下移对吧?哎,到这儿了,他又糊上了这个地。就上来了。啊,然后最后一步也写了吧,来吧,他也到这了,他也到这了,一。那不是两边同时变便利完了吗?对吧?当然如果这边多了一个节点,比如上面多了一个节点,那这个时候他就会发现新增了,新增的不就加进去就行了,也加到旧后之后吗。
26:04
对吧,因为你要判断是谁先结束谁后结束,所以这个节,所以它这个可能性非常的多啊,就圈一圈二圈三圈四,你要移动节点移动到哪里,它这个可能性非常的多。那可能性非常的多,怎么办啊,没关系,你在写代码的时候,你过一过脑子。哎,一定要知道,但是面试官在让你描述的时候啊,他面试官不可能发个笔记本电脑,说你给我写写吧,把第一步算法你给我写写吧,那四种。对吧,但是你一定要能跟面试官说出来啊,新前旧后,新后旧后新后旧前新前旧后啊,然后呢,尤其是你要注意,就是当三和四发生的时候,这时候要涉及移动字典。啊,那么就涉及移动节点对吧,涉及移动节点。哎,那么这个也是涉及移动节点。啊,一定记住三是就后之后,四是就前之前对吧?哎,那么现在这节课的这个PPT啊,大家尽量啊,你们也开一个PPT软件啊,你们也打开一个PPT软件。
27:03
明白吗?哎,你们也是在这个PPT上,大家伙啊,你们也是在这个PPT上努力。啊,努力拿拿PPT也去。把这个算法比比啊,把这个算法自己拿这个PPT上去比一比,你就能明白了啊,你就真的就恍然大悟他是怎么回事了。好吧,哎,你就能恍然大悟他是怎么回事了,好吧,啊,然后嗯,咱们有一句说一句啊,就是大家如果光听那是不行的,一定要动手做,动手做之后呢,你就会觉得,哇,这个玩意儿真的很美好吧,哎。
我来说两句