欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

總結(jié)在前端排序中遇到的問題

 更新時間:2016年07月19日 09:07:48   投稿:daisy  
這篇文章給大家羅列了在前段排序中會遇到的問題并寫了解決方案,非常詳細,有需要的朋友可以參考。

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

前端排序

前端排序的場景

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

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

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

排序算法

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

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

JavaScript的排序

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

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

Array.prototype.sort規(guī)范

Array.prototype.sort(compareFn)

復制代碼 代碼如下:

The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y.

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

在這樣的背景下,前端排序這件事其實取決于各家瀏覽器的具體實現(xiàn)。那么,當今主流的瀏覽器關(guān)于排序是怎么實現(xiàn)的呢?接下來,我們分別簡單對比一下 Chrome、FirefoxMicrosoft 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)已被關(guān)閉。但是于2013年6月被開發(fā)組成員重新打開,作為 ECMAScript Next 規(guī)范討論的參考。

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

復制代碼 代碼如下:

It does not change. Stable is a subset of unstable. And vice versa, every unstable algorithm returns a stable result for some inputs. Mark's point is that requiring “always unstable” has no meaning, no matter what language you chose.
/Andreas

正如本文前段所引用的已定稿 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 設(shè)計的一個重要考量在于引擎的性能。

快速排序 相比較于 歸并排序,在整體性能上表現(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)是設(shè)定一個閾值,對最下層的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));
};

以上代碼的主要問題在于:利用 leftright 兩個數(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)定排序,那該怎么辦呢?

解決方案

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

瀏覽器出于不同考慮選擇不同排序算法。可能某些偏向于追求極致的性能,某些偏向于提供良好的開發(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 的一篇排序相關(guān)的Bug。大致意思是討論過程中有人建議用極端情況下性能更好的 Timsort 算法替換 歸并排序,但是 Mozilla 的工程師表示由于 Timsort 算法存在License授權(quán)問題,沒辦法在 Mozilla 的軟件中直接使用算法,等待對方的后續(xù)回復

總結(jié)

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

相關(guān)文章

  • 一個炫酷的Bootstrap導航菜單

    一個炫酷的Bootstrap導航菜單

    這篇文章主要為大家詳細介紹了一個炫酷的Bootstrap導航菜單的制作方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2016-12-12
  • JS實現(xiàn)點擊事件統(tǒng)計的簡單實例

    JS實現(xiàn)點擊事件統(tǒng)計的簡單實例

    下面小編就為大家?guī)硪黄狫S實現(xiàn)點擊事件統(tǒng)計的簡單實例。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-07-07
  • JavaScript實現(xiàn)10秒后再次獲取驗證碼

    JavaScript實現(xiàn)10秒后再次獲取驗證碼

    這篇文章主要為大家詳細介紹了JavaScript實現(xiàn)10秒后再次獲取驗證碼,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-12-12
  • js數(shù)組的五種迭代方法及兩種歸并方法(推薦)

    js數(shù)組的五種迭代方法及兩種歸并方法(推薦)

    下面小編就為大家?guī)硪黄猨s數(shù)組的五種迭代方法及兩種歸并方法(推薦)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-06-06
  • 使用typescript+webpack構(gòu)建一個js庫的示例詳解

    使用typescript+webpack構(gòu)建一個js庫的示例詳解

    這篇文章主要介紹了typescript+webpack構(gòu)建一個js庫,本文主要記錄使用typescript配合webpack打包一個javascript library的配置過程,需要的朋友可以參考下
    2022-07-07
  • JS實現(xiàn)超簡單的鼠標拖動效果

    JS實現(xiàn)超簡單的鼠標拖動效果

    這篇文章主要介紹了JS實現(xiàn)超簡單的鼠標拖動效果,涉及JavaScript響應鼠標事件動態(tài)操作頁面元素的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-11-11
  • 基于JavaScript實現(xiàn)瀑布流布局(二)

    基于JavaScript實現(xiàn)瀑布流布局(二)

    這篇文章主要介紹了原生JavaScript實現(xiàn)瀑布流布局的相關(guān)資料,實現(xiàn)鼠標下拉圖片自動加載效果,和百度圖片效果類似,需要的朋友可以參考下
    2016-01-01
  • javascript實現(xiàn)數(shù)字配對游戲的實例講解

    javascript實現(xiàn)數(shù)字配對游戲的實例講解

    下面小編就為大家分享一篇javascript實現(xiàn)數(shù)字配對游戲的實例講解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2017-12-12
  • 如何基于uni-app實現(xiàn)微信小程序一鍵登錄與退出登錄功能

    如何基于uni-app實現(xiàn)微信小程序一鍵登錄與退出登錄功能

    uni-app 是使用vue的語法+小程序的標簽和API的一套框架,是一套代碼多端使用,目前是大前端的一種趨勢,下面這篇文章主要給大家介紹了關(guān)于如何基于uni-app實現(xiàn)微信小程序一鍵登錄與退出登錄功能的相關(guān)資料,需要的朋友可以參考下
    2022-09-09
  • Js中async/await的執(zhí)行順序詳解

    Js中async/await的執(zhí)行順序詳解

    隨著async/await正式納入ES7標準,越來越多的人開始研究據(jù)說是異步編程終級解決方案的 async/await。下面這篇文章主要給大家介紹了關(guān)于Js中async/await執(zhí)行順序的相關(guān)資料,需要的朋友可以參考借鑒,下面來一起看看吧。
    2017-09-09

最新評論