乐趣区

关于javascript:前端-BUG-录-因数组排序造成的卡顿

jiezi

前端 BUG 录 – 因 lodashjs debounce 去抖优化造成的 bug
这两个 BUG 其实是同一个 BUG，怎么说呢？两个都没错，错就错在同时应用了。

因为我 没解决边界，导致我会给一个大数组排序，造成了卡顿。而后卡顿造成了节流工夫成为了笑话。

发问

因为这个 BUG 其实有好几个 限定条件 才会触发，所以我先来提几个问题

  1. 5000 条 乱序 的数据，排序须要多少工夫？Array.prototype.sort
  2. 5000 条 有序 的数据，排序须要多少工夫？Array.prototype.sort
  3. 对于有序数据，什么样的算法适合？
  4. 对于无序数据，什么样的算法适合？
  5. Array.prototype.sort 应用的是什么算法？

这些灵魂拷问，你有答案吗？

我以后的这个场景是 分页拉取数据 ， 展现的时候要有序。

如果你有答案，那能够晓得，sort 对于我的这个场景不是很实用，插入排序应该是最优的抉择。

Array.prototype.sort 测试

地址：https://www.lilnong.top/static/html/user-session-list-virtual-insertsort-log-2.html

Array.prototype.shuffle = function() {
  let array = this;
  let len = array.length;
  for (let i = len - 1; i > 0; i--) {let j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
}
vm.list.shuffle();

console.time('a')
vm.list.sort((n,m)=>n.id-m.id);
console.timeEnd('a')

console.time('b')
vm.list.sort((n,m)=>n.id-m.id);
console.timeEnd('b')

console.time('c')
vm.list.sort((n,m)=>n.id-m.id);
console.timeEnd('c')

我遇到的问题 & 解决方案

Array.prototype.sort 代码有过降级

其实在新的浏览器中跑，我的计划也是能过来了，耗时也就 10ms 以下。
然而因为咱们是 pc 客户端 ，须要 兼容 xp 零碎，所以 chrome 的版本极低（40 多）。

新版本应用的其实是 timsort，timsort 是工业级算法，其混用插入排序与归并排序，二分搜寻等算法，亮点是充分利用待排序数据可能局部有序的事实，并且根据待排序数据内容动静扭转排序策略——选择性进行归并以及 galloping。什么是 Timsort 排序办法？

所以这里咱们能够把 sort 改成 timsort。

只须要一次插入排序

https://www.lilnong.top/static/html/user-session-list-virtual-insertsort-log-2.html

因为我的数据是有序的，所以 插入排序能够更快。

我依赖 lodash 的 _.sortedIndexBy 来实现，因为还有置顶规定，所以提供了一个计算权重的办法

微信公众号：前端 linong

欢送大家关注我的公众号。有疑难也能够加我的微信前端交换群。

退出移动版