关于javascript:精读磁贴布局-性能优化

4次阅读

共计 3320 个字符，预计需要花费 9 分钟才能阅读完成。

通过上一篇精读《磁贴布局 – 性能实现》的介绍，这次咱们进入性能优化环节。

磁贴布局性能优化形式有很多，比方通过空间换工夫，存储父子关系的索引，不便疾速查找到指标组件。但有一个最外围的性能优化点，即碰撞性能优化。

试想，最奢侈的判断组件碰撞办法是什么？个别会遍历画布所有的组件，依据以后组件地位与指标组件地位的绝对地位判断是否产生碰撞，所以仅判断单个组件碰撞时，工夫复杂度是 O(n)。

但磁贴布局的碰撞判断波及整个画布，因为一个组件的挪动可能引发另一个组件的挪动，造成一系列连环布局变动，比方上面这个状况：

         [---]
         [ ]
         [A]
         [ ]
     ↑   [---]
[---------]
[B]
[---------]
  [---]
  [C]
  [---]
   [-------]
   [D]
   [-------]

比方将 B 向上挪动，每个组件落下来时都要做独立的碰撞断定。因为最终碰撞后果是很难预测的，只能一个组件一个组件的判断。比方下面的例子，后果如下：

[---------]
[B]
[---------]
  [---]  [---]
  [C]  [ ]
  [---]  [A]
         [ ]
         [---]
   [-------]
   [D]
   [-------]

能够看到，D 原本是紧紧靠着 C 的，但因为 A 组件移下来了，且 A 比 C 高，所以 D 紧靠的组件就从 C 变成 A 了，这个在 C 做独立碰撞判断之前，是难以通过画布的构造剖析进去的，更不用说联合上画布的整体大小缩放、栅格数量的变动后产生的影响，组件最终落点必须每个组件通过正确程序顺次断定碰撞后能力确定。

因而磁贴碰撞的工夫复杂度是 O(n²)，比方页面中有 100 个组件，就至多要遍历 10000 次能力实现一次布局计算，这样在比拟极限的状况下，比方页面有 1000 个组件时，布局计算必定十分耗时。

再思考一个问题，正是因为磁贴布局的碰撞断定，导致 磁贴布局不可能存在组件重叠的状况，因而即使画布存在 1000 个组件，只有组件宽高不是特地小（比方每个组件 1px 宽高，挤满 1000px 区域），都不可能汇集在某个小区域内，而是扩散在很大的范畴，那么与以后组件过远的组件就基本不须要做碰撞断定，因为他们不可能相交。

再类比到人判断碰撞的视角，当画布有 1000 个组件时，咱们也能一眼看进去某个组件与哪些组件相交，但这个判断来自于肉眼在可视区域一扫而过，而不是把 1000 个组件全副看一遍。这阐明人眼断定碰撞是通过优化的：以这个组件为圆心，上下左右扩充肯定的范畴扫一眼是否有碰撞就够了。

因而咱们模仿人眼找碰撞的思路，把画布分为若干的栅格，记录每个组件所在的栅格，这样碰撞断定时，只有在组件所在栅格内进行断定就行了。

如下将画布分为若干栅格：

  [---] │        │        │        │
  [A] │        │        │        │
  [---] │        │        │        │
────────┼────────┼────────┼────────┼────────
     [-----]     │        │        │
     [B]     │   [---]│        │
     [-----][C]  │   [G]│        │
────────┼────────┼───[---]┼────────┼────────
        │        │   [E]  │   [F]  │
        │        │   [-----------] │
        │        │   [ ] │
────────┼────────┼───[D]─┼────────
        │        │   [ ] │
        │        │   [-----------] │
        │        │        │        │

这样当断定如下组件碰撞时，要比照的组件如下：

A：比照组件无。
B：比照组件 C。
D：比照组件 E、F、G

因为一个区域承载组件数量是固定的，所以 O(n²) 工夫复杂度就优化为了 O(n x P) 其中 P 对每个组件来说都是常数，因而工夫复杂度最终为 O(n)。

当然这里存在几个注意事项：

须要空间换工夫，即存储每个组件属于哪些区域，以及每个区域有哪些组件，这样拖拽断定时无需遍历所有组件。
栅格大小不宜过大，栅格过大则划分栅格的意义就不大了，因为一个栅格内组件数还是很多。
栅格大小不宜过小，这样每个组件可能横跨很多栅格，导致栅格数量自身的循环次数甚至会超过组件树，就变成了负优化。

对于栅格大小，个别磁贴布局会设置 cols rowHeight 两个选项，以这两个选项的正整数倍为跨度设置栅格是比拟适合的，这样会尽可能减少栅格的有效面积。

下面说了 组件碰撞 如何应用栅格计算，咱们再总结一下：断定组件碰撞，只有找到以后组件所在的栅格 areas，遍历每一个栅格区域内的组件即可。

除了碰撞判断外，磁贴拖拽过程中还有两个场景须要计算组件间碰撞关系，次要包含 落点地位 与 落点后组件排序 两个场景。

比方上面的例子：

蓝色框为鼠标拖动组件时，鼠标的实时地位，而红色背景正方形示意 落点地位 ，红色正方形下方的组件属于 落点后组件，这些组件因为红色正方形的地位插入，须要从新计算地位。

为了最大水平利用栅格优化性能，这两种状况须要别离判断。

因为磁贴布局的重力是垂直向上的，因而落点只会落在以后组件的上方，也就是落点只会与上方组件碰撞，因而思考垂直向上的栅格区域即可。而且过程中还是能够优化的，即一格一格向上查找，只有在某个格内查到碰撞组件，就能够终止查找了：

  [---] │        │
  [A] │        │
  [---] │        │
────────┼────────┼─────────
     [-----]     │
     [B]     │
     [-----]     │
────────┼────────┼─────────
[-----] │        │
[C] │        │
[-----] │        │
────────┼────────┼─────────
    [-----]      │
    [D]      │
    [-----]      │

如下面的例子，挪动 D 时：

先思考 D 所在区域是否有组件垂直区域可碰撞，因为 D 所在区域只有本人，所以跳过。
在思考 D 区域上方一格区域，发现组件 C，且与 D 在垂直地位可碰撞，因而 D 的落点地位放在 C 的下方。
查找完结，再向上的区域间接跳过。

因而落点地位的查找时间复杂度是 O(1)。

落点地位决定后，因为落点地位毕竟产生了变动，落点之后的组件都要从新依照磁贴向上的重力作用排序，所以此时组件查找范畴是蕴含落点所在区域内，垂直向下的所有区域：

  [---] │        │
  [A] │        │
  [---] │        │
────────┼────────┼─────────
     [-----]     │
     [B]     │
     [-----]     │
────────┼────────┼─────────
[-----] │        │
[C] │        │
[-----] │        │
────────┼────────┼─────────
    [-----]      │
    [D]      │
    [-----]      │

如下面的例子，挪动 A 时，A 所在区域下方所有区域都要从新判断落点，也就是 B、C、D 组件所在区域。其余区域不受影响。咱们假如所有组件平均的平铺在所有区域，那么最坏的状况下（挪动的组件在最顶部，那么一整条高度的区域都要搜寻）纵向区域的组件数是 logn，所以工夫复杂度实践上是 O(logn)。但个别状况磁贴布局高度远大于宽度，所以可能往较坏的 O(n) 复杂度倒退，但不论如何，这个线性性能是可承受的。

通过优化，磁贴布局在拖拽前、中、后各个阶段的计算复杂度均为 O(n)，即一个领有 500 个组件实例的简单画布，也只有在每次拖动时循环 500 次计算地位，而配合空间换工夫的一些 Map 映射关系配合，500 次计算加起来最多耗费 2~3 ms，而 1000 个组件实例也最多 4~6 ms 的耗费，但超过 1000 个组件实例的画布简直是不可能存在的，况且这里 log(n) 的 n 指的是每个容器内的组件，因而只有单个容器内组件数量简直不会超过特地多，所以性能是没有问题的。