クラス版 DOM Iterator の利用例と解説

JavaScript

id:reinyannyan:20060411:p1 の後半で、DOM 要素コレクションを prototype.js 的にイテレーション可能にするクラス "Domi" (仮称) を実装しました。

実装の動機については id:reinyannyan:20060404:p2 に述べたんですが、ここで改めてまとめておきましょう:

Prototype 的アプローチでは、"$A(collection).each(...)" のように、$A 関数でコレクションを配列化した上でイテレーションを行うのですが、

  • DOM コレクションと同じサイズの配列を作成・(一時的に) 保持する
  • 配列作成の際に、いったん全要素のイテレーションが行われる

という「重さ」を伴うわけなんですね。そして、DOM 要素を配列として保持したいのではなく、each でイテレーションを行いたいだけという場合、その重さは残念ながら全く無駄なものになってしまいます。

この問題に対する解決案が "Domi" ということでした。ここではそのクラス版の具体的な利用例を見ていきます。Prototype の配列イテレータを意識しながら見ていただければと思います。

例題: XML ドキュメントから JPEG 画像へのリンク要素を抜き出す

ドキュメントの仕様が分かっていないものとして、全ての item 要素を得るところから始めましょう:

var items = $D(xmldoc.selectNodes('//item/*'));

$A (配列化) の代わりに $D という関数を提供しており、その戻り値が Prototype の配列オブジェクトと全く同じ感覚で扱える、というのがここでのポイントになります。

続き:

var jpegs = items.select(function (node) {
  return node.text.match(/^http\S+\.jpg$/);
});

上において、"items" は Domi クラスのインスタンスですが、"jpegs" はその別名 (同一のインスタンスへの参照) となります。要は一行で書けることなんですが、$D 関数の、「Domi インスタンスの作成者」としての役割を明確にするために分けてみました*1。

"select" メソッドは、配列化を伴わずに要素を抽出する機能で、このクラスの最大の目玉です。

select の解説

一般的なイテレータと同様に、引数として関数 (ここでは iteratee と呼ぶことにします) を渡します。これが、DOM コレクションから要素を抽出する条件となります。

ここで理解していただきたいのは、select が行うのは検索条件をイテレータに与えることだけ、ということです。つまり、この select は Enumerable のそれとは違い、イテレータではないのです。したがって、この時点ではまだループは全く回っていません。

また、select はインスタンス自身を返しますので、これを利用して

  • select(...).each(...) のように、直接他のイテレータを連結
  • select のさらなる連結による多重絞込み
  • 複雑な抽出作業を抽出専門家オブジェクトに任せる

といったことが可能になります。

さらに、select を何重に適用したとしてもイテレータ (内部の for ループ) は一周、即ち要素の個数分しか回らない、ということも指摘しておきたいと思います。

閑話休題

では、例の続きです:

jpegs.each(function (node) {
  document.body.appendChild(document.createElement('IMG')).src = node.text;
});

Enumerable#each と同様なんですが、抽出条件の適用により、全ての「JPEG 画像の URI を保持する要素」が "node" として回ってくることになります。

そして、ブラウザ上には沢山の JPEG 画像が表示されることでしょう。

以上で例は終わりです。

ベンチマーク

$D の方が $A よりもイテレーションが一回少ない分、単純に考えて倍の速度が出ると考えられるのですが、いちおう確認のためにベンチマークを取ってみましょう。

HTML ドキュメント中に 100 個のアンカー要素を用意して、以下のテストを行いました:

function test1(handler) {
  var links = handler(document.getElementsByTagName('a'));
}
// 20.74074074074074

function test2(handler) {
  var links = handler(document.getElementsByTagName('a'));
  links.each(function () {});
}
// 2.664451827242525

function test3(handler) {
  var links = handler(document.getElementsByTagName('a'));
  links = links.select(function (n) {
    return n.href.match(/\.jp/);
  });
  links.each(function () {});
}
// 1.6217712177121772

function test4(handler) {
  var links = handler(document.getElementsByTagName('a'));
  links = links.select(function (n) {
    return n.href.match(/\.jp/);
  });
  links.inject([], function (arr, n) {
    arr.push(n.href);
    return arr;
  });
}
// 1.4775036284470244

function test5(handler) {
  var links = handler(document.getElementsByTagName('*'));
  links = links.select(function (n) {
    return n.tagName == 'A';
  });
  links = links.select(function (n) {
    return n.href.match(/\.jp/);
  });
  links.inject([], function (arr, n) {
    arr.push(n.href);
    return arr;
  });
}
// 1.6400885935769655

コメントの数値は、各テストの $A での実行時間を $D での実行時間で除算したものです。それぞれ 50 回の試行の平均時間を取っています。この数値が大きければ大きいほど速度差が大きいことになります。

each でイテレーションを行っただけの test2 の結果を見ると、$D の方がなぜか倍よりも速くなっていることが分かります。そして、test1 から test4 までを見ると、複雑になればなるほど差は縮まる傾向に見えるんですが、test4 よりも複雑な test5 ではまた差が大きくなっています。

実際的に見て、each だけを利用する単純なケースであれば、倍程度以上の高速化を期待して良いのではないかと考えられます。

おわりに

クラス化によって、当初の Domi よりもはるかに柔軟で、より Prototype 的なコレクション操作が可能になりました。

また、配列化を伴う手法に対する速度面での利点も明確にできました。メモリー効率上の利点については計測の手段を持たないので示せませんでしたが、要素数が大きければ大きいほど有利になることは明らかでしょう。


最後に、Domi の拡張例として (抽出条件を適用された) コレクションの要素数を得るメソッドを提示しておきます:

Domi.prototype.size = function () {
  return this.inject(null, function (_,_, idx) { return idx+1 });
};

*1:$A を使用した場合、items と jpegs は別個の配列オブジェクトになります