

使用链表描述复杂结构
source link: https://zhuanlan.zhihu.com/p/350513130
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

halo 米娜过年好,俺是 132,首先大家过年好哇!大家知道我写过一个叫 fre 的框架,在 fre 中最主要的特点就是使用链表去描述 vdom 树,这是很少见的
今天给大家带来一篇文章,详细讲讲那些传统框架很少见到的,链表这个数据结构
链表替代数组
大家熟知的 3kb react like 框架 preact 最近在进行大重构,使用两阶段的 diff/patch 的新架构
它使用了一个叫做 commitQueue 的数组队列去装载 diff 的结果
另外,preact 还是一个经典的同步递归框架,当然像 vue 等框架也是一样
这就比较尴尬了,因为无论是递归还是数组,都会爆栈
解决爆栈的思路非常简单,就是使用链表和循环
let commitment = null // 构建单向环状链表 for (let i = 0; i < children.length; i++){ commitment.next = children[i] commitment = children[i] } commitment.next = children[0] // 循环遍历链表 let current = commitment.next while (current) { // do something current = current.next }
短短几行代码,就可以将一个数组(栈,队列)转化为一个单向链表
一不需要递归,二不需要数组这种连续内存占用,解决了爆栈的问题,适合大量数据的遍历替代使用
其中在 fre 中就使用了同样的方式,解决了大量节点的内存问题
链表替代树
我们平时看到的前端框架,vue,preact,angular 都是使用 vdom 树或者 idom 树
树是一个非常常用的结构,构建容易,遍历也方便(递归)
同样的道理,当数据量大了以后,无论是内存还是时间,递归的弊端就会很明显,此时我们就需要使用链表了
// 构建链表树 // https://github.com/yisar/fre/blob/master/src/reconciler.ts#L176 for (var i = 0, prev = null; i < bCh.length; i++) { const child = bCh[i] child.parent = WIP if (i > 0) { prev.sibling = child } else { if (WIP.tag & OP.SVG) child.tag |= OP.SVG WIP.child = child } prev = child }
这段代码是 fre 中,将树的数组转化为链表的代码,非常简单
它将第一个孩子变成 child,之后的用 sibling 串联

这个结构相信读过 react 文章的很熟悉,实际上这还是一棵树,只是使用链表去描述了而已
这样的好处是,可以用经典的循环遍历了,除了上面的内存方面的好处,循环还是异步友好的,可以很方便得打断,继续……
// 遍历链表树 // https://github.com/facebook/react/issues/7942 let root = fiber let node = fiber while (true) { // Do something with node if (node.child) { node = node.child continue } if (node === root) return while (!node.sibling) { if (!node.return || node.return === root) return node = node.return } node = node.sibling }
到这里,都是 fre 中对链表的使用,当然主要思路还是来自 react,但在这个满大街的同步框架的世界里,使用链表确实有它的好处,内存优势,异步友好等等
但这还没完呢?
使用双链表去描述 dom 树
大家有想过吗?如果 fiber 不是由框架 runtime 实现,而是浏览器内置,到底需要怎样的硬性条件呢?
很简单,那就是浏览器中复杂的树,比如 dom 树,同样使用链表去描述
写过 html parser 的人都知道,其实我们无论如何拿到的都是一串字符串,我们的遍历从左到右线性的
<div id = root> 132 <br/> </div> [ # # [ ] ] Element > Node > Node > Element > End > End
所以它真是是一棵树吗?不从来都不是,它无论如何都是一串字符串而已
我们使用双向链表同样可以很方便地表述这串字符串的线性关系
const {ELEMENT, ATTRIBUTE, TEXT} = Node const div = new Node(ELEMENT) const id = new Node(ATTRIBUTE) tag.next = id id.prev = div const text = new Node(TEXT) id.next = text text.prev = id const br = new Node(ELEMENT) text.next = br br.prev = text br.end = new Node(br.End) div.end = new Node(div.End)
同样的,我们可以遍历这个链表,来做我们想做的事情
const childNodes = element => { const nodeList = [] let { next, end } = element while (next !== end) { if (next.type !== Node.ATTRIBUTE) { nodeList.push(next) if (next.type === Node.ELEMENT) next = next.end } next = next.next } return nodeList }
到这里,我们基本上是可以利用链表去描述 dom 树了,有了链表,我们在任何循环的地方都可以进行打断了……
其实无论如何,我们需要同步的地方只有两处,一是 js 行为,二是画图行为
不管是浏览器,还是我们自己实现渲染引擎,除了这两个行为之外的所有环节,比如排版,合成,统统都可以异步打断
过去 fre 实在框架 runtime 创造异步条件,那是因为我们没办法控制浏览器
我自己实现渲染引擎,我希望将这部分内容移交给引擎,相反 js runtime 越轻量越好
未来是物联网时代,没人乐意和浏览器玩♂耍了……
总结
其实说实话,我们使用链表而不是使用树,并不是看上了性能,至少我是对性能完全无感的,都什么年代了,还追求那点点时间
但是写树真的写腻了……尤其是渲染引擎这种复杂,大型的东西,数据结构一旦确定下来,就很难撼动了……
我希望从一开始就站在至高点,不要说什么先整个简单的,后续再重构……这是不现实的,越重要的东西越是从一开始就得确定好
最后大家过年好!年后一起搞事情鸭!
Recommend
-
41
比起晦涩复杂的数学或文本描述,也许代码能帮助我们更好地理解各种卷积模块。计算机科学家 Paul-Louis Pröve 用 Keras 对瓶颈模块、Inception 模块、残差模块等进行了介绍和代码说明,并在最后留下了 AmoebaNet Normal Cell 代码实现的练...
-
36
一、链表简介 1、链表概念 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,节点可以在运行时动态生成,节点包括...
-
18
本文源码:GitHub·点这里||GitEE·点这里一、链表简介1、链表概念链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,节点可以在运行时动态生成,节点包括两个部分:一个是存储数据元...
-
19
第8节提到 linux 中,进程不仅是执行期的程序,它实际上是各种资源混杂的集合,那么“各种资源”究竟是指什么呢?这里不打算一句一句描述出“各种资源”,因为直接查看代码更加清楚。用于描述 linux 进程的 task_struct 结构体lin...
-
15
还记得刚开始接触 C 语言的时候,为了描述一个平行四边形的边长和对角线长,我定义了四个变量:短边长 a,长边长 b,对角线1长 d1,对角线2长 d2。在写代码的过程中,发现又要定义一个平行四边形,于是我不得不又定义了四个变量:a2,b2,d12,d22,结果变量又...
-
7
链式存储结构之双向链表与跳表-五分钟学算法 当前位置:五分钟学算法 > 数据结构 > 链式存储结构之双向链表与跳表 ...
-
8
线性表链式存储结构之单链表-五分钟学算法 当前位置:五分钟学算法 > 数据结构 > 线性表链式存储结构之单链表 ...
-
3
JZ-025-复杂链表的复制发布于 12 月 14 日复杂链表的复制输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个...
-
9
百图画鸿蒙 | 一图一主干 如果把鸿蒙比作人,百图目的是要画出其骨骼系统。 双向链表是内核最重要的结构体,说它怎么重要都不为过,其插入删除操作被内核高频,灵活的使用,若不理解透彻在分析源码过程中很容易卡壳...
-
5
讲一些CLR里面的内存模型。本篇MethodDesc,意为函数的描述之意,看下一个函数在CLR里面是如何被描述的。 MethodDesc结构 这个结构体在CLR里面高达1600多行,这里仅截取一些 class MethodDesc { friend clas...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK