如何批量排序JS数组(性能)

Question

我有一个JS应用程序需要做一个复杂的大型数组,然后显示它.使用内置array.sort(cb)方法可能需要1秒钟的数据.这足以让我的UI变得笨拙.

因为UI的高度足以在屏幕上显示已排序数组的子集,其余部分位于滚动或分页下方,所以我有了一个想法.如果我制作了一个通过大型数组并快速排序的算法,前N个项目完全排序,但数组中的其余项目未完全排序,该怎么办？每次运行算法时,它都会从上到下对数组进行排序.

因此,我可以将处理分解成块并具有流畅的UI.在最初的几秒钟内,阵列将无法完美排序,但缺陷将位于滚动下方,因此不会被注意到.

我天真的解决方案是编写我自己的"选择排序",能够在N次匹配后中断并稍后恢复,但"选择排序"是一个非常糟糕的算法.更快的算法(根据我的理解)必须完成以保证前N个项目是稳定的.

有谁知道现有的解决方案吗？我疯了吗？有什么建议？

UPDATE

根据@moreON提出的想法,我写了一个自定义的QuickSort,一旦它具有所需的精度就会挽救.此数据的本机排序需要1秒.常规QuickSort大约需要250毫秒,这已经出乎意料地好了.在排序前100个项目后匆匆忙忙的QuickSort活跃了10ms,这要好得多.然后我可以再花250ms来完成排序,但这并不重要,因为用户已经在查看数据了.这将用户经历的延迟从1秒减少到10毫秒,这非常棒.

//Init 1 million random integers into array
var arr1 = [];
var arr2 = [];
for(var i=0;i<1800000;i++) {
   var num = Math.floor(Math.random() * 1000000);
   arr1.push(num);
   arr2.push(num);
}
console.log(arr1);

//native sort
console.time("native sort");
arr1.sort(function(a,b) { return a-b; });
console.timeEnd("native sort"); //1sec
console.log(arr1);

//quicksort sort    Ref: https://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/
function swap(arr, a, b) {
   var temp = arr[a];
   arr[a] = arr[b];
   arr[b] = temp;
}
function cmp(a,b) {
   return (a<b);
}
function partition(items, left, right) {
   var pivot = items[Math.floor((right + left) / 2)];
   var i = left;
   var j = right;

   while (i <= j) {
      while (cmp(items[i],pivot)) i++;
      while (cmp(pivot,items[j])) j--;
      if (i <= j) {
         swap(items, i, j);
         i++;
         j--;
      }
   }
   return i;
}
function quickSort(items, left, right, max) {    
   if(max && left-1 > max) return items; //bail out early if we have enough
   if (items.length > 1) {
      var index = partition(items, left, right);
      if (left < index - 1) quickSort(items, left, index - 1, max);
      if (index < right) quickSort(items, index, right, max);
   }
   return items;
}

//sort first 100
console.time("partial Quicksort");
arr2 = quickSort(arr2,0,arr2.length-1,100);
console.timeEnd("partial Quicksort"); //10ms
console.log(arr2);

//sort remainder
console.time("finishing Quicksort");
arr2 = quickSort(arr2,100,arr2.length-1); //250ms
console.timeEnd("finishing Quicksort");    
console.log(arr2);

Answer 1

首先，对绩效改进预期有一些看法。高效的排序算法为 O(N * log2(N))。对于 N=1,000,000 个项目，N * log2(N) ~ N * 20。我怀疑您尝试在网页中呈现那么多项目。

如果您只需要渲染前 25 行，选择排序将需要 N * 25 来对它们进行排序，因此假设开销相当恒定，它实际上会表现更差。

如果您确实想进一步尝试这一点，我能想到的一种算法是：维护 PAGE_SIZE 最小项目的二叉树。通过一次数据传递不断更新它，当发现较小的项目时删除最大的项目。忽略重新平衡，您将需要 N * log2(PAGE_SIZE) 来填充树并呈现第一页结果。