fre v2.5 基於 LCS 的 diff 演算法

語言: CN / TW / HK

好久不賤!俺回來了……快過年了,之前說 fre 玩完了,但是還是很不甘心

於是……俺又重寫了一波,兜兜轉轉又一年,最終還是實現了最初想實現的演算法

fre 也算是把所有演算法都搞了一遍

fre1:簡單的 keymap 演算法

這也是 diff 演算法最簡單的版本,react 目前的演算法就在這個階段,因為 fre1 主要以抄 react 為主,所以也只是實現了最簡單的版本

fre2.0:指標碰撞 + keymap

這是 fre 做的第二個演算法,在 keymap 的基礎上增加了預處理,這也是 vue2 使用的演算法,但是由於單向連結串列遍歷的順序限制,這個演算法寫到最後,覺得不優雅就放棄了

fre2.3:基於 LIS

這也是前端框架中最常用的一個演算法了,vue3、inferno 等框架都用了這個演算法,我為了將它在 fre 中復現,使用了倒序遍歷的奇技淫巧,甚至還搞出來了離屏渲染……最終各種騷操作加成下,可以說搞定了,但程式碼也變得很亂了

fre2.5:基於 LCS

lcs 和 lis 是同一種演算法,合稱 LICS 演算法,他們的複雜度都是 O(nlogn),前端框架世界裡普遍使用 lis,其實是同一份程式碼互相複製貼上……fre 2.5 中使用了一種 lcs 的演算法變體,將 lcs 演算法用於連結串列中,比 lis 要優雅得多,因為沒有一個 indexmap 的對映,要知道連結串列這玩意,一旦涉及到索引就頭大……

LICS 變體

其實 lics 演算法有許多變體,在過去我研究過許多,現在也快忘得差不多啦,之後有機會再來 bb

why fre?

fre 不快,也不好用,服務也不好,功能也不全……

摸著胸來說,我是不建議將 fre 用於生產的……

但是!至少對我來說,fre 是一個一直放不下的框架,我搞小程式,搞跨端,搞渲染,都離不開 fre 的經驗

同樣的道理,fre 現在 300+ pr/issue,已經有許多人從中發現了神奇的祕密

接下來,我還會繼續借助 fre 做更多客戶端的事情

放個地址:

https:// github.com/yisar/fre