2020-04-15日计划：Fiber、requestIdleCallback、岛屿问题

[sl1673495]

Fiber

出现背景

JavaScript 是单线程运行的，而且在浏览器环境屁事非常多，它要负责页面的JS解析和执行、绘制、事件处理、静态资源加载和处理, 这些任务可以类比上面’进程‘。

对于 Vue 来说，

1. 模板的静态可优化特性
2. 响应式底层机制带来的组件的精确更新 使得他可以把每个任务尽可能的压缩小，这也是尤大觉得Vue3不需要时间分片的原因。

这是React V15 下面的一个列表渲染资源消耗情况。整个渲染花费了130ms, 🔴在这里面 React 会递归比对VirtualDOM树，找出需要变动的节点，然后同步更新它们, 一气呵成。这个过程 React 称为 Reconcilation(中文可以译为协调)。在 Reconcilation 期间，React 会霸占着浏览器资源，一则会导致用户触发的事件得不到响应, 二则会导致掉帧，用户可以感知到这些卡顿。

所以 React 通过Fiber 架构，让自己的Reconcilation 过程变成可被中断。 '适时'地让出CPU执行权，除了可以让浏览器及时地响应用户的交互。

Fiber 的做法

Fiber 和 浏览器之间配合调度，属于 合作式调度(Cooperative Scheduling)，并没有人有权利抢占，而是 Fiber 主动向浏览器申请空闲时间的时间片 requestIdleCallback，然后 Fiber 自己查询剩余时间是否充足，不足的话再把执行权交回给浏览器。

window.requestIdleCallback(
  callback: (dealine: IdleDeadline) => void,
  option?: {timeout: number}
)

interface IdleDealine {
  didTimeout: boolean // 表示任务执行是否超过约定时间
  timeRemaining(): DOMHighResTimeStamp // 任务可供执行的剩余时间
}

浏览器每一帧会做什么事情：

1. 处理用户输入事件
2. Javascript执行
3. requestAnimation 调用
4. 布局 Layout
5. 绘制 Paint

如果浏览器处理完上述的任务(布局和绘制之后)，还有盈余时间，浏览器就会调用 requestIdleCallback 的回调。

但是在浏览器繁忙的时候，可能不会有盈余时间，这时候requestIdleCallback回调可能就不会被执行。 为了避免饿死，可以通过requestIdleCallback的第二个参数指定一个超时时间。

[sl1673495]

fps算法：

function fps() {
  return new Promise(resolve => {
    requestAnimationFrame(rAFTime => {
      requestAnimationFrame(nextRAFTime => {
        resolve(1000 / (nextRAFTime - rAFTime));
      });
    });
  });
}

[sl1673495]

观察performence面板可以发现，postMessage确实是在下一个task的开始执行。

requestAnimationFrame 是在这一帧结束之前调用回调函数，此后会经历 Recalculate Style、Update Layer Tree、Paint重绘、Composite Layers合成层

虽然 HTML 规范文档中说 task 之间会经历浏览器的渲染，但是一帧之间是允许存在多个 task 的。

嵌套的setTimeout 并不一定能保证两个 task 分别经历自己的渲染轮次（chrome）中，可能会对其进行合并优化。

嵌套 postMessage 也一样不能保证，而且经过测验发现还会随机的把一个帧卡成上百毫秒。

所以如果要写动画还是要requestAnimationFrame比较靠谱。它一定会保证每一个rAF的回调都能经历一次渲染。

no:

setTimeout(() => {
  document.body.style.background = 'red'
  setTimeout(() => {
    document.body.style.background = 'yellow'
  });
});

good:

requestAnimationFrame(() => {
  document.body.style.background = 'red'
  requestAnimationFrame(() => {
    document.body.style.background = 'yellow'
  });
});

[sl1673495]

岛屿问题

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    let count = 0
    for (let i = 0; i < grid.length; i++) {
        let row = grid[i]
        for (let j = 0; j < row.length; j++) {
            if (row[j] === '1') {
                dfs(grid, i, j)
                count++
            }
        }
    }
    return count
};

function dfs(grid, i, j) {
    let point = grid[i] && grid[i][j]
    if (point === '0' || point === undefined) {
        return
    }
    grid[i][j] = '0'

    dfs(grid, i - 1, j) // 上
    dfs(grid, i + 1, j) // 下
    dfs(grid, i, j - 1) // 左
    dfs(grid, i, j + 1) // 右
}

分析

很经典的 dfs 问题，很棒很棒的思路，当找到一个点为1的时候，先记录数量加一。

然后对于每个点递归的去遍历自己和上下左右的节点，如果值为1就置为0再继续遍历上下左右，这样直到遇到某一边本身就为0的时候停止。

这样，一片 “值为1的岛屿” 就全部归零了。