① (六) 概率演算法
前面所討論演算法的每一計算步驟都是確定的，而本次所討論的概率演算法允許演算法在執行過程中隨機地選擇下一個計算步驟。在許多情況下，當演算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此概率演算法可在很大程度上降低演算法的復雜度。
概率演算法的一個基本特徵是對所求解問題的同一實例用同一概率演算法求解兩次可能得到完全不同的效果。這兩次求解所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下， 可將概率演算法大致分為四類：數值概率演算法、蒙特卡羅(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)