好耶!是 BST

关于 BST

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

回到 BST,它有一个重要的特性,就是:

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

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

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

  • 前驱节点(predecessor):比当前节点小的最大节点
  • 后继节点(successor):比当前节点大的最小节点
Read more
Vue3 源码阅读笔记(五)—— diff 算法解析

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.

Read more
Vue3 源码阅读笔记(四)—— 模板编译器的设计,从 AST 类型说起

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

简述

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

  • parse
  • transform
  • code generate

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

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

Read more
使用膜隔离应用程序的子组件

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

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

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

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

Read more
好耶!是 Webpack(二)———— 代码分割

为什么要进行代码分割

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

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

Read more
好耶!是 Webpack(一)———— 基础概念

简述

Webpack 是什么?官网是这样介绍的:

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

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

核心概念

Webpack 的核心概念分为四个:entryoutputloaderplugin
理解这些概念是更好的使用 Webpack 的保证。

Read more
Vue3 源码阅读笔记(三)—— 响应式?不过是数据劫持罢了

简述

事实上,响应式并不是 Vue3 的新概念,它是一个核心概念。在实际代码中,响应式系统经常与组件化相提并论。更进一步的说,组件化赋予了开发者模块化代码的能力,而响应式系统则让开发者可以通过数据控制组件的呈现方式。

不过这东西从本质上来讲,其实就是劫持数据的变化,在数据变化后自动的执行一些副作用函数。

如果你大致的了解过这个东西,你大概会知道,Vue2Vue3 的响应式系统实现有些略微不同。
从表象上来说,Vue2 的响应式系统是黑盒。Vue2 承包了一切工作,你只需要将数据定义在诸如 datapropscomputed 等选项中就行。而 Vue3 则是把这个决定权交给了开发者。由开发者来决定究竟哪些数据应该是响应式的。
从实现上来说,Vue2 使用 Object.defineproperty 来实现数据劫持,而 Vue3 则使用了 proxy

从逻辑上讲,其实二者是相同的,都是为了实现核心的数据劫持。
不过 Vue 毕竟是一个投入到实际生产中使用的框架,仅仅完成理论上的实现当然是不行的。从 Object.definepropertyproxy 的切换实际上也表现出了一些技术上的选择。

简单来说,因为 Vue2 对响应式数据黑盒化的设计,在框架初始化的时候,会递归遍历所有数据,然后使用 Object.defineproperty 来做劫持。这是一个解决方案,但并不够好。因为首先会付出很多性能消耗,其次,并不是每一条数据都需要变成响应式的。递归消耗的性能支出是否合算,全看开发者的具体实现方式。另外,Object.defineproperty 也不能监听到对象属性的新增与删除。
所以 Vue3 使用了 proxy 和显式的 reactice API。这样不仅可以让开发者自行决定哪些数据需要变成响应式的,还能减少劫持时的数据消耗。

除此之外,在具体实现中,Vue3 也做了一些调整来优化性能。更具体的东西,来直接看源码吧。

Read more
Vue3 源码阅读笔记(二)—— 响应式系统之前,是创建与渲染

一些说明

  1. 这篇文章并不是专注于介绍响应式 API 的文章,所以如果你想搞清楚新的 API 该怎么用,那么你应当关注官方的 Migration Guide
  2. 为了更明确的说明一些问题,我可能会删减许多代码。但这些代码并非是不必要的,只是对于我们要阐述的主题来说,它们是毫无必要的

从 CreateApp 开始

在这一节,我们会介绍 Vue.js 的入口函数 createApp,以及这之后的一整套渲染过程。阅读这一部分的内容有助于你理解响应式系统在整个 Vue.js 中扮演了怎样的角色。

当你使用 Vue3 写一个组件时,你可能会这样做:

1
2
3
const vm = createApp({
// ...
}).mount("#app");
Read more
Vue3 源码阅读笔记(一)—— 搭建环境

工欲善其事必先利其器,在阅读源码前,首先要做的一步就是搭建调试源码的环境。

  1. Github 下载源码:
1
git clone git@github.com:vuejs/vue-next.git
  1. 使用 Webstrom 打开项目,安装依赖
1
yarn install
  1. 配置项目运行

你可以参考我的配置,但请注意将一些个性化设置配置成你自己的。
注意 Arguments 一栏的参数 -s。这个参数会生成 source map 来帮助你调试源码。

Vue3 源码运行配置

Read more
Tree Shaking

关于 Treeshaking

tree shaking 指的是移除 JavaScript 上下文中的的未引用代码(dead-code)。这个术语和概念最先是 ES2015 打包工具 rollup 发展的。

事实上,消除无用代码并不是一个新的概念。这种技术被广泛运用于传统的编程语言编译器中,编译器会判断代码是否影响功能,并移除那些无用的代码,这个技术被称为 DCE (dead code elimination)

从先后来讲,tree shakingDCE 的一种新的实现。不过和传统的 DCE 不一样的是,tree shaking 更关注于消除没有用到的代码,而 DCE 则关注那些不可能执行的代码,由编译器将 dead code 从 AST 上删除。
另一方面,在大多数情况下,JavaScript 都是通过网络加载的。众所周知,网络速度可是一个变化多端的东西。所以如果能缩短代码的加载时间,那么这对网络应用性能和用户体验的提升都是极大的。

Read more