React Algorithm

位运算（bit-operation）

特性

位运算在计算机中作为非常底层的运算，速度快，但不太直观且不支持整数运算。

位运算只能在整型变量之间进行运算
js 中的Number类型在底层都是以浮点数(参考 IEEE754 标准)进行存储
js 中所有的按位操作符的操作数都会被转成补码形式的有符号32位整数

位运算	用法	描述
按位与(`&`)	`a & b`	对于每一个比特位,两个操作数都为 1 时, 结果为 1, 否则为 0
按位或(`\|`)	`a \| b`	对于每一个比特位,两个操作数都为 0 时, 结果为 0, 否则为 1
按位异或(`^`)	`a ^ b`	对于每一个比特位,两个操作数相同时, 结果为 0, 否则为 1
按位非(`~`)	`~ a`	反转操作数的比特位, 即 0 变成 1, 1 变成 0
左移(`<<`)	`a << b`	将 a 的二进制形式向左移 b (< 32) 比特位, 右边用 0 填充
有符号右移(`>>`)	`a >> b`	将 a 的二进制形式向右移 b (< 32) 比特位, 丢弃被移除的位, 左侧以最高位来填充
无符号右移(`>>>`)	`a >>> b`	将 a 的二进制形式向右移 b (< 32) 比特位, 丢弃被移除的位, 并用 0 在左侧填充

基础使用

定义一些枚举常量

1
2
3

const A = 1 << 0; // 0b00000001
const B = 1 << 1; // 0b00000010
const C = 1 << 2; // 0b00000100

位掩码特性快速操作实现增加、删除、比较

const A = 1 << 0; // 0b00000001
const B = 1 << 1; // 0b00000010
const C = 1 << 2; // 0b00000100

// 增加属性
const ABC = A | B | C; // 0b00000111
// 删除属性
const AB = ABC & ~C; // 0b00000011

// 属性比较
// 1. AB当中包含B
console.log((AB & B) === B); // true
// 2. AB当中不包含C
console.log((AB & C) === 0); // true
// 3. A和B相等
console.log(A === B); // false

react中使用

优先级管理 lanes

//类型定义
export opaque type Lanes = number;
export opaque type Lane = number;

// 变量定义
export const NoLanes: Lanes = /*                        */ 0b0000000000000000000000000000000;
export const NoLane: Lane = /*                          */ 0b0000000000000000000000000000000;

export const SyncLane: Lane = /*                        */ 0b0000000000000000000000000000001;
export const SyncBatchedLane: Lane = /*                 */ 0b0000000000000000000000000000010;

export const InputDiscreteHydrationLane: Lane = /*      */ 0b0000000000000000000000000000100;
const InputDiscreteLanes: Lanes = /*                    */ 0b0000000000000000000000000011000;

const InputContinuousHydrationLane: Lane = /*           */ 0b0000000000000000000000000100000;
const InputContinuousLanes: Lanes = /*                  */ 0b0000000000000000000000011000000;
// ...
// ...

const NonIdleLanes = /*                                 */ 0b0000111111111111111111111111111;

export const IdleHydrationLane: Lane = /*               */ 0b0001000000000000000000000000000;
const IdleLanes: Lanes = /*                             */ 0b0110000000000000000000000000000;

export const OffscreenLane: Lane = /*                   */ 0b1000000000000000000000000000000;

方法定义

// 分离出最高优先级 得到此lanes中最右边的的1
function getHighestPriorityLane(lanes: Lanes) {
  return lanes & -lanes;
}

// 分离出最低优先级
// clz32(lanes) => https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32
function getLowestPriorityLane(lanes: Lanes): Lane {
  // This finds the most significant non-zero bit.
  const index = 31 - clz32(lanes);
  return index < 0 ? NoLanes : 1 << index;
}

执行上下文 ExecutionContext

export const NoContext = /*             */ 0b0000000;
const BatchedContext = /*               */ 0b0000001;
const EventContext = /*                 */ 0b0000010;
const DiscreteEventContext = /*         */ 0b0000100;
const LegacyUnbatchedContext = /*       */ 0b0001000;
const RenderContext = /*                */ 0b0010000;
const CommitContext = /*                */ 0b0100000;
export const RetryAfterError = /*       */ 0b1000000;

// Describes where we are in the React execution stack
let executionContext: ExecutionContext = NoContext;

方法定义

// scheduleUpdateOnFiber函数中包含了好多关于executionContext的判断(都是使用位运算)
export function scheduleUpdateOnFiber(
  fiber: Fiber,
  lane: Lane,
  eventTime: number,
) {
  if (root === workInProgressRoot) {
    // 判断: executionContext 不包含 RenderContext
    if (
      deferRenderPhaseUpdateToNextBatch ||
      (executionContext & RenderContext) === NoContext
    ) {
      // ...
    }
  }
  if (lane === SyncLane) {
    if (
      // 判断: executionContext 包含 LegacyUnbatchedContext
      (executionContext & LegacyUnbatchedContext) !== NoContext &&
      // 判断: executionContext 不包含 RenderContext或CommitContext
      (executionContext & (RenderContext | CommitContext)) === NoContext
    ) {
      // ...
    }
  }
  // ...
}

深度优先遍历（dfs）

概念

是一种用于遍历或搜索树或者图的算法。

// 实现方式1 递归
function dfs(nodes) {
  console.log('探寻阶段: ', nodes.name);
  nodes.children.forEach(child => {
    dfs(child);
  });
  console.log('回溯阶段: ', nodes.name)
} 

// 实现方式2 栈
function dfs(node) {
  const stack = [];
  stack.push(node);
  // 栈顶元素还存在, 就继续循环
  while ((node = stack[stack.length - 1])) {
    if (node.visited) {
      console.log('回溯阶段: ', node.name);
      // 回溯完成, 弹出该元素
      stack.pop();
    } else {
      console.log('探寻阶段: ', node.name);
      node.visited = true;
      // 利用栈的先进后出的特性, 倒序将节点送入栈中
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i]);
      }
    }
  }
}

react中使用

深度优先遍历在react中的经典应用场景是ReactElement与fiber树的构造过程
使用context时，深度优先查找消费的context节点

堆排序（heap-sort）

概念

最常见的堆结构就是二叉堆。二叉堆也是完全二叉树（注意和满二叉树区分），即对于节点为n，深度为k的二叉树与节点n，深度为k的满二叉树除了最后一层外一一对应。
堆排序利用二叉根的特性，对根节点循环提取，从而达到排序目的，时间复杂度o(nlogn)。

特性

父节点的值大于等于子节点的值（最大堆），父节点的值小于等于子节点的值（最小堆）
假设一个数组[k0, k1, k2, …kn]下标从 0 开始. 则ki <= k2i+1,ki <= k2i+2 或者 ki >= k2i+1,ki >= k2i+2 (i = 0,1,2,3 .. n/2)

排序使用

一次循环完 heapInsert构造大顶堆或小顶堆

function heapInsert(arr, curIndex) {
  while (arr[curIndex] > arr[((curIndex - 1) / 2) >>> 0]) {
    swap(arr, curIndex, ((curIndex - 1) / 2) >>> 0)
    curIndex = ((curIndex - 1) / 2) >>> 0
  }
}

// 1. 构造大顶堆
for (let i = 0; i < arr.length; i++) {
  heapInsert(arr, i)
}

循环提取根节点

// 向下调整的过程 始终保持一个大顶堆状态
function heapify(arr, index, size) {
  let leftIndex = 2 * index + 1

  while (leftIndex < size) {
    // 左右子树最大的一位
    let largestBtw =
      leftIndex + 1 < size && arr[leftIndex + 1] > arr[leftIndex]
        ? leftIndex + 1
        : leftIndex
    let largest = arr[index] > arr[largestBtw] ? index : largestBtw

    // 如果都大于子树 停止
    if (largest === index) break
    swap(arr, index, largest)
    index = largest
    leftIndex = 2 * index + 1
  }
}


// 2. 循环提取根节点
// 2.1 将根节点与末尾元素交换 heapSize减1
// 2.2 交换之后进行向下调整
let heapSize = arr.length
while (heapSize--) {
 swap(arr, 0, heapSize)
 // 向下调整达到保持大顶堆
 heapify(arr, 0, heapSize)
}

react中使用

对于二叉堆的应用在scheduler，有两个数组taskQueue和timerQueue，它们都是以最小堆的形式存储。

栈（stack）

概念

栈是一个先入后出(FILO-FirstInLastOut)的有序列表。

特性

先入后出，后入先出
除头尾节点之外, 每个元素有一个前驱, 一个后继

基本使用

class Stack {
  constructor() {
    this.dataStore = [];
    this.top = 0;
  }

  // 压栈
  push(element) {
    this.dataStore[this.top++] = element;
  }

  // 弹栈
  pop() {
    return this.dataStore[--this.top];
  }

  // 预览栈顶元素
  peek() {
    return this.dataStore[this.top - 1];
  }

  // 检测栈内存储了多少个元素
  length() {
    return this.top;
  }

  // 清空栈
  clear() {
    this.top = 0;
  }
}

react中使用

context状态管理 ReactFiberStack.js中定义
executionContext 执行上下文

链表操作（linked-list）

概念

链表是一种常见的基础数据，是一种线性表。

特性

物理上不连续，逻辑上连续
单向链表: 每个节点包含两个域, 一个信息域和一个指针域. 这个指针指向列表中的下一个节点, 而最后一个节点则指向一个空值
双向链表: 每个节点有两个连接, 一个指向前一个节点(第一个节点指向空值), 而另一个指向下一个节点(最后一个节点指向空值)
循环链表: 在单向链表的基础上, 首节点和末节点被连接在一起

基本使用

// 定义Node节点类型
function Node(name) {
  this.name = name;
  this.next = null;
}

// 链表
function LinkedList() {
  this.head = new Node('head');

  // 查找node节点的前一个节点
  this.findPrevious = function(node) {
    let currentNode = this.head;
    while (currentNode && currentNode.next !== node) {
      currentNode = currentNode.next;
    }
    return currentNode;
  };

  // 在node后插入新节点newElement
  this.insert = function(name, node) {
    const newNode = new Node(name);
    newNode.next = node.next;
    node.next = newNode;
  };

  // 删除节点
  this.remove = function(node) {
    const previousNode = this.findPrevious(node);
    if (previousNode) {
      previousNode.next = node.next;
    }
  };

  // 反转链表
  this.reverse = function() {
    let prev = null;
    let current = this.head;
    while (current) {
      const tempNode = current.next;
      // 重新设置next指针, 使其指向前一个节点
      current.next = prev;
      // 游标后移
      prev = current;
      current = tempNode;
    }
    // 重新设置head节点
    this.head = current;
  };
}

react中使用

fiber对象
hook对象

React Algorithm

位运算（bit-operation）

特性

基础使用

react中使用

深度优先遍历（dfs）

概念

react中使用

堆排序（heap-sort）

概念

特性

排序使用

react中使用

栈（stack）

概念

特性

基本使用

react中使用

链表操作 （linked-list）

概念

特性

基本使用

react中使用

链表操作（linked-list）