Qiitaのの18日目の投稿です。私は業務やプライベートで、node.jsを使って開発をしています。勉強のために、時間のあるときにv8のソースコードを読んでいて内部の実装について調べています。先日、配列のソート周りの仕組みが面白いと感じたので今回紹介します。chromeやnode.jsで使われているjavascriptエンジンのことです。https://github.com/v8/v8/blob/master/src/js/array.jsでみれます。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関係なく一般的に有効な戦略で、下記の「参考」項目にリンクをまとめています。要素数の2乗で計算量が増えていきますが。増やさずにソートすることができます。計算量的には挿入ソートより優秀ですが、ソート中に関数の再帰をおこなうため、オーバーヘッドが非常に多く、要素数が少ない場合、そのオーバーヘッドが無視できないため挿入ソートが勝る場合があります。計算量は強力で、挿入ソートと比較して圧倒的に性能があがります。万以上の単位になると挿入ソートは全く使えないほどパフォーマンスが落ちます。)という2つのアルゴリズムを切り替えていることを紹介しました。アルゴリズムに関してこの記事では深くは紹介しませんが、v8においては配列ソートにおいてメモリ使用量と速度を考慮した実装が行われていることを確認できました。Qiitaさんの投稿になります。config.'月別アーカイブ参加グループプログラミングテクノロジーはてなブログをはじめよう!kaktsさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。