フロントエンドのサークルには常に誤解があったようです。フロントエンドはアルゴリズムの知識を使用できません。長い間、誰もがこの声明の影響を受けているかもしれません。少し前に製品の需要に遭遇するまで、私は振り返って、そうではないことがわかりました。
フロントエンドのソート
フロントエンドのソートシナリオ
フロントエンドは、ソート条件をリクエストパラメーターとしてバックエンドに渡し、バックエンドはソート結果をフロントエンドへのリクエスト応答として返します。これは一般的なデザインです。しかし、それは一部の製品にはそれほど適していません。
シナリオを想像してみてください。フードアプリを使用するとき、並べ替え方法を切り替え、価格で並べ替えて、評価でソートすることがよくありますか。
実際の生産では、サーバーコストなどの要因により、単一のデータクエリが全体的なパフォーマンスボトルネックになる場合、フロントエンドでソートすることでパフォーマンスを最適化することも考慮されます。
ソートアルゴリズム
これを紹介する必要はないと感じています。コンピューターサイエンスの基本的なアルゴリズムとして、説明はWikipediaから直接コピーされます。
この段落は、最初の（男）と2番目の（SHU）を継承する目的で純粋にここに存在します。
JavaScriptソート
フロントエンドのソートについて話しているので、JavaScriptのネイティブインターフェイスArray.prototype.sortについて自然に考えます。
このインターフェイスはECMAScript 1st Edition以来存在しています。最新の仕様でその説明がどのように見えるか見てみましょう。
array.prototype.sort仕様
Array.prototype.sort(compareFn)
コードコピーは次のとおりです。
この配列の要素はソートされます。ソートは安定した必要ではありません（つまり、等しいと比較する要素は、必ずしも元の順序にとどまるとは限りません）。比較されていない場合、それは2つの引数xとyを受け入れ、x <yの場合、x = yの場合はゼロ、またはx> yの場合は陽性値を返す関数である必要があります。
明らかに、仕様は、 sortアルゴリズムが内部で実装したものを制限していません。インターフェイスの実装でさえ、安定したソートをする必要はありません。これは非常に重要であり、次に何度も関与します。
これに関連して、フロントエンドのソートは実際に各ブラウザの特定の実装に依存します。それでは、主流のブラウザはどのようにソートを実装しますか？次に、それぞれChrome 、 Firefox 、 Microsoft Edgeを簡単に比較します。
Chromeでの実装
ChromeのJavaScriptエンジンはV8です。オープンソースであるため、ソースコードを直接確認できます。
Array.js全体がJavaScript言語で実装されます。ソートメソッドの部分は、明らかに私が見たクイックソートよりもはるかに複雑ですが、明らかにコアアルゴリズムはまだクイックソートです。複雑なアルゴリズムの理由は、V8がパフォーマンスに関する考慮事項に多くの最適化を行ったためです。 （次にそれについて話します）
Firefoxでの実装
FirefoxのJavaScriptエンジンが使用しようとしているアレイソートアルゴリズムを決定することはできません。 [3]
既存の情報によると、Spidermoneyは内部的に並べ替えを実装しています。
Microsoft Edgeでの実装
Microsoft EdgeのJavaScriptエンジンチャクラのコードの中核部分は、2016年初頭にGitHubに供給されました。
ソースコードを見ると、Chakraの配列ソートアルゴリズムも迅速なソートを実装していることがわかります。また、V8と比較して、V8のパフォーマンスの最適化の痕跡はまったくありません。
JavaScriptアレイソートの問題
誰もが知っているように、クイックソートは不安定なソートアルゴリズムであり、マージソートは安定したソートアルゴリズムです。異なるエンジンのアルゴリズム選択の違いにより、フロントエンドはarray.prototype.sortインターフェイスによって実装されたJavaScriptコードに依存し、ブラウザで実行される実際のソート効果は一貫していません。
ソートの安定性の違いは、問題が発生する前に特定のシナリオによってトリガーする必要があります。多くの場合、不安定なソートは影響を与えません。
実際のプロジェクト開発における配列のソートに安定性が必要ない場合、実際にこれを見ることができ、ブラウザ間の実装の違いはそれほど重要ではありません。
しかし、プロジェクトでソートが安定している必要がある場合、これらの違いの存在は需要を満たしません。このために追加の作業を行う必要があります。
例えば：
特定の都市の自動車ライセンスオークションシステムの最終的な勝利規則は次のとおりです。
1。価格で逆に並べ替えます。
2。入札命令（つまり、価格提出時間）に応じて、同じ価格が積極的にソートされます。
並べ替えがフロントエンドで行われた場合、クイックソートを使用してブラウザに表示される勝者は、期待と矛盾する可能性があります。
違いを調べてください
解決策を見つける前に、問題の理由を調査する必要があります。
Chromeがクイックソートを使用する理由
実際、この状況は最初から存在していました。
Chrome Betaは2008年9月2日にリリースされました。しかし、リリース後まもなく、一部の開発者はChromium Development Groupに＃90のバグフィードバックを提出しました。 V8の配列ソート実装は安定していません。
このバグの問題の議論はたくさんあります。 2015年11月10日まで、開発者はV8でのアレイソートの実装について依然としてコメントしました。
同時に、問題が閉鎖されていることにも気付きました。ただし、ECMAScriptの次の仕様の議論のリファレンスとして、2013年6月に開発チームメンバーによって再開されました。
そして、es-discussの最後の結論はです
コードコピーは次のとおりです。
それは変わりません。 Stableは不安定なサブセットです。また、その逆も、すべての不安定なアルゴリズムがいくつかの入力に対して安定した結果を返します。マークのポイントは、「常に不安定」を要求することは、どんな言語を選んでも意味がないということです。
/アンドレアス
この記事で前述した最終的なECMAScript 2015の仕様で説明されているように。
時代の特徴
IMHO、この問題はChromeのリリースの開始時に報告されました。
上記のように、Chromeの最初のバージョンは2008年9月にリリースされました。StatCounterの統計によると、その期間中の最高の市場シェアを持つ2つのブラウザは、IE（当時のIE6とIE7のみ）とFirefoxであり、市場シェアはそれぞれ67.16％と25.77％に達しました。言い換えれば、2つのブラウザの合計市場シェアは90％を超えています。
別のブラウザソートアルゴリズム統計によると、90％以上の市場シェアを持つこれらの2つのブラウザは安定した配列ソートを採用しています。したがって、Chromeのリリースの開始時に開発者から質問されることは合理的です。
仕様に従ってください
バグの問題の議論から、エンジンの実装の迅速な並べ替えを使用する際に、開発チームメンバーのいくつかの考慮事項を大まかに理解できます。
これらの1つは、エンジンがECMAScript仕様に準拠している必要があると彼らが信じていることです。仕様では安定した選別の説明は必要ないため、V8の実装は仕様に完全に沿っていると考えています。
パフォーマンスに関する考慮事項
さらに、V8設計における重要な考慮事項はエンジンのパフォーマンスであると彼らは信じています。
クイックソートは、マージソートよりも全体的なパフォーマンスが向上します。
より高いコンピューティング効率。クイックソートは、実際のコンピューター実行環境では、同じ時間の複雑さを持つ他のソートアルゴリズムよりも速くなります（最悪の組み合わせに達していない場合）
低スペースコスト。前者はO（n）スペースの複雑さのみを持っていますが、後者のO（n）スペースの複雑さと比較して、ランタイム中のメモリ消費量は少なくなります。
配列ソートアルゴリズムのV8のパフォーマンス最適化
V8はエンジンのパフォーマンスに非常に興味があるため、配列のソートで何をしますか？
ソースコードを読むことで、私はまだいくつかの基本的な知識を学びました。
混合挿入ソート
クイックソートは、大きな配列を分割して征服し、大きな配列を分解し、レイヤーごとに下に戻すというアイデアです。ただし、再帰の深さが大きすぎる場合、再帰コールスタックのメモリリソース消費も非常に大きくなります。最適化が不十分な場合、スタックオーバーフローさえ引き起こす可能性があります。
V8の現在の実装は、しきい値を設定し、最低層の10以下の長さの小さな配列の挿入ソートを使用することです。
Wikipediaのコードコメントと説明によると、挿入ソートの平均時間の複雑さはO（n²）がQuick Sort O（NN）のそれよりも悪いです。ただし、実行中の環境では、小さな配列の挿入並べ替えを使用する効率は、高速ソートよりも効率的であるため、ここでは拡張されません。
V8コードの例
var QuickSort = function QuickSort（a、from、to）{...... while（true）{//挿入ソートは、短い配列の場合より速くなります。 if（to -<= 10）{insertionsort（a、from、to）;戻る; } ......} ......};3つの数字があります
知られているように、クイックソートアキレスヒールは、アルゴリズムが最悪のアレイの組み合わせで退化することです。
クイックソートアルゴリズムのコアは、ピボットを選択し、その後の再帰の参照に従って比較され、2つの数値領域に交換された配列を分解することです。既に順序付けられた配列の場合、参照要素が選択されるたびに最初または最後の要素が常に選択されている場合、毎回空の数の領域があり、再帰数のレイヤーがnに到達し、最終的にはアルゴリズムの時間の複雑さの分解につながります。したがって、ピボットの選択は非常に重要です。
V8はmedian-of-threeの最適化を使用します。最初と終わりの2つの要素に加えて、ベンチマーク要素の競合に参加するために別の要素が選択されます。
3番目の要素の選択戦略は大まかです。
配列の長さが1000以下の場合、ターゲット要素として半分の位置の要素を選択します。
アレイの長さが1000を超える場合、200〜215の距離で1つの要素（固定されていない、配列の長さで変更）を選択して、最初に候補要素のバッチを決定します。次に、このバッチの候補要素を並べ替え、結果の中央値をターゲット要素として使用します。
最後に、3つの要素の中央値をピボットとして取得します。
V8コードの例
var getthirdindex = function（a、from、to）{var t_array = new internalArray（）; //「from」と「to」の両方を使用して、ピボット候補を決定します。 var increment = 200 +（（to --from）＆15）; var j = 0; += 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 shuld_index = t_array [t_array.length >> 1] [0]; return shuld_index;}; var QuickSort = fucks QuickSort（a、from、）{...... while（true）{...... if（to -from> 1000）{third_index = getthirdindex（a、from、to）; } else {shuld_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]）; }} quicksort（左）.concat（[pivot]、quicksort（右））;};上記のコードの主な問題は、再帰サブアレイを保存するために左右に2つの数値領域を使用するため、O（n）の追加のストレージスペースが必要です。これは、理論的な平均空間的複雑度O（n）と比較して大きな違いです。
追加のスペースオーバーヘッドは、実際のランタイムの全体的な速度にも影響します。これは、同じレベルの時間の複雑さを超える実際のランタイムで迅速な並べ替えが実行できる理由の1つでもあります。したがって、一般的に言えば、より良いパフォーマンスを備えた高速ソートは、インプレースソートを採用します。
V8ソースコードの実装は、元の配列で要素を交換することです。
Firefoxがマージソートを使用する理由
その背後にも物語があります。
実際、Firefoxが最初にリリースされたとき、それは安定したソートアルゴリズムを使用してアレイソートを実装していませんでした。
Firefox（Firebird）の元のバージョンによって実装された配列ソートアルゴリズムは、ヒープソートであり、これも不安定なソートアルゴリズムでもあります。したがって、誰かが後にバグを提出しました。
Mozilla Developmentチームは、この問題について一連の議論を行いました。
ディスカッションプロセスから、いくつかのポイントを描くことができます
1。同じ期間のモジラの競合他社はIE6でした。上記の統計から、IE6がソートで安定していることがわかります。
2. JavaScriptの父であるBrendan Eichは、安定性は良いと考えています
3. Firefoxは、ヒープソートの前にクイックソートを使用します
開発グループメンバーが安定したソートアルゴリズムを実装する傾向があるという主な前提に基づいて、Firefox3はアレイソートの新しい実装としてマージソートを取ります。
ソートの安定性の違いを解決します
私は主に各ブラウザのソートの実装の違いを伝え、これらの違いが存在するより表面的な理由のいくつかを説明するために、それほど上記のことを言ってきました。
しかし、これを読んだ後、読者はまだ質問があるかもしれません：私のプロジェクトが安定した選別に頼る必要がある場合はどうすればよいですか？
解決
実際、この問題を解決するという考えは比較的簡単です。
ブラウザは、さまざまな考慮事項のために異なるソートアルゴリズムを選択します。極端なパフォーマンスを追求する傾向がある人もいれば、優れた開発体験を提供する傾向がある人もいますが、従うべきルールがあります。
現在の既知の状況から判断すると、すべての主流のブラウザ（IE6、7、8を含む）は基本的に配列ソートアルゴリズムの実装を列挙できます。
1.マージソート/ティムソート
2。クイックソート
それで、クイックソートを安定したソートに変換することができますか？
一般的に言えば、オブジェクト配列に不安定なソートを使用すると、結果に影響します。他のタイプの配列自体は、安定したまたは不安定なソート結果を使用しますが、等しいです。したがって、計画はほぼ次のとおりです。
オブジェクトの他の属性と競合しないように、ソートする配列を事前に処理し、ソートする各オブジェクトに自然な順序属性を追加します。
カスタムソート比較メソッドCompareFNは、前の判決が等しい場合、常に2番目の判断の次元として自然な順序を使用します。
マージソートなどの実装に直面する場合、アルゴリズム自体が安定しているため、追加の自然順序の比較はソート結果を変更しないため、スキームの互換性が向上します。
ただし、ソートする配列を変更することが含まれ、自然な順序プロパティを保存するには追加のスペースが必要です。 V8のようなエンジンは、同様の方法を使用すべきではないと考えられます。ただし、開発者によってカスタマイズされた選別計画として実行可能です。
スキームコードの例
'Strict'; const index = symbol（ 'index'）; function getComparer（Compare）{return function（左、右）{let result = compare（左、右）; return result === 0？左[index] - 右[index]：result; };} function sort（array、compare）{array = array.map（（item、index）=> {if（typeof item === 'object'）{item [index] = index;} return item;}）; return array.sort（getComparer（比較））;}上記は、安定したソートを満たす単純なアルゴリズムの変更例です。
簡単な理由は、実際の生産環境での配列入力としてのデータ構造が複雑であり、実際の状況に基づいてより多くのタイプの事前注文が必要かどうかを判断する必要があるためです。
タグ
1.フロントエンドは、比較的広い概念になりました。この記事のフロントエンドは、主にブラウザをキャリアとして、JavaScriptをプログラミング言語として使用する環境を指します。
2。この記事では、アルゴリズム全体を含めるつもりはありません。一般的なソートアルゴリズムをエントリポイントとして使用したいと思います。
3. Firefoxアレイのソートによって実装されたアルゴリズムを確認すると、Spidermoneyでソート関連のバグが見つかりました。一般的に言えば、議論の中で、誰かが極端なケースでより良いパフォーマンスでTIMSORTアルゴリズムを使用することを提案してマージのソートを置き換えましたが、Mozillaのエンジニアは、TIMSORTアルゴリズムのライセンス認証問題のために、Mozillaのソフトウェアでアルゴリズムを直接使用し、相手の党の後続の返信を待つ方法はないと述べました。
要約します
上記は、フロントエンドのソートで発生した問題の要約と解決策です。近年、ますます多くのプロジェクトが豊富なクライアントアプリケーションに変化しており、プロジェクトのフロントエンドの割合が増加しています。将来のブラウザコンピューティングパワーがさらに改善されると、より複雑な計算が可能になります。責任の変更により、フロントエンドフォームにはいくつかの大きな変化が生じる可能性があります。世界を歩くとき、あなたは常にスキルを持っている必要があります。