)我有一個JS應用程序需要做一個複雜的大型數組,然後顯示它。使用內置的array.sort(cb)
方法可能需要1秒鐘的時間才能處理我的數據。這足以讓我的用戶界面變得很笨拙。如何批量排序JS數組(
由於用戶界面的高度足以顯示屏幕上的排序數組的子集,其餘部分位於滾動或分頁之下,因此我有一個想法。如果我製作了一個通過大型數組的算法,並且快速按照前N個項目完全排序的方式進行排序,但是數組中的其餘項不完全排序。每次運行我的算法時,它都會從上到下排列更多的數組。
因此,我可以將我的處理分解爲塊並擁有流暢的UI。在頭幾秒鐘數組不會被完美排序,但缺陷會在滾動下方,所以他們不會被注意到。
我天真的解決方案是編寫我自己的「選擇排序」,能夠在N次匹配後中斷並稍後恢復,但「選擇排序」是一個非常糟糕的算法。更快的算法(從我的理解)必須完成,以確保前N個項目是穩定的。
有沒有人知道現有的解決方案呢?我瘋了嗎?有什麼建議麼?
UPDATE
回吐@moreON提出這個想法,我寫道,撈出一旦它具有精度要求的自定義快速排序。這種數據的本地排序需要1秒。常規的QuickSort花費了大約250毫秒,這已經非常好了。在排序前100個項目後排序的QuickSort花了10毫秒,這要好得多。然後我可以再花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);
請加你嘗試。 –
如果您的數據集沒有完全排序,是不是有可能第一個項目不應該是您向用戶展示的數組中的第一個項目? – Bryce
對不起,但我認爲你可能有點瘋狂,我想糾正,但我不認爲你可以保證沒有訪問所有項目的部分排序。至多你可以保證**你已經排序的項目**,它們是完全分類的。在至少訪問過一次之前,您無法與剩餘的項目交談。 「選擇排序」將工作,但它的指數算法,瘋狂緩慢。我非常確定'array.sort'是一種快速排序,對於大多數數據分佈來說,你可能無法做得更好。 – Jim