2007/09/24

DOM検索効率化をもう少し追ってみる。

やったよ。やった。ようやくキーボードが届いたよ。ここ3ヶ月、私のキーボードはC-xと]}のキーが壊れていたのだけど、ようやく快適に打てるようになったよ。私の状態を見兼ねて買ってくれた学生時代の恩師の稲葉先生どうもありがとうございます。つーか、そのくらい自分で買えばいいのだけど、なんか買う気がなかなか起こらなくて、ダラダラしてました。。。

で、さっそく簡単なプログラムを書きはじめている。えと、実はまだDOM検索周りを調べているのだけど、一つ疑問があがってきた。それは以下の通り。

childNodesでの検索とfirstChildとnextSiblingの検索について。つまり、どちらでも子ノードを取得することができるのだけど、実際どっちを使ったらいいの？

ググってみるとパフォーマンスを見ている人がいたのだが、childNodesよりも、fistChildを取ってnextSiblingで検索する方が速いということらしい。特に、IE6が良くないとのこと。ブラウザの実装によるのね。。。
new Blah().list(); node.childNodes[] performance
うーむ。てっきりnextSiblingって、いかにもリンクリストな感じでその要素の数を線形探索しないといけないから、O(log(n))で、childNodesでindex指定で取得したら、O(1)で速いんだろうなぁ、なんて思っていたのだけど、どうやらそうでないみたい。。。と鵜呑みにするのもどうか、と思うのだが、まぁ、いいや。

ええと、何でこんなことを調べているかと言うと、私はchildNodesからelementNodeだけの配列を取得するようなメソッドが欲しかったので、作ろうと思っていたのだ。そして、その際に、firstChildからnextSiblingでグルングルン回すか、childNodes分こっちもグルングルン回するかどっちにしようかな、と思っていたのだ。そこで自分でベンチマークを取ってみたよ。まぁ、結局、全てを線形探索するのだから、どっちでもいいような気がするけども。。。で、ベンチマークツールはamachang氏のbenchmark.jsを使用した。

ソースはこんな感じ。ここにサンプルも置いておくよ。childNodes && firstChild + nextSibling Benchmark

  1. <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
  2. <html lang="ja">
  4.     <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  5.     </meta><meta http-equiv="Content-Style-Type" content="text/css">
  6.     </meta><meta http-equiv="Content-Script-Type" content="text/javascript">
  7.     <script language="JavaScript" type="text/javascript" src="js/prototype.js"></script>
  8.     <script language="JavaScript" type="text/javascript" src="js/scriptaculous.js"></script>
  9.     <script language="JavaScript" type="text/javascript" src="benchmark.js"></script>
  10.     <script language="JavaScript" type="text/javascript">
  11.       Element.addMethods({
  12.         _childElementsByFirstChildNextSibling: function(element) {
  13.           var children = [];
  14.           var child = element.firstChild;
  15.           while (child) {
  16.             if (child.nodeType == 1) {
  17.               children.push(child);
  18.             }
  19.             var child = child.nextSibling;
  20.           }
  21.           return children;
  22.         },
  23.         _childElementsByChildNodes: function(element) {
  24.           var children = [];
  25.           var nodes = element.childNodes;
  26.           var child = null;
  27.           for (var i = 0, l = nodes.length; i <l; i++) {
  28.             child = nodes.item(i);
  29.             if (child.nodeType == 1) {
  30.               children.push(child);
  31.             }
  32.           }
  33.           return children;
  34.         },
  35.         _childElementByChildNodes: function(element, index) {
  36.           var nodeIndex = 0;
  37.           var nodes = element.childNodes;
  38.           var child = null;
  39.           for (var i = 0, j = 0, l = nodes.length; i <l; i++) {
  40.             child = nodes.item(i);
  41.             if (child.nodeType == 1 && index == j++) {
  42.                return child;
  43.             }
  44.           }
  45.           return null;
  46.         },
  47.         _childElementByFirstChildNextSibling: function(element, index) {
  48.           var nodeIndex = 0;
  49.           var child = element.firstChild;
  50.           while (child) {
  51.             if (child.nodeType == 1 && index == nodeIndex++) {
  52.               return child;
  53.             }
  54.             child = child.nextSibling;
  55.           }
  56.           return null;
  57.         }
  58.       });
  59.     benchmark({
  60.         'initialize': function() {
  61.           for (i = 0; i <5000; i++) {
  62.             $('main').appendChild(Builder.node('div', 'item:' + i));
  63.           }
  64.         },
  65.         'firstChild + nextSibling childElements': function() {
  66.           $A($('main')._childElementsByFirstChildNextSibling()).each(function(e) {
  67.             e.style.margin = '0.5em';
  68.           });
  69.         },
  70.         'childNodes childElements': function() {
  71.           $A($('main')._childElementsByChildNodes()).each(function(e) {
  72.             e.style.margin = '0.5em';
  73.           });
  74.         },
  75.         'firstChild + nextSibling childElement': function() {
  76.            var ce = $('main')._childElementByFirstChildNextSibling(50);
  77.            ce.style.backgroundColor = '#ddd';
  78.         },
  79.         'childNodes childElement': function() {
  80.            var ce = $('main')._childElementByChildNodes(50);
  81.            ce.style.backgroundColor = '#ddd';
  82.         },
  83.         'prototype.js down + next': function() {
  84.           var ce = $($('main').down()).next(49);
  85.            ce.style.backgroundColor = '#ddd';
  86.         }
  87.    });
  88.     </script>
  89.     <title>childNodes && firstChild + nextSibling Benchmark + next</title>
  90.   </script></meta></head>
  91.   <body>
  92.     <h1 style="text-align:center;">childNodes && firstChild + nextSibling Benchmark</h1>
  93.     <div id="main"></div>
  94.   </body>
  95. </html>

firefox2.0.0.7の私の環境での結果は。。。

preparing ...
let's go!
.
*** initialize ***
result : 2763.966739[ms]
.
*** firstChild + nextSibling childElements ***
result : 680.966739[ms]
.
*** childNodes childElements ***
result : 400.966739[ms]
.
*** firstChild + nextSibling childElement ***
result : 48.991075[ms]
.
*** childNodes childElement ***
result : 51.991075[ms]
.
*** prototype.js down + next ***
result : 440.966739[ms]
.
finish!

childNodesの方が速い。まぁ、あんまり変わらないけど、予想と違うぞ？つーか、downとnextの組み合わせ遅すぎ。
ついでにIE6でも見てみる。

preparing ...
let's go!
.
*** initialize ***
result : 67827.967579[ms]
.
*** firstChild + nextSibling childElements ***
result : 1151.967579[ms]
.
*** childNodes childElements ***
result : 14900.967579[ms]
.
*** firstChild + nextSibling childElement ***
result : 59.089179[ms]
.
*** childNodes childElement ***
result : 3354.967579[ms]
.
*** prototype.js down + next ***
result : 22592.967579[ms]
.
finish!

うーん。洒落になってねぇ。ブラウザが死んだかと思たよ。。。childNodes重いっす。。。まぁ、線形探索っぽくchildNodesのitemを見て回っているので、遅くなることはしょうがないのだけど、なんとかならんかな。。。textNodeをすっ飛ばさなくてもいいのだったら、childNodesでindex指定で一発で取れて速そうだけど、今回の目的のelementNodeだけが欲しいならダメだね。こりゃ。

というわけで、firefoxでは、少しだけchildNodesの方が速かったのだけど、IE6のためにfirstChildとnextSiblingを採用するということになりました。。。つーか、downとnextはさらに使いものにならん。。。

prototype.jsのcleanWhitespaceなんかを見てみると、firstChildからnextSiblingを取っているのは理由があったのね。

Leave a comment

Bloglines feedburner