JavaScriptでDOMをDFSする4つの書き方

はじめに

DOM(Document Object Model)のDFS（深さ優先探索）をする場合、再帰関数を使う普通の書き方をしています。

再帰関数を使わないでDOMのDFSを書けることは有名ですが、DOMが子要素や兄弟要素へのリンクを持つ特性を利用することによって、配列も再帰関数も使わないで書けます。

コメントで知った方法と合わせて4つの書き方があることを紹介します。

それぞれの時間を計測したら意外な結果になりました。

4通りの書き方

4つのJavaScriptプログラムは一文字命名規則を使っています。

dfs_1

普通は再帰関数で書きます。

var dfs_1 = (e_base) => {
	var e_children = e_base.children;
	for (let index = 0; index < e_children.length; index++) {
		const e_child = e_children[index];
		dfs_1(e_child);
	}
};

dfs_2

配列に状態を保存することによって再帰関数を使わないで書けます。

var dfs_2 = (e_root) => {
	var e_focus;
	var d_dfs = [e_root];

	while (d_dfs.length) {
		e_focus = d_dfs.shift();

		if (e_focus.children.length) {
			d_dfs.unshift(...e_focus.children);
		}
	}
};

dfs_3

DOMが子要素(firstElementChild)や兄弟要素(nextElementSibling)へのリンクを持つ特性を利用することによって実は配列も再帰も使わないで書けます。

どのように書けば良いでしょうか？

頭の体操です。正解を折りたたみで隠しますので少し考えてみてください。

再帰も配列も使わない書き方

var dfs_3 = (e_root) => {
	var e_focus = e_root;

	outer: while (true) {

        if (e_focus.firstElementChild) {
			e_focus = e_focus.firstElementChild;
			continue;
		}

		while (true) {
			if (e_focus == e_root) {
				break outer;
			} else if (e_focus.nextElementSibling) {
				e_focus = e_focus.nextElementSibling;
				continue outer;
			} else {
				e_focus = e_focus.parentElement;
			}
		}
	}
};

dfs_4

Web API のcreateTreeWalkerでも書けます。

MDN Web Docs には DFS という説明がありませんが DFS のようです。

var dfs_4 = (e_root) => {
	var t_root = document.createTreeWalker(e_root, NodeFilter.SHOW_ELEMENT);
	var e_focus = t_root.currentNode;

	while (e_focus) {
		e_focus = t_root.nextNode();
	}
};

時間計測

時間を計測してみました。

dfs	時間(msec)
dfs_1	23.7
dfs_2	91.0
dfs_2b	79.7
dfs_3	12.8
dfs_4	5.7

メソッド push/pop は処理が速く、shift/unshift は遅いです。

現代の JavaScript チュートリアルの配列

というのを見つけて shift/unshif を push/pop に変えたプログラムがdfs_2bです。

さいごに

dfs_1 > dfs_2 > dfs_3 と予想していたので意外な結果になりました。

JavaScriptで配列を使うくらいなら再帰関数のままで良い、と言えそうです。

shift/unshift を push/pop に変えても少しだけ速くなりましたが、そもそも配列を使うことが遅くする、と言えそうです。

dfs_4 はシンプルで可読性が高く最速です。Web API が存在するなら Web API を使いましょう。