ノードの集合を「ドキュメント順」に高速に並べ替える。その１

ドキュメント順とは何か？

ドキュメント順とは、簡単に言えば「XML のソース上の前にある順」のこと。
詳しくはこのへんを見てね。

XPath ではこの「ドキュメント順」という概念がよく登場する。

たとえば、ノードを文字列化するときは子孫テキストノードを「ドキュメント順」に文字列として連結しなければならない。とかとか

でも、このドキュメント順へのソート

考えただけでもめちゃめちゃ重そうだ・・・。

いろいろ考えてみた。

XPath 実行中はドキュメント順が変わることがないので、DOM アクセスはキャッシュできる。
ノードの集合は木構造で保存したほうが比較回数が少なくてすむ（アルゴリズム初心者なので、実際に早いか検証しないと＞＜）

で、今回は DOM アクセスをキャッシュしながらノードを比較する関数を作る

汎用的に作ったので XPath 目的以外でも使えます。

var order = function(node1, node2) {
    var wrapper1 = new order.wrapper(node1);
    var wrapper2 = new order.wrapper(node2);
    if (wrapper1 == wrapper2) return 0;
    var ancestors1 = [wrapper1];
    while (wrapper1 = wrapper1.parent()) {
        if (wrapper1 == wrapper2) return 1;
        ancestors1.push(wrapper1);
    }
    var prev2;
    while (wrapper2 = (prev2 = wrapper2).parent()) {
        for (var i = 0; i < ancestors1.length; i ++) {
            if (wrapper1 == ancestors1[i]) {
                wrapper2 = ancestors1[i - 1];
                if (!prev2) return -1;
                wrapper1 = prev2;

                while(wrapper1 = wrapper1.next())
                    if (wrapper1 == wrapper2) return -1
                return 1
            }
        }
    }
    return -1;
};

order.id = 0;

order.wrapper = function(node) {
    var wrapper = node.__order__;
    if (wrapper && wrapper._id === order.id) return wrapper;
    this._id = order.id;
    this._node = node; 
    node.__order__ = this; 
};

order.wrapper.prototype = {
    next: function() {
        var next = ('_next' in this) ? this._next : (this._next = this._node.nextSibling);
        return next ? new order.wrapper(next) : null;
    },
    parent: function() {
        var parent = ('_parent' in this) ? this._parent : (this._parent = this._node.parentNode);
        return parent ? new order.wrapper(parent) : null;
    }
};

使い方

以下のような HTML で

<div id="id1">
  <div id="id2">
    <div id="id3"></div>
  </div>
  <div id="id4"></div>
</div>

以下のようになる。

var $ = function(id) { return document.getElementById(id) };

alert(order($('id1'), $('id2'))); // -1
alert(order($('id3'), $('id3'))); // 0
alert(order($('id4'), $('id1'))); // 1

たとえば、配列相手なら

[$('id4'), $('id2'), $('id1'), $('id3'), $('id2')].sort(order); // order 関数を sort 関数に引数で渡してやる

こうすると以下のように「ドキュメント順」に並び変わる。

この時、DOM プロパティアクセスのキャッシュによって parentNode と nextSibling へのアクセスは各要素一回ずつしか行われない。その他の DOM プロパティアクセスはない。
ドキュメントを変更した場合は以下のようにすると、キャッシュを破棄できる。

order.id++; // id を変える

たとえば、

XPath の評価中はデータをキャッシュして、終わったら id をインクリメントしてやればいいことになる。

よし、次は

ノードの集合をリストで持つのと木構造で持つのとパフォーマンスがどのくらい変わるかを実験したい＞＜

IT戦記

プログラミング、起業などについて書いているプログラマーのブログです😚