O(n)の処理をちょっとでも高速化したい。 プログラムがいろいろあれば、そのアプローチもいろいろなはず。 とはいえ、高速化といえば、その基本に次の3点があるそうです。
- 処理する数 n をできる限り減らす。
- 処理する数 n が減らせないなら、 1回あたりの処理を軽くする
- 別のアルゴリズムを使って O(n) より小さな傾きの処理に変える
ここでは、2番目の「1回あたりの処理を軽くする」に焦点を当てた高速化について 思いつく限り列挙していこうかと。 …というか、高速化について書かれたサイトの多くは、この点について述べていることが多いと思うけど。。
小手先テクニック
- オブジェクトアクセスを減らす
- DOMの追加削除は最低限にする
- innerHTML より appendChild(document.createTextNode('hoge')) にする
- for 文は逆順でまわす
- if 文は可能性の高い順に並べる or ネストさせる or switch にする
オブジェクトアクセスを減らす
入れ子になったオブジェクトの探索にはコストがかかるので、 利用頻度が高いものはローカル変数に移すことで高速化が見込める。
次に示すものは、DOM要素に対するアクセス削減。
1 2 3 4 5 | var element = document.getElementById( 'someElement' ); var style = element.style; style.position = 'absolute' ; style.top = '10px' ; style.left = '100px' ; |
1 2 3 4 | var element = document.getElementById( 'someElement' ); element.style.position = 'absolute' ; element.style.top = '10px' ; element.style.left = '100px' ; |
次に示すものは、for文中に隠れているアクセスの削減。 具体的には Array の length プロパティへのアクセス、配列要素へのアクセスを減らしてる。 この例だと数が少なすぎて効果は期待できない… ちなみにfor文は使わなくて済むなら使わない方が良い(for文を始めるためのオーバーヘッドがなくなるため)。
1 2 3 4 5 6 7 | var i, length; var nodeList = document.getElementsByTagName( 'input' ), nodeItem; for (i = 0, length = nodeList.length; i < length; i++) { nodeItem = nodeList[i]; nodeItem.style.display = 'none' ; nodeItem.appendChild(document.createTextNode(i)); } |
1 2 3 4 5 6 | var i; var nodeList = document.getElementsByTagName( 'input' ); for (i = 0; i < nodeList.length; i++) { nodeList[i].style.display = 'none' ; nodeList[i].appendChild(document.createTextNode(i)); } |
DOMの追加削除は最低限にする
現在表示されているDOM要素へ作成したDOM要素を追加すると、 ブラウザの再描画が走る(可能性が高い)ので、 できる限り表示されているDOM要素への追加はまとめて行うようにする。
1 2 3 4 5 6 7 8 9 10 | var container = document.getElementById( 'someElement' ); var fragment = document.createDocumentFragment(); var contents = [ 'item1' , 'item2' , 'item3' , 'item4' ]; var i, length, item; for (i = 0, length = contents.length; i < length; i++) { item = document.createElement( 'div' ); item.appendChild(document.createTextNode(contents[i])); fragment.appendChild(item); } container.appendChild(fragment); |
1 2 3 4 5 6 7 8 | var container = document.getElementById( 'someElement' ); var contents = [ 'item1' , 'item2' , 'item3' , 'item4' ]; var i, length, item; for (i = 0, length = contents.length; i < length; i++) { item = document.createElement( 'div' ); item.innerHTML = contents[i]; container .appendChild(item); } |
innerHTML より appendChild( document.createTextNode( 'hoge' ) ) にする
純粋にテキストを追加するだけであれば、innerHTML より appendChild(document.createTextNode('hoge')) を利用した方が良い。 まぁ、innerHTML は HTML 構文解析が含まれるから仕方ないのだけれど…
1 | element.appendChild(document.createTextNode( 'サンプルテキスト.' )); |
1 | element.innerHTML = 'サンプルテキスト.' ; |
for 文は逆順でまわす
カウントアップ処理がなくなる分、速くなる。 順序が関係ない場合は後ろから回すに限る。 こればかりは積み重ねが大切なので、プロジェクトの初期から取り組んでいないと厳しくなるかも…
1 2 3 | for ( var i = itemList.length; i--;) { // 何か処理する。 } |
1 2 3 | for ( var i = 0, length = itemList.length; i < length; i++) { // 何か処理する。 } |
if 文は可能性の高い順に並べる or ネストさせる or switch にする
確率が高い順にif 文を並べるのは理解できるとして…確率が同じ場合の例を以下で載せます。 例えば、0-5の乱数を振り分けるプログラムは以下のような感じ。 当確率なら switch を使うのが鉄則。 if文をネストさせることで判定回数を分散させるのも手法の1つ。 ただ、 if 文のネストは読みづらくなるので個人的には…。。 そしてよくある if - else の連続。 まぁ、良くも悪くもたまに見かける… 最悪な例もたまに見かけるけど、if-else と違って判定が終わっていても再判定が走るのでコードとして論外。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | var value = Math.floor(Math.random() * 6); // 0-5の乱数 switch (value) { case 0: // 0の場合 break ; case 1: // 1の場合 break ; case 2: // 2の場合 break ; case 3: // 3の場合 break ; case 4: // 4の場合 break ; case 5: // 5の場合 break ; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | var value = Math.floor(Math.random() * 6); // 0-5の乱数 if (value < 3) { if (0 === value) { // 0の場合 } if (1 === value) { // 1の場合 } else { // 2の場合 } } else { if (3 === value) { // 3の場合 } else if (4=== value) { // 4の場合 } else { // 5の場合 } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | var value = Math.floor(Math.random() * 6); // 0-5の乱数 if (0 === value) { // 0の場合 } else if (1 === value) { // 1の場合 } else if (2 === value) { // 2の場合 } else if (3 === value) { // 3の場合 } else if (4 === value) { // 4の場合 } else { // 5の場合 } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | var value = Math.floor(Math.random() * 6); // 0-5の乱数 if (0 === value) { // 0の場合 } if (1 === value) { // 1の場合 } if (2 === value) { // 2の場合 } if (3 === value) { // 3の場合 } if (4 === value) { // 4の場合 } if (5 === value) { // 5の場合 } |
と、いろいろ書いてはみたけれど…この手の効果はミリ秒以下の世界なので実質ほとんど効果無し。。。 やっぱり O(n) の n を減らすことが一番効果的と思う…
例えば…不要な処理は行わない。後回しにできることは後回しにする。画面だけは反映しとく。…といったこと。具体的には次のようなことかなぁ
- DOM生成に関しては、画面上で見えてる範囲、見えてる情報のみ描画して、後は必要になったとき処理する。
- Ajax通信に関しては、画面上は先に反映してしまって、結果はあとから通知する。
こういったことって設計段階で考慮していないと、後から修正は厳しいから難しい。。
最後に… このブログに興味を持っていただけた方は、 ぜひ 「Facebookページ に いいね!」または 「Twitter の フォロー」 お願いします!!