共计 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，遍历每一个栅格区域内的组件即可。
除了碰撞判断外，磁贴拖拽过程中还有两个场景须要计算组件间碰撞关系，次要包含 落点地位 与 落点后组件排序 两个场景。
比方上面的例子：
<img width=200 src=”https://user-images.githubusercontent.com/7970947/209458368-80dcd2b4-b6ee-4df9-adb7-271171352844.png”>
蓝色框为鼠标拖动组件时，鼠标的实时地位，而红色背景正方形示意 落点地位 ，红色正方形下方的组件属于 落点后组件，这些组件因为红色正方形的地位插入，须要从新计算地位。
为了最大水平利用栅格优化性能，这两种状况须要别离判断。
落点地位
因为磁贴布局的重力是垂直向上的，因而落点只会落在以后组件的上方，也就是落点只会与上方组件碰撞，因而思考垂直向上的栅格区域即可。而且过程中还是能够优化的，即一格一格向上查找，只有在某个格内查到碰撞组件，就能够终止查找了：
[---] │ │
[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 指的是每个容器内的组件，因而只有单个容器内组件数量简直不会超过特地多，所以性能是没有问题的。
探讨地址是：精读《磁贴布局 – 性能优化》· Issue #461 · dt-fe/weekly
如果你想参加探讨，请 点击这里，每周都有新的主题，周末或周一公布。前端精读 – 帮你筛选靠谱的内容。
关注 前端精读微信公众号
<img width=200 src=”https://img.alicdn.com/tfs/TB165W0MCzqK1RjSZFLXXcn2XXa-258-258.jpg”>
版权申明：自在转载 - 非商用 - 非衍生 - 放弃署名（创意共享 3.0 许可证）
