全置換はどうしたらはやい？

JavaScript

JSである単語を全置換するときにどうしたらはやいのかというベンチマークネタ。例えば、"Hello World!! Hello Worold!! Hello World!!..."で"Hello"を"Foo"に変換したいものとする。その際に正規表現を用いて全置換を行った場合と単純にString#repalceを繰り返したほうがはやいのかという検証。

検証コード

function regexpReplace(num)
{
	var Str = Array(num + 1).join("Hello World!!");
	var timestamp = new Date().getTime();
	Str = Str.replace(RegExp("Hello","g"), "Foo");
	return new Date().getTime() - timestamp;
};

function normalReplace(num)
{
	var Str = Array(num + 1).join("Hello World!!");
	var timestamp = new Date().getTime();
	for(var i=0;i<=num;i++){
		Str = Str.replace("Hello", "Foo");
	};
	return new Date().getTime() - timestamp;
};

alert(regexpReplace(1000));
alert(normalReplace(1000));

NUM += 4;

rTotal = 0;
nTotal = 0;

for(i=0;i<1000;i++)
{
    rTotal += regexpReplace(NUM);
    nTotal += normalReplace(NUM);
}

alert(rTotal);
alert(nTotal);

実験したところ。

  • 置換対象文字列が十分に長く、かつ、置換する数が十分に多い場合は、正規表現を利用したほうが早かった。regexpReplace -> 6ms, normalReplace -> 500ms
  • 上記NUMの値を、1..2..3..4..5と増やした場合、1〜4の範囲まではnoramalReplaceのほうがはやかったが、NUMが5を超えたところregexpReplaceのほうがはやくなった。

場合分けが足りないのであとで追記。