海屿文章列表

不相交集合元素的数据结构——并查集

不相交集合有两种基本操作:合并(union)和查询(find)。

并查集保持了一组不相交的动态集合,每个集合通过一个代表来识别,代表即集合中的某个成员。

数组实现Quick Find

我们可以直接用数组来存储集合的标识,这样查找操作直接返回对应数组的值即可,复杂度为O(1);而合并操作每次都需要遍历整个数组,复杂度为O(n)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   4   5   6   7   8   9

union(1, 4)
union(1, 5)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   1   1   6   7   8   9

有根树表示 Quick Union

为了降低合并操作的复杂度,我们可以用多个有根树表示集合,每个结点存储指向其父亲结点的指针,根节点指向自己。判断是否属于同一个集合时,我们只需要判断元素所属的树根是否相同。

批注 2019-10-08 010040.jpg

这种方式实际上并没有本质提高,而且如果一些极端情况下会退化成一个链表,查找操作的复杂度反而上升了,上面的例子中就是这样。

查找和合并的时间复杂度都为O(h),h表示树高。

所以我们需要对合并操作进行优化,优化方式一般为以下两种。

按秩合并(union by rank)

秩(Rank)就是一颗树的结点数,即使包含较少结点的树根指向包含较多结点的树根。
所以上面的例子中union(1, 2)操作会让 2 节点会指向 1 。
批注 2019-10-08 010145.jpg

这样查找操作最坏情况的时间复杂度为O(logN)

路径压缩

在查找所在位置是我们会进行递归,那么我们可以利用递归回溯的过程进行路径压缩。所谓压缩表示的就是将从x结点搜索到祖先结点所经过的结点都指向该树的根节点结点。
DSU_path_compression.png

在压缩之后树的高度低了,所以查找复杂度也降低了。

同时使用按秩合并和路径压缩

复杂度为反阿克曼函数,具体的证明比较复杂,可以参科下面这篇讲义。
这里简单介绍下阿克曼函数,他表示f(n) = 2 ^2^2^…^2,可见其增长速度极快,其反函数用lg*n表示,其值可以认为小于5。

https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/UnionFind.pdf

批注 2019-10-08 010145.jpg
参考文章:
https://cp-algorithms.com/data_structures/disjoint_set_union.html
https://algs4.cs.princeton.edu/15uf/

子元素 diff 算法的优化

5a58d2b2bbd4b-min.jpg

React 的 Diff

React先遍历新数组来找到插入和需要移动的节点,为了避免不必要的移动,react使用了一个哨兵值lastIndex,记录访问过的源数组下标最大值,如果当前元素的下标小于lastIndex,表示原相对位置无法满足需要了需要移动,否则更新lastIndex,这样来最大限度地利用原相对位置。
最后遍历一遍旧数组找到需要删除的元素。

但这种方式并不是总能得到最优结果。

例如:'1234' ➔ '4123'
React 并没有将4移到最前面,而是将234都移动一次。因为对新数组的遍历是从左向右的依次进行,所以这种位置相对关系总是局部的。

Diff 的改进

缩小问题规模

首先考虑一种情况,我们只对字符串进行了一次插入或删除操作,其实是没有必要进行diff,我们通过匹配两个字符串的通用前缀/后缀,可以直接找出差异,即便字符串进行了多次插入删除,查找公共前后缀也能在一定程度上减小diff的计算量,因为使用二分搜索的时间复杂度是O(nlogn)。

例如下面的两个字符串的公共前缀为abc,后缀为g,可以直接去掉。

A: -> [a b c d e f g] <-
B: -> [a b c h f e g] <-

寻找最小的移动次数

diff 算法首先需要一个旧数组的索引{1:0,2:1,3:2,4:3},通过该索引计算出新数组的对应位置。然后计算数组索引的最长上升子序列,通常使用动态规划实现,具体不做展开。

A: [a b c d]
B: [d a b c]
P: [3 0 1 2]
LIS: [0 1 2]

然后我们自右向左遍历新数组和 LIS 序列,查看元素的位置是否能与 LIS 序列的任何一个值匹配,若匹配则位置无需移动,然后取前一个LIS值继续,否则将其移动到当前遍历新数组元素的前面。
如上面的例子中,中有遍历到第一位时才不匹配,所以将B[1]=d移动到A[1]=a的前面即可。

为什么LIS能够做到这一点,因为它在整体上保留了数组升序排列的相对位置。

参考文章:
https://www.zhihu.com/question/65824137
https://github.com/NervJS/nerv/issues/3

限制 requestAnimation 渲染帧数

当机器性能不足以维持高帧数渲染时,一个较低的稳定的帧数相比不断在60帧上下波动能带来更好的体验。所以在一些动画交互较多的场景,有必要限制渲染帧数。

class AnimationFrame {
  constructor(fps = 60, animate) {
    this.requestID = 0;
    this.fps = fps;
    this.animate = animate;
  }

  start() {
    let then = performance.now();
    const interval = 1000 / this.fps;
    const tolerance = 0.1;

    const animateLoop = (now) => {
      this.requestID = requestAnimationFrame(animateLoop);
      const delta = now - then;

      if (delta >= interval - tolerance) {
        then = now - (delta % interval);
        this.animate(delta);
      }
    };
    this.requestID = requestAnimationFrame(animateLoop);
  }

  stop() {
    cancelAnimationFrame(this.requestID);
  }
}

requestAnimationFrame永远以60FPS运行,也就是每16.6ms执行一次,以我们要限制在10FPS(100ms)为例。递归7次时116.2ms>100ms,我们再执行下一次渲染。为了避免误差导致整体帧数低于设置,这里不能直接使用then = now,而是 then = now - (delta % interval)

See the Pen Limiting FPS (framerate) with Request Animation Frame by Rishabh (@rishabhp) on CodePen.

参考文章:
Controlling the Frame Rate with requestAnimationFrame
limitLoop.js

深入了解包含then属性的对象的promise解析

我们将包含then属性的对象称为thenable对象。

TC39规范

  • If Type(resolution) is not Object, then
    Return FulfillPromise(promise, resolution).
  • Let then be Get(resolution, "then").
  • If then is an abrupt completion, then
    Return RejectPromise(promise, then.[[Value]]).
  • Let thenAction be then.[[Value]].
  • If IsCallable(thenAction) is false, then
    Return FulfillPromise(promise, resolution).
  • Perform EnqueueJob("PromiseJobs", PromiseResolveThenableJob, « promise, resolution, thenAction »).

让我们一步一步解释:

resolve 一个非对象元素

Promise.resolve('Hello').then(
  value => console.log(`Resolution with: ${value}`)
);

// log: Resolution with: Hello

resolves 一个包含 abruptCompletion 的 then 对象

abruptCompletion 表示任何非正常的完成值。

const value = {};
Object.defineProperty(
  value,
  'then',
  { get() { throw new Error('no then!'); } }
);

Promise.resolve(value).catch(
  e => console.log(`Error: ${e}`)
);

// log: Error: no then!

resolves 包含 then 且其属性不为函数的对象

Promise.resolve(
  { then: 42 }
).then(
  value => console.log(`Resolution with: ${JSON.stringify(value)}`)
);

// log: Resolution with: {"then":42}

resolves 包含 then 且其属性为函数的对象

这部分是本文探讨的重点,也是递归promise链的基础。
当一个promise使用包含then方法的对象解析时,解析过程将then使用通常的promise参数调用resolve 和 reject。如果resolve没有被调用,promise将无法完成。

Promise.resolve(
  { then: (...args) => console.log(args) }
).then(value => console.log(`Resolution with: ${value}`));

// log: [fn, fn]
//        |   \--- reject
//     resolve

// !!! No log of a resolution value
Promise.resolve(
  { 
    then: (resolve) => { 
      console.log('Hello from then');
      resolve(42);
    }
  }
).then(value => console.log(`Resolution with: ${value}`));

// log: Hello from then
// log: Resolution with: 42

动态导入

当您使用动态import函数加载JavaScript模块时,import遵循相同的过程,因为它返回一个promise。导入模块的结构值将是一个包含所有导出值和方法的对象。

// file.mjs
export function then (resolve) {
  resolve('Not what you expect!');
}

export function getValue () {
  return 42;
}

// index.mjs
import('./file.mjs').then(
  resolvedModule => console.log(resolvedModule)
);

// log: Not what you expect

内存泄露的风险

参考co库的这个 issue https://github.com/tj/co/issues/180

原文地址:https://www.stefanjudis.com/today-i-learned/promise-resolution-with-objects-including-a-then-property/

Vue 单例组件

类似弹窗等组件我们希望是全局单例的,下面是 Vue 中的几种实现方式。

Vue 实例

使用Vue.extend方法得到一个组件的实例,挂载之后插入到DOM中。

var MyComponent = Vue.extend({
  template: '<div v-on:click="world">Hello {{msg}}!</div>',
  props: {
    msg: {
      type: String,
      required: true
    }
  }
  methods : {
    world : function() {
      console.log('world')
    }
  }
})
 
var component = new MyComponent(propsData: {msg: 'world'}).$mount()
document.getElementById('app').appendChild(component.$el)

传入prop需要在 new 组件时传入一个名为propsData的对象。组件内的data可以直接以component.data['name']这种形式修改。

Vue实例组件生命周期还有$forceUpdate()$nextTick()$destroy()方法。
注意:$forceUpdate()不会影响所有子组件,只影响实例本身和插入插槽内容的子组件。

Vue 全局 mixin

Vue.mixin({
    mounted:function(){
        if(this.$root===this){
            var ne=document.createElement("div");
            ne.id="placeholderGLOBAL";
            this.$el.appendChild(ne);
            var dp=Vue.component("global-components");
            var idp=new dp({parent:this,el:"#placeholderGLOBAL"});
            idp.$mount();
        }
    }
});

https://forum.vuejs.org/t/solved-component-singleton-render-only-once-reuse-dom-elements/17799/9