• 正常人，有头发，不穿格子衫
• 本科材料，半路出家的 Web 程序员
• 自顶向下生长的开发技能树
• 最近想要学习算法和 Android 开发
• 会弹吉他，但是完全看不懂五线谱
• 想把头发染成蓝色的，但是被价格劝退
• steam 喜加一党，开放世界游戏党，Minecraft 挖矿平地爱好者，被铁拳锤爆的退坑安娜玩家
• 喜欢村上春树的小说，忠实的 Kindle 泡面用户
• Windows / MacOS 双修，但其实更希望完全使用 Linux，因为 Ubuntu 有好看的主题（划掉）

其实折腾博客很久了，但一直没输出什么像样的文章。很多笔记或者想法都是保存在本地自娱自乐。当然一方面是因为懒，但主要还是因为没做出什么像样的东西出来。毕竟总是觉得手头做的这些东西根本不值得写成文章分享出去。

后来在微博上读了一篇工业聚的文章。

然而实际上，不管是开源还是 TS，它们其实是渐进的、有层次的，呈现的不是非黑即白，而是一段光谱。

…

你可以随意开源，即便跑不起来，即便没有单元测试，即便你连什么是代码覆盖率都不知道。

你可以去写 TypeScript，即便仅仅是把 .js 后缀改成 .ts。对刚开始的你而言，不改一行代码，你也已足够 TypeScript。

你可以在光谱的最左端停留，这是你的起点。等你变强之后，你可以提升你的项目的完成度和质量，往光谱的右侧移动。

每个人都需要经历起步阶段。所有项目都有希望变得更好，不管当前处于哪个阶段。

…

希望你能成长起来。

深受鼓舞，于是决定重新开始。

大概就是这样。

简述

尽管我们可以从逻辑上简单的将 Vue 的实现拆分为：响应式系统和渲染器。因为现代前端框架所关注的问题就是如何同步 state 与 UI。

但在实际工程中，UI 的渲染并不是一次性的。根据数据的变化，它是会随之不断变化的。从理论上来说，我们可以对数据的变化应收尽收。也就是说，只要 state 发生了变化，我们就去更新 UI。这种罗永浩式不管不顾的做法尽管也不是不能用，但却会大大降低渲染更新的速度。所以我们就需要一种机制，来控制渲染。

任何逻辑只要足够通用、足够复杂，就有价值抽象出来单独研究。

另外的，调度器与调度策略是一个很复杂的问题。在操作系统设计中，你可能看到过很多精妙的设计与研究。这里我们并不打算过于深入这个主题，而是恰到好处的阐述，来完成我们的工程目标。

引子

如果你使用 JavaScript 或 TypeScript 开发，那你就不能不去了解运行它们的环境。我们可以笼统的将运行环境区分为浏览器和 Node.js。在这篇文章，我们的讨论范围仅限于浏览器中。

一个在展开讨论前的必要信息是：JavaScript 是一个单线程语言。这意味着在任何时候，都只能有一个主线程来处理任务。事实上这个设计不能怪 Brendan Eich，JavaScript 语言的设计者。他当年捣鼓这个东西的时候，也没有想到互联网能发展成今天这个样子。

如果我们考虑单线程这件事，我们会意识到，这个设计会带来灾难性的后果。比如用户在网站上发起了一个网络请求，这个网络请求所需要的时间可能长达几秒，在这期间，整个网站的渲染线程是被挂起的，从用户的角度来看，网站就像卡住了。这种浏览体验可能是所有用户都不愿意见到的。

说到这，你可能会想：不对啊，我平常上网怎么没遇到过这种情况？的确没有，这就要归功于 Event Loop 了。
简单来说，Event Loop 这个设计，使得浏览器可以将 JavaScript 代码中 同步 和 异步 任务区分开。这种设计是有重大意义的。这使得浏览器可以在处理诸如网络请求这种高延时工作的时候，依然可以为用户提供流畅的渲染体验。

简述

二叉树的遍历是解 leetcode 树类型题目的基础。搞清楚每一种遍历的细节和复杂度是解题的关键。
leetcode 上有很多相关的题目，但题解却经常只关注唯一的一道题。比如后序遍历就是利用稍微修改后的前序遍历倒置解出的，思路很巧妙，但是这种方法不具有普适性，无法解答其他与后序遍历相关的题目。
所以在这里完全总结一下二叉树遍历的问题，以便不仅仅可以写出题目，更重要的是在实际应用，比如模板解析中应用这些思路。
尽管对于二叉树来说，分为前中后序三种深度优先遍历和广度优先遍历四种。但实际上三种深度优先遍历不过是改变了访问子树根节点的时机，所以事实上可以认为是同一种遍历方式。

BeforeEach

我们约定树节点的数据类型如下，后不再赘述：

1
2
3
4
5

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

前序遍历

前序遍历是深度优先遍历，顺序是根节点 -> 左子树 -> 右子树。
所以你可以看到，这种方式是先处理子树根节点，再缓存左子树，最后处理右子树。

递归

对于树遍历的处理，天然的可以使用递归来处理。因为处理根和子树的逻辑是一样的，区别仅仅是我们需要根据不同的情况，来改变遍历（缓存）顺序。

1
2
3
4
5
6
7
8
9
10

def preorderTraversal(root: TreeNode):
    def visit(node):
        if not node: return
        res.append(node.val)
        visit(node.left)
        visit(node.right)

    res = []
    preorder(root)
    return res

二叉树中的每一个节点都被访问了，所以时间复杂度为 O(n)
递归过程中有栈的空间开销，对于二叉树，平均空间复杂度为 O(logn)，最差情况下树呈现链状，空间复杂度为 O(n)

迭代

递归实质上是代码自身通过函数调用栈隐式的维护了待处理节点的栈。所以我们也可以自己维护这个栈。你可以直接使用 list 来模拟栈，不过 collections 模块有个 deque 实现了头尾添加删除相同的速度，所以你也可以使用这个模块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def preorderTraversal(root: TreeNode):
    if not root: return

    stack = [root]
    res = []

    while stack:
        cur = stack.pop()
        res.append(cur.val)
        if res.right:
            stack.append(res.right)
        if res.left:
            stack.append(res.left)

    return res

你应该注意到了，我们在向栈内添加子树的时候，是先添加右子树，后添加左子树。这主要是因为模拟的栈和递归隐式处理的调用栈是不同的。
递归时，我们不仅可以处理当前节点，还能缓存未处理节点的所有信息，这个信息不仅仅包含其本身的数据，还有对其要做的操作。换句话说，递归时我们并不知道接下来的处理路线。
而迭代时，我们是实际上是要借用栈这个数据结构来模拟出一个树的节点遍历顺序。而处理的顺序是从栈顶弹出，所以我们这里先压入左子树，再压入右子树。换句话说，迭代时我们知道将要处理的节点清单。

更进一步的，为什么我们不能使用队列？
因为树的遍历有一个特点，就是在深度优先遍历中，我们不能遇到什么节点就处理好什么节点。换句话说，我们会缓存一些待处理的节点，而这些待处理节点的处理时机则是先遇到的后处理，即先进后出，符合栈的逻辑。

时间复杂度与空间复杂度的分析同递归。原因是我们在这里也是模拟的递归调用栈。

Morris 遍历

关于 BST

BST 算是 leetcode 关于树的考察的一个重点了。不过这并不意味着它是一个可以广泛运用的数据结构。主要原因就在于其查找、插入、删除操作的时间复杂度均与树高度成正比，换句话说，就是 O(logn) 。这意味着在很多情况下，时间消耗都比较大。所以我们会转而使用平衡树。比如红黑树，B+，B-等等（不过这些还没学会，就不说了

回到 BST，它有一个重要的特性，就是：

• 左低右高：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 左右子树也均为 BST

这也就意味着，它中序遍历的结果是一个递增数列。

另外还有两个关于 BST 的概念。这两个概念是依附于 BST 本身的性质而提出的，并不是独立的概念。

• 前驱节点(predecessor)：比当前节点小的最大节点
• 后继节点(successor)：比当前节点大的最小节点

Sketch

If you have watched the Vue3 Live Release video, you will know the Vue core team rewrote the diff algorithm.
The new diff algorithm refers to the ivi and inferno, whitch make virtual nodes diff quicker. You can visit this test result to check the accurate data.

As a whole, the algorithm can divide into three parts:

• patch the repetitive prefix & suffix nodes
• sync the old & new virtual nodes lengths
• diff subsequence of the same length

Next, we will explain the algorithm with the source code of Vue3.

注意这里讨论的模板编译器源码是 Vue3 的。另外的，我并不会粘贴完整的代码，而只是基于当前讨论的主题来选取一些关键的代码句子。你可以比对着真正的源码来阅读。毕竟源码才是最好的课本。

简述

Vue 的模板编译器算是除响应式系统之外的，另一个核心系统了。得益于模板编译器的支持，我们可以在写代码时使用诸如 v-if，v-slot 等方便的 api。
尽管名称中带有“编译器”三个字，但它相较于一些现代语言编译器来说，还是十分简单的。但总的来说，还是一样的，分为下面几个步骤：

• parse
• transform
• code generate

如果你提前阅读过 Vue3 的模板编译器语法，你会发现代码量很大。但再复杂的系统，也往往都是从几个简单的核心概念一步步构建起来的。只要找到了这几个核心概念，理清楚它们解决了什么问题，又是如何相互协作的，再去一条条的考虑具体边界情况，就能很容易的搞清楚整个系统了。

建议你使用官方的 模板调试工具 来查看一下不同模板实际产出的 AST。如果你不了解 AST，那么你可以查看 维基百科的解释。
不过你需要注意的是，调试工具输出的 AST 是 transform 之后的产物，在这个过程中会对原先通过 parser 产出的树做一些优化处理，这主要是为最后一步 code generate 做准备。
如果你觉得这样看比较难受，那么你可以下载 vue-next 的源码，直接调试或自己编写测试用例。

本文翻译自 Isolating application sub-components with membranes

膜是一种防御式的编程模式，被运用在一个应用程序的子组件之间。这种模式适用于内存安全的编程语言。

这种模式被提出已经很久了，但却并不广为人知。这篇文章的目的就是讲清楚膜编程背后的思想。因为我关于 膜 的很多经验都是建立于 Web 平台的，所以我会主要从 Javascript 和 Web 平台的用例来解释。值得注意的是，膜 模式并不是仅仅针对于 Web 编程提出的概念，它是一个可以广泛应用的模式。

历史: 膜的概念来源于对 Capability-secure Systems 的研究。最早可追溯至功能安全操作系统，例如 KeyKOS。 以及功能安全语言，例如 Joule 和 E。本文对膜的介绍主要基于 Mark S 中的描述。Miller 的 博士论文。膜后来被独立地发明，并被广泛应用于函数式编程社区去实现高阶函数的契约。

为什么要进行代码分割

事实上，尽管 Webpack 的功能是打包，但将所有文件都打包到一个文件下并不是一个好的选择。过大的打包文件会让加载变慢，导致用户感受到的 白屏时间 更长。
但如果直接加载开发环境的代码，过于零碎的模块同样会使加载变慢。这主要是因为目前主流的 HTTP 1.1 对同一个域名下的并行请求有所限制。另外，过多请求的请求头也会占用流量和带宽。

总而言之，代码的颗粒度并没有一个确切的值。你需要根据业务本身来作出决定。

简述

Webpack 是什么？官网是这样介绍的：

本质上，webpack 是一个现代 JavaScript 应用程序的静态模块打包工具。当 webpack 处理应用程序时，它会在内部构建一个 依赖图(dependency graph)，此依赖图会映射项目所需的每个模块，并生成一个或多个 bundle。

只要你从事前端开发，就不可能绕过 Webpack 这个工具。这篇文章基于 Webpack4，总结其核心概念及常规用法。

核心概念

Webpack 的核心概念分为四个：entry、output、loader 和 plugin。
理解这些概念是更好的使用 Webpack 的保证。