① (六) 概率算法
前面所讨论算法的每一计算步骤都是确定的，而本次所讨论的概率算法允许算法在执行过程中随机地选择下一个计算步骤。在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。
概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下， 可将概率算法大致分为四类：数值概率算法、蒙特卡罗(MonteCarlo) 算法、拉斯羡孝陵维加斯(Las Vegas) 算法和舍伍德(Sherwood) 算法。
随机数在随机化算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在随机化算法中使用的随机数都是一定程度上随机的，即伪随机数。
线性同余法 是产生伪随机数的最常用的方法。由线性同余法产生的随机序列 满足
其中 。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得充分大，因此可取m为机器大数，另外应取 ，因此可取b为一素数。
为了在设计概率算法时便于产生所需的随机数，建立一个随机数类RandomNumber：该类包含一个需由用户初始化的种子randSeed。给定初始种子后，即可产生与之相应的随机序列。种子randSeed是一个无符号长整型数， 可由用户选定也可用系统时间自动产生。函数Random的输入参数 是一个无符号长整型数，它返回 范围内的一个随机整数。函数fRandom返回[0，1) 内的一个随机实数。
数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。且近似解的精度随计算时间的增加而不断提高。在许多情况下，要计算出问题的精确解是不可能的或没有必要的，因此用数值概率算法可得到相当满意的解。
当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时
舍伍德算法就是一种利用随机算法改造确定性算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏情形行为与特定实例之间的关联性。
思想：利用随机算法改造已有算法，使得算法的性能尽量与输入数据无关，即平滑算法的性能。它总能求得问兄戚题的一个解，且求得的解总是正确的。
算法的性能 =平均性能 + 一个很小的随机值。 舍伍德算法是为了得到好的平均性能。
一个算法，对于不同的输入数据，其算法的性能是不一样的。比如快排算法，每次选择第一个元素作为基准，慎带对序列从小到大排序：
拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法会找不到解。
与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。
蒙特卡罗算法用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。
用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点也在于此。一般情况下，无法有效地判定所得到的解是否肯定正确。
在实际应用中常会遇到一些问题，不论采用确定性算法或随机化算法都无法保证每次都能得到正确的解答。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。
有些蒙特卡罗算法除了具有描述问题实例的输入参数外，还具有描述错误解可接受概率的参数。这类算法的计算时间复杂性通常由问题的实例规模以及错误解可接受概率的函数来描述。
参考链接： http://www.ruanyifeng.com/blog/2015/07/monte-carlo-method.html
数值概率算法的应用
舍伍德算法的应用
拉斯维加斯算法的应用
蒙特卡罗算法的应用
② React的diff算法详解
一、什么是diff算法？
为了增强用户体验，React从版本16开始将 同步更新 重构成了 可中断的异步更新 ，即采用了新的Reconciler(协调器，用于找出变化的组件），而新的Reconciler中采用了fiber架构。fiber架构的原理在此不再详细解释，我们目前只需要知道fiber节点可以保存dom信息，fiber节点构成的树叫fiber树，而更新dom是要用到‘双缓存技术’，即比较旧的fiber树与此次要渲染的jsx对象，返回新的fiber树进行渲染。 在旧fiber树与jsx对象比较时，决定哪些节点要复用的过程，就是diff算法 。
由于diff本身也会带来性能消耗，为了降低算法复杂度，React对diff做了 三个预设限制 ：
更新后
如果没有key会走第二条限制，有了key，react就可以判断div和p节点是存在的，可以复用，只需要交换顺序。
diff算法会根据不同的jsx对象执行不同的处理函数，根据jsx对象的不同，我们可以分为两类 ：
1.JSX对象（之后都用newChildren表示）的类型为object、number、string，代表同级只有一个节点
2. newChildren的类型为Array，代表同级有多个节点。
二、单节点diff
对于单节点diff，用一个流程图就可以解释
更新后
由于 key的默认值为null ，所以更新前与更新后满足key相同且元素类型不同，那么我们要删除更新前的三个div节点，新增p节点
三、多节点diff
对于多节点diff, 我们要 遍历newChildren和oldFiber 进行比较。由于React团队发现dom节点一般有更新，增加，删除这三种操作，而更新更为频繁，所以他们设置更新的优先级高于增加删除。基于以上原因，在多节点diff算法的实现中有两层遍历， 第一层遍历处理更新的节点，第二层遍历处理更新以外的节点 。
第一层遍历
遍历newChildren与oldFiber, 判断节点是否可复用，如果可以复用，则继续遍历。
如果不能复用，分为两种情况：
第二层遍历
第二层遍历从第一层遍历的结束位开始
第一层遍历结束后有4种结果
首先我们要判断newChildren中遍历到的节点，在oldFiber中是否存在，基于此，React将oldFiber中的节点以key-oldfiber 键值对的形式存在Map中，只需要newChildren的key，就可以判断oldFiber中有没有相应的节点。
如果oldFiber中没有相应的节点，则将newChildren生成的fiber打上placement标记
如果有相应的节点，将它的索引记为oldIndex，与上一次可复用节点在oldFiber的索引位置lastPlacedIndex比较，如果每次可复用的节点在上一次可复用右边就说明位置没有变化 ，即
若 oldIndex >=lastPlacedIndex, 说明相对位置没有变化 ，那么令lastPlacedIndex=oldIndex
若 oldIndex<lastPlacedIndex, 代表本节点需要向右移动 。
例如:
参考文档 ：
React技术揭秘 (iamkasong.com)