この記事はJavaScript Advent Calendar 2016 - Qiitaのの18日目の投稿です。
私は業務やプライベートで、node.jsを使って開発をしています。
勉強のために、時間のあるときにv8のソースコードを読んでいて内部の実装について調べています。
先日、配列のソート周りの仕組みが面白いと感じたので今回紹介します。
V8とは
developers.google.com chromeやnode.jsで使われているjavascriptエンジンのことです。
Array.sort
v8におけるjavascriptのArray.sortのソースは https://github.com/v8/v8/blob/master/src/js/array.jsでみれます。
Array.sortの関数自体は https://github.com/v8/v8/blob/master/src/js/array.js#L1559から読み進めていくことができます。
Array.innerSortの実装について
Array.sort内や様々なところで呼び出されているinnerSort関数の実装はやや複雑ですが、sortのパフォーマンスを上げるためにかなり工夫がされています。
挿入ソートとクイックソートを組み合わせるソート戦略
Array.innerSortでは、ソートする配列の要素数に応じて、挿入ソートとクイックソートを使い分けています。
コメント上で要素数が22以下の場合挿入ソートにしたほうが効率が良いと書かれていて、実際に要素数が10以下の場合は挿入ソートをつかっています。
https://github.com/v8/v8/blob/master/src/js/array.js#L763-L767
このソート戦略については、javascript関係なく一般的に有効な戦略で、下記の「参考」項目にリンクをまとめています。
挿入ソートについて
https://github.com/v8/v8/blob/master/src/js/array.js#L726-L740
挿入ソートは平均計算量で、要素数の2乗で計算量が増えていきますが。
いわゆるin-place*1なアルゴリズムで、ソート中に元の配列を書き換えながらソートを行うので、ソート中に用いるメモリ量
を増やさずにソートすることができます。
(追記) 挿入ソートについて kakts-tec.hatenablog.com
クイックソートについて
https://github.com/v8/v8/blob/master/src/js/array.js#L760-L844
クイックソートは平均計算量で、計算量的には挿入ソートより優秀ですが、ソート中に関数の再帰をおこなうため、オーバーヘッドが非常に多く、要素数が少ない場合、そのオーバーヘッドが無視できないため挿入ソートが勝る場合があります。
流石に膨大な要素数に対するソートとなると、の計算量は強力で、挿入ソートと比較して圧倒的に性能があがります。
むしろ万以上の単位になると挿入ソートは全く使えないほどパフォーマンスが落ちます。
まとめ
v8の配列ソートにおいて、要素数に応じて挿入ソート()とクイックソート(
)という2つのアルゴリズムを切り替えていることを紹介しました。
アルゴリズムに関してこの記事では深くは紹介しませんが、v8においては配列ソートにおいてメモリ使用量と速度を考慮した実装が行われていることを確認できました。
次回の JavaScript Advent Calendar 2016 - Qiitaは wtnk - Qiitaさんの投稿になります。
参考
挿入ソートとクイックソートについて
- algorithms - Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent? - Computer Science Stack Exchange
- algorithm - Why is Insertion sort better than Quick sort for small list of elements? - Stack Overflow
- [http://www.techscore.com/blog/2014/12/06/comparison-of-sorting-algorithm/:embed:cite]
