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

前端排序

前端排序的場(chǎng)景

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

試想一個(gè)場(chǎng)景：你在使用美食類APP時(shí)，是否會(huì)經(jīng)常切換排序方式，一會(huì)兒按照價(jià)格排序，一會(huì)兒按照評(píng)分排序。

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

排序算法

感覺這個(gè)沒什么介紹的必要，作為計(jì)算機(jī)科學(xué)的一種基礎(chǔ)算法，描述就直接照搬 Wikipedia。

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

JavaScript的排序

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

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

Array.prototype.sort規(guī)范

Array.prototype.sort(compareFn)

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

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

Chrome中的實(shí)現(xiàn)

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

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

Firefox中的實(shí)現(xiàn)

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

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

Microsoft Edge中的實(shí)現(xiàn)

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

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

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

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

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

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

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

舉個(gè)例子：

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

    1. 按價(jià)格進(jìn)行倒排序；

    2. 相同價(jià)格則按照競(jìng)標(biāo)順位（即價(jià)格提交時(shí)間）進(jìn)行正排序。

排序若是在前端進(jìn)行，那么采用快速排序的瀏覽器中顯示的中標(biāo)者很可能是不符合預(yù)期的

探究差異的背后

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

Chrome為什么采用快速排序

其實(shí)這個(gè)情況從一開始便存在。

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

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

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

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

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

時(shí)代特點(diǎn)

IMHO，Chrome發(fā)布之初即被報(bào)告出這個(gè)問題可能是有其特殊的時(shí)代特點(diǎn)。

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

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

符合規(guī)范

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

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

性能考慮

另外，他們認(rèn)為 v8 設(shè)計(jì)的一個(gè)重要考量在于引擎的性能。

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

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

既然說 v8 非常看中引擎的性能，那么在數(shù)組排序中它做了哪些事呢？

通過閱讀源代碼，還是粗淺地學(xué)習(xí)了一些皮毛。

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

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

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

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ù)組組合情況下會(huì)算法退化。

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

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

第三個(gè)元素的選取策略大致為：

當(dāng)數(shù)組長(zhǎng)度小于等于1000時(shí)，選擇折半位置的元素作為目標(biāo)元素。
當(dāng)數(shù)組長(zhǎng)度超過1000時(shí)，每隔200-215個(gè)(非固定，跟著數(shù)組長(zhǎng)度而變化)左右選擇一個(gè)元素來先確定一批候選元素。接著在這批候選元素中進(jìn)行一次排序，將所得的中位值作為目標(biāo)元素
最后取三個(gè)元素的中位值作為 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);
    }
  }
  ......
};

原地排序

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

但是發(fā)現(xiàn)一大部分的代碼實(shí)現(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 兩個(gè)數(shù)區(qū)存儲(chǔ)遞歸的子數(shù)組，因此它需要 O(n) 的額外存儲(chǔ)空間。這與理論上的平均空間復(fù)雜度 O(㏒n) 相比差距較大。

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

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

Firefox為什么采用歸并排序

它的背后也是有故事的。

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

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

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

從討論的過程我們能夠得出幾點(diǎn)

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

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

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

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

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

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

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

解決方案

其實(shí)解決這個(gè)問題的思路比較簡(jiǎn)單。

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

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

1.歸并排序 / Timsort

2.快速排序

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

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

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

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

但是涉及修改待排序數(shù)組，而且需要開辟額外空間用于存儲(chǔ)自然序?qū)傩裕上攵?v8 這類引擎應(yīng)該不會(huì)采用類似手段。不過作為開發(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));
}

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

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

標(biāo)注

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

2.本文無意于涉及算法整體，謹(jǐn)以常見的排序算法作為切入點(diǎn)

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

總結(jié)

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

最新評(píng)論