DIV CSS 佈局教程網

前端排序踩坑記:Array.prototype.sort 的穩定性差異與解法
編輯:關於JavaScript     

前端圈流傳很久的一句話是「前端用不到演算法」。這個說法影響了不少人,直到某次接到一個產品需求,回頭再看才發現並非如此。

為什麼排序會跑到前端

把排序條件當請求參數丟給後端、由後端回傳排好的結果,是很常見的設計。但有些產品並不適用:想想你用的美食類 App,使用者往往會頻繁切換排序方式,一下按價格、一下按評分。每次切換都打一次後端,成本並不划算。

而在實際生產環境中,當單次查詢成為效能瓶頸時,把排序移到前端完成,也是一種合理的優化手段。

規範怎麼說

談前端排序,第一個想到的当然是原生介面 Array.prototype.sort,它從 ECMAScript 1st Edition 就存在。最新規範對它的描述大意是:

陣列元素會被排序,且不保證穩定——比較結果相等的元素,不保證維持原本的相對順序。若提供了 comparefn,它應該接受兩個參數 x 與 y,x < y 回傳負值、x = y 回傳 0、x > y 回傳正值。

關鍵就在那句「不保證穩定」。規範既沒限定 sort 內部要用哪種排序演算法,也不要求結果穩定。這意味著實際行為完全取決於各瀏覽器的實作。

各家引擎的實作

· Chrome(V8):整個 array.js 用 JavaScript 寫成,核心演算法是快速排序,程式碼之所以看起來複雜,是因為做了大量效能優化。

· Firefox(SpiderMonkey):內部實作的是合併排序,屬於穩定排序。

· Microsoft Edge(Chakra):核心程式碼已於 2016 年初在 GitHub 開源,實作的也是快速排序,而且是相當樸素、沒有 V8 那種效能優化的版本。

問題浮現

快速排序不穩定,合併排序穩定。引擎選擇不同,同一段依賴 Array.prototype.sort 的程式碼,在不同瀏覽器上跑出來的排序結果就可能不一致。

如果專案對排序穩定性沒有要求,看到這裡其實就夠了,差異無傷大雅。但一旦需求要求穩定排序,這些差異就會變成 bug。

舉個例子:某市機動車牌照拍賣系統,最終中標規則是——

1. 依出價由高到低排序;

2. 出價相同者,依競標順位(也就是出價時間先後)正序排列。

如果排序在前端進行,那麼在採用快速排序的瀏覽器上,顯示的中標者很可能與預期不符。

差異從何而來

Chrome 為何選快速排序

這件事從一開始就存在。Chrome 測試版於 2008 年 9 月發布,不久就有開發者向 Chromium 團隊回報「V8 的陣列排序不是穩定排序」。這個 Issue 討論跨度極大,直到 2015 年 11 月仍有開發者在上面留言;它曾被關閉,又於 2013 年 6 月被重新開啟,作為 ECMAScript Next 的規範討論參考。

es-discuss 最後的結論大意是:這不會改變。穩定是不穩定的子集,反過來說,任何不穩定的演算法在某些輸入下也會給出穩定的結果,因此「要求永遠不穩定」這種描述本身沒有意義。

兩個現實因素可以解釋這個決定。其一是符合規範:規範既然不要求穩定,團隊認為 V8 的實作完全合規。其二是效能:快速排序在整體效能上優於合併排序——實際環境中的計算效率更高(不碰上最差組合時),且空間成本更低,前者空間複雜度僅 O(log n),後者為 O(n)。

另外值得注意的是時代背景。2008 年 Chrome 第一版問世時,市佔率最高的兩款瀏覽器是 IE(當時只有 IE6 與 IE7)與 Firefox,分別約 67.16% 與 25.77%,兩者合計超過九成,而它們都採用穩定排序。以當時的環境來看,開發者的質疑合情合理。

V8 在排序上做了哪些優化

混合插入排序:快速排序是分治思想,逐層遞迴分解大陣列,但遞迴太深會帶來可觀的呼叫堆疊開銷,處理不好甚至可能爆堆疊。V8 的做法是設一個閾值,對長度 10 及以下的子陣列改用插入排序。插入排序平均時間複雜度 O(n²) 雖不如快速排序的 O(n log n),但在小陣列上實際反而更快。

var QuickSort = function QuickSort(a, from, to) {
  ......
  while (true) {
    // Insertion sort is faster for short arrays.
    if (to - from <= 10) {
      InsertionSort(a, from, to);
      return;
    }
    ......
  }
  ......
};

三數取中:快速排序的致命弱點在於最壞情況會退化。基準點(pivot)的選擇至關重要——若對一個已排序的陣列每次都選頭或尾當基準,每次分割都會有一側是空的,遞迴層數達到 n,時間複雜度退化成 O(n²)。V8 除了頭尾之外,另外挑一個元素一起競爭基準位置。第三個元素的選取策略大致是:陣列長度不超過 1000 時取折半位置的元素;超過 1000 時每隔約 200–215 個(非固定值,隨長度變化)挑一個候選,先對這批候選排序取中位數,最後再取三個元素的中位數作為 pivot。

var GetThirdIndex = function(a, from, to) {
  var t_array = new InternalArray();
  // Use both 'from' and 'to' to determine the pivot candidates.
  var increment = 200 + ((to - from) & 15);
  var j = 0;
  from += 1;
  to -= 1;
  for (var i = from; i < to; i += increment) {
    t_array[j] = [i, a[i]];
    j++;
  }
  t_array.sort(function(a, b) { return comparefn(a[1], b[1]); });
  var third_index = t_array[t_array.length >> 1][0];
  return third_index;
};

var QuickSort = function QuickSort(a, from, to) {
  ......
  while (true) {
    ......
    if (to - from > 1000) {
      third_index = GetThirdIndex(a, from, to);
    } else {
      third_index = from + ((to - from) >> 1);
    }
  }
  ......
};

原地排序:網路上不少用 JavaScript 實作快速排序的範例長這樣:

var quickSort = function(arr) {
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++){
    if (arr[i] < pivot) { left.push(arr[i]); }
    else { right.push(arr[i]); }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

問題在於它用 left 與 right 兩個陣列存遞迴子陣列,需要 O(n) 額外空間,與理論平均的 O(log n) 差距不小。額外空間配置同樣會拖慢實際執行速度——這也正是快速排序實測能勝過同時間複雜度量級的其他演算法的原因之一。所以效能取向的實作通常會採用原地(in-place)交換,V8 就是直接在原陣列上交換元素。

Firefox 為何選合併排序

這背後也有段故事。Firefox 最早(當時叫 Firebird)的陣列排序實作其實是堆排序,同樣不穩定,後來因此被提了一個 Bug。Mozilla 團隊的討論可以整理出幾點:當時的對手 IE6 是穩定排序;JavaScript 之父 Brendan Eich 認為「Stability is good」;Firefox 在改用堆排序之前用的是快速排序。在團隊傾向實作穩定排序的前提下,Firefox 3 把合併排序定為新的陣列排序實作。

怎麼解決穩定性問題

思路其實不複雜。主流瀏覽器(含 IE6、7、8)的陣列排序實作基本可以歸為兩類:合併排序/Timsort,以及快速排序。

一般來說,只有物件陣列遇到不穩定排序才會出問題;其他型別的陣列,用穩定或不穩定排序的結果是相等的。因此方案是:

1. 预处理待排序陣列,為每個物件加上一個自然序屬性(只要別和既有屬性名稱衝突即可)。

2. 自訂比較函式,把自然序作為「比較結果相等時」的第二判斷依據。

面對合併排序這類天生穩定的實作,多一層自然序比較不會改變結果,所以相容性很好。缺點是需要改動輸入陣列並額外配置空間,引擎本身大概不會這麼做,但作為開發者自行加上的方案完全可行。

'use strict';

const INDEX = Symbol('index');

function getComparer(compare) {
  return function (left, right) {
    let result = compare(left, right);
    return result === 0 ? left[INDEX] - right[INDEX] : result;
  };
}

function sort(array, compare) {
  array = array.map((item, index) => {
    if (typeof item === 'object') {
      item[INDEX] = index;
    }
    return item;
  });
  return array.sort(getComparer(compare));
}

這只是最基礎的改造示範。之所以說基礎,是因為真實環境中的輸入資料結構往往更雜,可能還需要在前置階段加入更多型別檢測。

幾點補充說明

1. 「前端」現在是個很寬的概念,本文指的是以瀏覽器為載體、以 JavaScript 為語言的環境。

2. 本文无意涵蓋演算法整體,只是以排序作為切入點。

3. 在查證 Firefox 的實作時,可以找到 SpiderMonkey 一個排序相關的討論:有人建議用極端情況下效能更好的 Timsort 取代合併排序,但 Mozilla 工程師表示 Timsort 存在授權問題,無法直接在自家軟體中使用。

結語

這幾年越來越多專案往富客戶端應用方向發展,前端在專案中的比重變大。隨著瀏覽器計算能力持續提升,它允許進行更複雜的計算,伴隨職責變化,前端形態也可能出現重大轉變。行走江湖,總要有一技傍身。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved