使用 Vue 实现一个虚拟列表

大列表问题

因为 DOM 性能瓶颈,大型列表存在难以克服的性能问题。 因此,就有了 “局部渲染” 的优化方案,这就是虚拟列表的核心思想。

虚拟列表的实现,需要重点关注的问题一有以下几点:

  1. 可视区域的计算方法
  2. 可视区域的 DOM 更新方案
  3. 事件的处理方案

下面逐一分解说明。

可视区域计算

可视区域的计算,就是使用当前视口的高度、当前滚动条滚过的距离,得到一个可视区域的坐标区间。 算出可视区域的坐标区间之后,在去过滤出落在该区间内的列表项,这个过程,列表项的坐标也是必须能算出的。

思考以下情况,

  1. 我们的视口高度为 100px
  2. 我们当前已经滚动了 100px
  3. 我们的列表项,每一项高度为 20px

根据这些条件,我们可以计算出,当前可视区域为第 11 项至第 20 项。

1
2
3
4
5
6
7
8
9
10
11
12
13
  01 - 05,可视区域上方
+----+-----------+--------
| 06 | 100 ~ 120 |
+----+-----------+
| 07 | 120 ~ 140 |
+----+-----------+
| 08 | 140 ~ 160 | 可视区域
+----+-----------+
| 09 | 160 ~ 180 |
+----+-----------+
| 10 | 180 ~ 200 |
+----+-----------+--------
  11 - N,可视区域下方

这是因为列表项高度是固定的,我们可以通过简单的四则运算算出已经滚动过去的 100px 中,已经滚动走了 5 个列表项,因此可视区域是从第 6 项开始,而视口高度为 100px,能容纳 100 / 20 即 5 个条目。

上面例子的情况非常简单,也不存在性能问题,因此实际上并没有展开讨论的价值。 而还有另一种复杂很多的情况,那就是,列表项高度不固定,根据内容决定高度。

此时,我们就没办法直接使用四则运算一步到位算出可视区域对应的条目了。

而必须实现一种机制,记录所有列表项的坐标,再通过检查列表项是否落在视口内。

下面重点讨论该问题。

READ MORE...

JavaScript 中的 “相等” 算法

整理笔记本时,看到以往一些对 JavaScript 中 “相等” 关系的记录。 尽管这是一个被说烂了的话题,但写一篇资料整理总结,当作复习下也不错。

JavaScript 的 “相等” 比较算法,按严格程度来排,有以下几种:

  1. == 双等号
  2. === 三等号
  3. SameValueZero 算法
  4. SameValue 算法

下面逐个介绍它们的特点。


== 双等号

在 JavaScript 中,使用 == 来判断相等,是一种不严格的比较。

关于双等号,最广为人知的一点,就是在比较不同类型的值时,JavaScript 会进行自动转型。

如果不明白其转型规则,可能会出现让人匪夷所思的结果。

举例来说:

1
2
3
'' == false // true
'  ' == false // true
'' == ' ' // false

具体的转型规则如下:

  1. 两边是对象(引用类型),比较内存地址是否相同。
  2. 一边是原始类型,一边是对象,则将对象转换成原始类型再比较
  3. 两边都是原始类型:
    • 3.1. 一边是 Symbol,则返回 false
    • 3.2. 两边类型一样,直接比较值
    • 3.3. 一边为 undefinednull,则比较另一边是否也为 undefinednull
    • 3.4. 一边为 “数字” 或者 “布尔值”,则以 “数字” 进行比较
READ MORE...

JavaScript 中的柯里化

不过多介绍柯里化的定义和应用场景,直接看实现。


柯里化实现

如果我们有以下加法函数:

1
const add = (a, b) => a + b

要怎么实现柯里化呢?


手工柯里化

我们可以选择直接手写柯里化的 add:

1
2
3
4
5
6
7
// 手工柯里化 
const curryingAdd = a => b => a + b

// 使用
const inc = curryingAdd(1)
inc(1) // 2

通过闭包的嵌套,我们可以实现每次只接受一个参数的手工柯里化的函数。

但是这种方式,对于每个需要柯里化的函数,都需要侵入其实现,非常麻烦。因此并没有什么实用价值。我们需要能一种通用的方案来自动化做这个事情。


自动柯里化

柯里化的实现,核心在于根据参数数量选择返回接受剩余参数的新函数,或者返回最终结果。

在 JavaScript 中,具备实现这一切的条件,我们可以通过函数的 length 得知形参的数量,通过 arguments 对象得知实参的信息,通过闭包返回新函数也不在话下。下面开始尝试实现,先从简单的两个参数的情况开始:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 单一参数函数的柯里化
const curry1 = (fn) => {
  // 生成一个柯里化的版本
  return function currying(a) {
    // 检查实参数量
    // 此处不能简单地用 undefined 判断,
    // 因为 fn 本身可能也能接受并处理 undefined
    switch (arguments.length) {
      // 没有传入任何参数,返回柯里化后的函数本身
      case 0: return currying

      // 传入了任意大于 0 个数量的参数,则调用应用它们
      default: return fn.apply(void 0, arguments)
    }
  }
}

// 两个参数的函数柯里化
const curry2 = (fn) => {
  // 生成一个柯里化的版本
  return function currying(a,b) {
    // 同 curry1,检查实参数量
    switch (arguments.length) {
      // 没有传入任何参数,返回柯里化后的函数本身
      case 0: return currying
 
      // 传入了 1 个参数,则记录下该参数,
      // 创建一个接受剩余参数的新函数并柯里化
      // 相当于简化了函数的参数规模
      case 1: {
        const arg = arguments[0]
        
        // 自动柯里化接受剩余参数的函数
        // 剩余参数只有 1 个,因此使用 curry1
        return curry1(function() {
          // 合并外层函数已经部分应用的参数          
          const args = [arg]
          args.push.apply(args, arguments)

          return fn.apply(void 0, args)
        })
      }

      // 传入了足够的参数时,直接应用这些参数
      default: return fn.apply(void 0, arguments)
    }
  }
}

// 使用
const add = (a, b) => a + b
const curryingAdd = curry2(add)
curryingAdd(1, 1) // 2
curryingAdd(1)(1) // 2
curryingAdd()(1)()(1) // 2
// ...

READ MORE...

λ 演算(λ-calculus)笔记

文中涉及到代码的地方,除了 λ 表达式,都尽量提供 Scheme 以及 JavaScript 代码做对照,以便加深理解。

先从基本概念开始。λ 演算包含构建 λ 项和对 λ 项执行操作。

READ MORE...

Scheme 中的 continuation

continuation 是一个非常抽象晦涩的概念,为了理解这个概念,翻阅了大量的资料。 下面记录一些对 continuation 的粗浅的理解。

continuation 代表了程序于某一点接下来将要执行的 “后续部分”。

在 scheme 中,操作符 all‑with‑current‑continuation(下文开始使用缩写 call/cc) 提供了使用 continuation 的方法。call/cc 会捕获调用处的 continuation,然后将该 continuation 传入其参数(一个 procedure)中进行处理。

call/cc 接受一个 procedure(过程/函数)作为参数,call/cc 调用处的 continuation 将作为该 procedure 的参数传入。

观察这个例子:

1
(+ 1 (call/cc (lambda (k) (+ 2 (k 3)))))

例子中,

  1. 首先,我们先把 call/cc 所处位置部分当作一个“空洞”
  2. 然后,call/cc 所处位置的 continuation,就是 “空洞” 之外的程序后续将执行的过程
1
(+ 1 空洞)

具体点,就是 “一个将对该(空洞)位置做加一的过程”,相当于:

1
(lambda (hole) (+ 1 hole))

再来观察上述例子中 call/cc 的参数部分,

1
(lambda (k) (+ 2 (k 3)))

其中形参 k 绑定的即为 continuation。执行时,该 continuation 会应用在 3 上。换句话说,3 充当了上述的“空洞”的值,继续走完 “下半程”(即 +1 操作)。

1
(+ 1 3) 

结果为 4

escaping continuation

需要注意的是,上述过程中,3 “走了不寻常的路” 穿梭到 k 这个 continuation 中去了。

而原本 (k 3) 处的 continuation(即 (+ 2 空洞))将被抛弃!就是说,开头的例子中,最终的运行结果就是 4

1
2
(+ 1 (call/cc (lambda (k) (+ 2 (k 3)))))
=>  4

这是个很有用的特性,叫做 escaping continuation,可以用于退出一个计算过程,在这个例子中就是退出 + 2 的运算过程。可以用下面的代码加深理解:

1
2
3
4
5
6
7
8
9
10
11
12
13
;; 返回
(+ 1 (call/cc (lambda (return) (+ 2 (return 3)))))
=> 4

;; 退出
(call-with-current-continuation
   (lambda (exit)
     (for-each (lambda (x)
                 (if (negative? x)
                     (exit x)))
               '(54 0 37 -3 245 19)) #t))
=> -3

作为比较:

1
2
(+ 1 (call/cc (lambda (k) (+ 2 3)))))
=> 6

该例子中,没有使用 call/cc 处的 continuation,因此不会有逃逸现象,(+ 2 3) 的值作为 call/cc 的返回值,然后 + 1,最终结果为 6

scheme 的 continuation 还能回到上一次离开的上下文,因为 continuation 里面,一直持有程序的“后续”,我们可以不限制的多次执行它们,用下面的例子来说明:

1
2
3
4
5
6
7
(define r #f)

(+ 1 (call/cc (lambda (k)
                ;; 将 `continuation` 保存在 `r` 中
                (set! r k)
                (+ 2 (k 3)))))
=> 4

这次的例子中,我们额外使用全局变量 r 来记录这个 continuation,该例子此时跟之前一样,仍然返回运算结果 4。 然后,我们再通过全局变量 r 来再次“重放”该 continuation

1
2
(r 5)
=> 6

再次强调,需要注意伴随 r 的逃逸现象,如下面的例子:

1
2
(+ 3 (r 5))
=>  6

其中 r 被应用在 5 时,(r 5) 本身的 continuation 就会被抛弃。

READ MORE...