貌似前端圈一直以來流傳著一種誤解：前端用不到算法知識。長久以來，大家或許都曾受這種說法的影響。直到前陣子遇到一個產(chǎn)品需求，回過頭來看，發(fā)現(xiàn)事實并非如此。

前端排序

前端排序的場景

前端將排序條件作為請求參數(shù)傳遞給后端，后端將排序結(jié)果作為請求響應返回前端，這是一種常見設計。但是對于有些產(chǎn)品則不是那么適用。

試想一個場景：你在使用美食類APP時，是否會經(jīng)常切換排序方式，一會兒按照價格排序，一會兒按照評分排序。

實際生產(chǎn)中，受限于服務器成本等因素，當單次數(shù)據(jù)查詢成為整體性能瓶頸時，也會考慮通過將排序在前端完成的方式來優(yōu)化性能。

排序算法

感覺這個沒什么介紹的必要，作為計算機科學的一種基礎算法，描述就直接照搬 Wikipedia。

這里存在這一段內(nèi)容純粹是為了承(cou)上(man)啟(zi)下(shu)。

JavaScript的排序

既然說到前端排序，自然首先會想到JavaScript的原生接口 Array.prototype.sort。

這個接口自 ECMAScript 1st Edition 起就存在。讓我們看看最新的規(guī)范中關于它的描述是什么樣的。

Array.prototype.sort規(guī)范

Array.prototype.sort(compareFn)

顯然，規(guī)范并沒有限定 sort 內(nèi)部實現(xiàn)的排序算法是什么。甚至接口的實現(xiàn)都不需要是 穩(wěn)定排序 的。這一點很關鍵，接下來會多次涉及。

在這樣的背景下，前端排序這件事其實取決于各家瀏覽器的具體實現(xiàn)。那么，當今主流的瀏覽器關于排序是怎么實現(xiàn)的呢？接下來，我們分別簡單對比一下 Chrome、Firefox 和 Microsoft Edge。

Chrome中的實現(xiàn)

Chrome 的JavaScript引擎是 v8。由于它是開源的，所以可以直接看源代碼。

整個 array.js 都是用 JavaScript 語言實現(xiàn)的。排序方法部分很明顯比曾經(jīng)看到過的快速排序要復雜得多，但顯然核心算法還是 快速排序。算法復雜的原因在于 v8 出于性能考慮進行了很多優(yōu)化。(接下來會展開說)

Firefox中的實現(xiàn)

暫時無法確定Firefox的JavaScript引擎即將使用的數(shù)組排序算法會是什么。[3]

按照現(xiàn)有的信息，SpiderMoney 內(nèi)部實現(xiàn)了 歸并排序。

Microsoft Edge中的實現(xiàn)

Microsoft Edge 的JavaScript引擎 Chakra 的核心部分代碼已經(jīng)于2016年初在Github開源。

通過看源代碼可以發(fā)現(xiàn)，Chakra 的數(shù)組排序算法實現(xiàn)的也是 快速排序。而且相比較于 v8，它就只是實現(xiàn)了純粹的快速排序，完全沒有 v8 中的那些性能優(yōu)化的蹤影。

JavaScript數(shù)組排序的問題

眾所周知，快速排序 是一種不穩(wěn)定的排序算法，而 歸并排序 是一種穩(wěn)定的排序算法。由于不同引擎在算法選擇上的差異，導致前端依賴 Array.prototype.sort 接口實現(xiàn)的JavaScript代碼，在瀏覽器中實際執(zhí)行的排序效果是不一致的。

排序穩(wěn)定性的差異需要有特定的場景觸發(fā)才會存在問題；在很多情況下，不穩(wěn)定的排序也不會造成影響。

假如實際項目開發(fā)中，對于數(shù)組的排序沒有穩(wěn)定性的需求，那么其實看到這里為止即可，瀏覽器之間的實現(xiàn)差異不那么重要。

但是若項目要求排序必須是穩(wěn)定的，那么這些差異的存在將無法滿足需求。我們需要為此進行一些額外的工作。

舉個例子：

某市的機動車牌照拍賣系統(tǒng)，最終中標的規(guī)則為：

    1. 按價格進行倒排序；

    2. 相同價格則按照競標順位（即價格提交時間）進行正排序。

排序若是在前端進行，那么采用快速排序的瀏覽器中顯示的中標者很可能是不符合預期的

探究差異的背后

尋找解決辦法之前，我們有必要先探究一下出現(xiàn)問題的原因。

Chrome為什么采用快速排序

其實這個情況從一開始便存在。

Chrome測試版 于2008年9月2日發(fā)布，然而發(fā)布后不久，就有開發(fā)者向 Chromium 開發(fā)組提交#90 Bug反饋v8的數(shù)組排序?qū)崿F(xiàn)不是穩(wěn)定排序的。

這個Bug ISSUE討論的時間跨度很大。一直到2015年11月10日，仍然有開發(fā)者對v8的數(shù)組排序?qū)崿F(xiàn)問題提出評論。

同時我們還注意到，該ISSUE曾經(jīng)已被關閉。但是于2013年6月被開發(fā)組成員重新打開，作為 ECMAScript Next 規(guī)范討論的參考。

而es-discuss的最后結(jié)論是這樣的

正如本文前段所引用的已定稿 ECMAScript 2015 規(guī)范中的描述。

時代特點

IMHO，Chrome發(fā)布之初即被報告出這個問題可能是有其特殊的時代特點。

上文已經(jīng)說到，Chrome第一版 是 2008年9月 發(fā)布的。根據(jù)statcounter的統(tǒng)計數(shù)據(jù)，那個時期市場占有率最高的兩款瀏覽器分別是 IE(那時候只有IE6和IE7) 和 Firefox，市場占有率分別達到了67.16%和25.77%。也就是說，兩個瀏覽器加起來的市場占有率超過了90%。

而根據(jù)另一份瀏覽器排序算法穩(wěn)定性的統(tǒng)計數(shù)據(jù)顯示，這兩款超過了90%市場占有率的瀏覽器都采用了穩(wěn)定的數(shù)組排序。所以Chrome發(fā)布之初被開發(fā)者質(zhì)疑也是合情合理的。

符合規(guī)范

從Bug ISSUE討論的過程中，可以大概理解開發(fā)組成員對于引擎實現(xiàn)采用快速排序的一些考量。

其中一點，他們認為引擎必須遵守ECMAScript規(guī)范。由于規(guī)范不要求穩(wěn)定排序的描述，故他們認為 v8 的實現(xiàn)是完全符合規(guī)范的。

性能考慮

另外，他們認為 v8 設計的一個重要考量在于引擎的性能。

快速排序 相比較于 歸并排序，在整體性能上表現(xiàn)更好：

更高的計算效率?？焖倥判?在實際計算機執(zhí)行環(huán)境中比同等時間復雜度的其他排序算法更快（不命中最差組合的情況下）
更低的空間成本。前者僅有O(㏒n)的空間復雜度，相比較后者O(n)的空間復雜度在運行時的內(nèi)存消耗更少
v8在數(shù)組排序算法中的性能優(yōu)化

既然說 v8 非?？粗幸娴男阅埽敲丛跀?shù)組排序中它做了哪些事呢？

通過閱讀源代碼，還是粗淺地學習了一些皮毛。

混合插入排序
快速排序 是分治的思想，將大數(shù)組分解，逐層往下遞歸。但是若遞歸深度太大，為了維持遞歸調(diào)用棧的內(nèi)存資源消耗也會很大。優(yōu)化不好甚至可能造成棧溢出。

目前v8的實現(xiàn)是設定一個閾值，對最下層的10個及以下長度的小數(shù)組使用 插入排序。

根據(jù)代碼注釋以及 Wikipedia 中的描述，雖然插入排序的平均時間復雜度為 O(n²) 差于快速排序的 O(n㏒n)。但是在運行環(huán)境，小數(shù)組使用插入排序的效率反而比快速排序會更高，這里不再展開。

v8代碼示例

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;
    }
    ......
  }
  ......
};

三數(shù)取中

正如已知的，快速排序的阿克琉斯之踵在于，最差數(shù)組組合情況下會算法退化。

快速排序的算法核心在于選擇一個基準 (pivot)，將經(jīng)過比較交換的數(shù)組按基準分解為兩個數(shù)區(qū)進行后續(xù)遞歸。試想如果對一個已經(jīng)有序的數(shù)組，每次選擇基準元素時總是選擇第一個或者最后一個元素，那么每次都會有一個數(shù)區(qū)是空的，遞歸的層數(shù)將達到 n，最后導致算法的時間復雜度退化為 O(n²)。因此 pivot 的選擇非常重要。

v8采用的是 三數(shù)取中(median-of-three) 的優(yōu)化：除了頭尾兩個元素再額外選擇一個元素參與基準元素的競爭。

第三個元素的選取策略大致為：

當數(shù)組長度小于等于1000時，選擇折半位置的元素作為目標元素。
當數(shù)組長度超過1000時，每隔200-215個(非固定，跟著數(shù)組長度而變化)左右選擇一個元素來先確定一批候選元素。接著在這批候選元素中進行一次排序，將所得的中位值作為目標元素
最后取三個元素的中位值作為 pivot。

v8代碼示例

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);
    }
  }
  ......
};

原地排序

在溫習快速排序算法時，我在網(wǎng)上看到了很多用JavaScript實現(xiàn)的例子。

但是發(fā)現(xiàn)一大部分的代碼實現(xiàn)如下所示

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 兩個數(shù)區(qū)存儲遞歸的子數(shù)組，因此它需要 O(n) 的額外存儲空間。這與理論上的平均空間復雜度 O(㏒n) 相比差距較大。

額外的空間開銷，同樣會影響實際運行時的整體速度。這也是快速排序在實際運行時的表現(xiàn)可以超過同等時間復雜度級別的其他排序算法的其中一個原因。所以一般來說，性能較好的快速排序會采用原地 (in-place) 排序的方式。

v8 源代碼中的實現(xiàn)是對原數(shù)組進行元素交換。

Firefox為什么采用歸并排序

它的背后也是有故事的。

Firefox其實在一開始發(fā)布的時候?qū)τ跀?shù)組排序的實現(xiàn)并不是采用穩(wěn)定的排序算法，這塊有據(jù)可考。

Firefox(Firebird)最初版本 實現(xiàn)的數(shù)組排序算法是 堆排序，這也是一種不穩(wěn)定的排序算法。因此，后來有人對此提交了一個Bug。

Mozilla開發(fā)組內(nèi)部針對這個問題進行了一系列討論。

從討論的過程我們能夠得出幾點

1.同時期 Mozilla 的競爭對手是 IE6，從上文的統(tǒng)計數(shù)據(jù)可知IE6是穩(wěn)定排序的

2.JavaScript之父 Brendan Eich 覺得 Stability is good

3.Firefox在采用 堆排序 之前采用的是 快速排序

基于開發(fā)組成員傾向于實現(xiàn)穩(wěn)定的排序算法為主要前提，F(xiàn)irefox3 將 歸并排序 作為了數(shù)組排序的新實現(xiàn)。

解決排序穩(wěn)定性的差異

以上說了這么多，主要是為了講述各個瀏覽器對于排序?qū)崿F(xiàn)的差異，以及解釋為什么存在這些差異的一些比較表層的原因。

但是讀到這里，讀者可能還是會有疑問：如果我的項目就是需要依賴穩(wěn)定排序，那該怎么辦呢？

解決方案

其實解決這個問題的思路比較簡單。

瀏覽器出于不同考慮選擇不同排序算法?？赡苣承┢蛴谧非髽O致的性能，某些偏向于提供良好的開發(fā)體驗，但是有規(guī)律可循。

從目前已知的情況來看，所有主流瀏覽器（包括IE6，7，8）對于數(shù)組排序算法的實現(xiàn)基本可以枚舉：

1.歸并排序 / Timsort

2.快速排序

所以，我們將快速排序經(jīng)過定制改造，變成穩(wěn)定排序的是不是就可以了？

一般來說，針對對象數(shù)組使用不穩(wěn)定排序會影響結(jié)果。而其他類型數(shù)組本身使用穩(wěn)定排序或不穩(wěn)定排序的結(jié)果是相等的。因此方案大致如下：

將待排序數(shù)組進行預處理，為每個待排序的對象增加自然序?qū)傩?，不與對象的其他屬性沖突即可。
自定義排序比較方法compareFn，總是將自然序作為前置判斷相等時的第二判斷維度。

面對歸并排序這類實現(xiàn)時由于算法本身就是穩(wěn)定的，額外增加的自然序比較并不會改變排序結(jié)果，所以方案兼容性比較好。

但是涉及修改待排序數(shù)組，而且需要開辟額外空間用于存儲自然序?qū)傩裕上攵?v8 這類引擎應該不會采用類似手段。不過作為開發(fā)者自行定制的排序方案是可行的。

方案代碼示例

'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));
}

以上只是一個簡單的滿足穩(wěn)定排序的算法改造示例。

之所以說簡單，是因為實際生產(chǎn)環(huán)境中作為數(shù)組輸入的數(shù)據(jù)結(jié)構(gòu)冗雜，需要根據(jù)實際情況判斷是否需要進行更多樣的排序前類型檢測。

標注

1.前端現(xiàn)在已經(jīng)是一個比較寬泛的概念。本文中的前端主要指的是以瀏覽器作為載體，以 JavaScript 作為編程語言的環(huán)境

2.本文無意于涉及算法整體，謹以常見的排序算法作為切入點

3.在確認 Firefox 數(shù)組排序?qū)崿F(xiàn)的算法時，搜到了 SpiderMoney 的一篇排序相關的Bug。大致意思是討論過程中有人建議用極端情況下性能更好的 Timsort 算法替換 歸并排序，但是 Mozilla 的工程師表示由于 Timsort 算法存在License授權問題，沒辦法在 Mozilla 的軟件中直接使用算法，等待對方的后續(xù)回復

總結(jié)

以上就是大家在前端排序中遇到的問題總結(jié)和解決方案，這幾年越來越多的項目正在往富客戶端應用方向轉(zhuǎn)變，前端在項目中的占比變大。隨著未來瀏覽器計算能力的進一步提升，它允許進行一些更復雜的計算。伴隨職責的變更，前端的形態(tài)也可能會發(fā)生一些重大變化。行走江湖，總要有一技傍身。

最新評論