Edited at

最速のreplaceAll()を求めて

More than 1 year has passed since last update.

Javascriptでは文字を全置換するビルトイン関数が存在しないので、よりよいreplaceAll()はどれか調べました。

replaceAll()の引数には文字列をとるものとします。

正規表現オブジェクトやエスケープされた文字列を渡すのは無しです。

この記事ではFoo.protoype.barFoo::barと表記します (例: Array.prototype.join -> Array::join)


前置き

JavaScript で全置換(正規表現も使った)の速度比較 - Qiita という記事をこの前改めて見て、昔もった違和感の原因を思いついたので検証してみようと思いまして。

というのもString::split() -> Array::join()のほうがString::replace(Reg(String::replace(before)), after)よりも速いのは計算量的にしっくりこなかったのです。

この原因は追って説明していきます。


replaceAll()をつくっていく

文字を全置換するには二つのアプローチが考えられます。

一つ目は、正規表現を利用する方法。

二つ目は、単純に文字列処理(String::indexOfなど)を利用していく方法。

ここから一つ目はreplaceAllS、二つ目はreplaceAllRと名付けていきます。

比較のために現在よく使われる(?)、検索で出てくるものもreplaceAllDと名付けていこうと思います。


replaceAllD


replaceAllD1

var replaceAllD1 = (str, beforeReg, after) => {

return str.replace(beforeReg, after);
};

おそらく一番使われているのはないかなと思います。

これは引数に正規表現オブジェクトを渡すので、

replaceAll()には当てはまりませんが比較のために使います。


replaceAllD2

var replaceAllD2 = (str, before, after) => {

return str.split(before).join(after);
};

これは簡単にかけてとても楽ですね。

ただ見る感じ結構無駄な処理をしてそうではあります。


replaceAllR


replaceAllR1

var replaceAllR1 = (str, before, after) => {

return str.replace(new RegExp(
before.replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
, 'g'), after);
};

前書きで書いたJavaScript で全置換(正規表現も使った)の速度比較 - Qiitaのコメント欄にあるものです。

beforeを正規表現オブジェクトに変換するために正規表現でエスケープして、String::replaceを使うというものです。

ここからはこれをいじっていこうと思います。


replaceAllR2

var Replacer = function (before, after) {

this.before = new RegExp(before
.replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
, 'g')
this.after = after;
};
Replacer.prototype.replace = function (str) {
return str.replace(this.before, this.after);
};

var r = new Replacer("abc", "123");
var replaceAllR21 = (str) => {
return r.replace(str);
};

var Replacer2 = class {
constructor(before, after) {
this.before = new RegExp(before
.replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
, 'g');
this.after = after;
}
replace(str) {
return str.replace(this.before, this.after);
}
};

var r2 = new Replacer2("abc", "123");
var replaceAllR22 = (str) => {
return r2.replace(str);
};

D1は正規表現リテラルを使っているので予め正規表現がコンパイルされているのですが1R1では置き換えを実行するたびに正規表現オブジェクトを生成しているのでR2ではそこを改善しました。

str.replaceAll(before, after)strの値は変わってもbeforeafterが変わることは多くはないのではないかということで固定しました。(そもそも一回しか実行しないならどの関数だろうが誤差レベルでしょうし、beforeを変えるなら正規表現で一つにまとめたほうが速そうですし…)

prototypeを使ったものとclassを使ったものの二つ書いてありますが、仕組みは変わりません。

ただ、もしかしたらclassのほうはJavascriptエンジン側の最適化ができてないかもしれないって程度で書きました。


replaceAllR3

var regs = Object.create(null);

var replaceAllR31 = function (str, before, after) {
var beforeReg;
if (before in regs) {
beforeReg = regs[before];
} else {
beforeReg = new RegExp(before
.replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
, 'g');
regs[before] = beforeReg;
}
return str.replace(beforeReg, after)
};

var regsM = new Map();
var replaceAllR32 = function (str, before, after) {
var beforeReg;
if (regsM.has(before)) {
beforeReg = regsM.get(before);
} else {
beforeReg = new RegExp(before
.replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
, 'g');
regsM.set(before, beforeReg);
}
return str.replace(beforeReg, after)
};

一々newしてというのはめんどくさいだろうなと思ってnewしなくてもいいようにしました。

ただ、先ほどのR2と違ってメモリ開放の手段がないので(R2はReplaceR = nullで解放できる)、一度しか使わないといった場合でメモリを食うかもしれません。(解放用の関数を作ってregs[before] = nullなどすればできなくはない)

ObjectMapの二種類用意してありますが、前のprototypeclassと同じ理由です。


replaceAllS


replaceAllS1

var replaceAllS1 = (str, before, after) => {

var result = str;
do {
str = result;
result = str.replace(before, after);
} while (str !== result);
return result;
};

先ほど取り上げた記事の前の記事のJavaScript全置換(正規表現使わない)の速度比較 - Qiitaの冒頭にのっている関数です。

String::replaceを繰り返すというものですね。


replaceAllS2

var replaceAllS2 = (str, before, after) => {

var b = str.indexOf(before);
if (b === -1) return str;
return str.slice(0, b) + after + replaceAllS2(str.slice(b+before.length), before, after);
};

String::replaceを繰り返すと既に走査済みのところも走査してしまうのでString::indexOfString::sliceを利用するようにしました。

分割して見つかった場所より後ろの部分を分割して…と繰り返します。


replaceAllS3

var replaceAllS3 = (str, before, after) => {

var i = 0;
var result = "";
while(true) {
i = str.indexOf(before);
if (i === -1) {
result += str;
break;
}
result += str.slice(0, i) + after;
str = str.slice(i+before.length);
}
return result;
};

ただS2の再帰呼び出しをwhileで書き直しました。

S2は末尾再帰最適化2が効かない形3なので、置き換え箇所が多数あるとUncaught RangeError: Maximum call stack size exceededが発生します。

また、関数呼び出しは遅いというのもあります。


replaceAllS4

var replaceAllS4 = (str, before, after) => {

var i = str.indexOf(before);
if (i === -1) return str;
var result = str.slice(0, i) + after;
var j = str.indexOf(before, i+before.length);
while (j !== -1) {
result += str.slice(i+before.length, j) + after;
i = j;
j = str.indexOf(before, i+before.length);
}
return result + str.slice(i+before.length);
};

S3ではstrを書き換えていたのでstrを書き換えないようにしました。

文字列を書き換えるのと数値を書き換えるのだと数値を書き換えるほうが速いです。(割と違いました)


replaceAllS5

var replaceAllS5 = (str, before, after) => {

var i = str.indexOf(before);
if (i === -1) return str;
var bLen = before.length;
var result = str.slice(0, i) + after;
i += bLen;
var j;
while ((j = str.indexOf(before, i)) !== -1) {
result += str.slice(i, j) + after;
i = j+bLen;
}
return result + str.slice(i);
};

いわゆる人類には(早|速)すぎる高速化ってやつです。

たぶん無駄にごちゃごちゃして意味不明になっただけです。

ほぼ変わらないと思います。


結果

ここまでたくさんのreplaceAll()を書きましたがその計測結果を書きます。

jsPerfは偉大…

replaceAll()
Chrome66(Win)
Canary70(Win)
Chrome68(Android)

D1
571,467
551,045
211,071

D2
358,059
333,419
176,312

R1
414,472
422,145
164,451

R2-1
513,877
493,442
171,090

R2-2
496,295
499,116
172,678

R3-1
496,193
495,639
178,892

R3-2
501,193
495,095
162,004

S1
102,670
127,185
49,012

S2
457,978
450,517
201,365

S3
497,030
505,375
219,658

S4
654,655
716,908
269,525

S5
656,770
729,293
270,619

単位は(Ops/sec)

replaceAlls - jsPerf

S1 << D2 < S2 < R2,R3 < S3 < D1 < S4 <= S5

こんな感じですかね。

計測結果から正規表現レテラルでもよいならD1、使いたくないならR3もしくはS4あたりがよさそうですかね。

ぱぱっと使うだけならD2で十分だとは思います。

もっと速くなる!!!って方法がありましたら是非コメントを!!





  1. 正規表現リテラルは早いのか? - Qiita 



  2. 末尾再帰による最適化 - Qiita 



  3. 効く形でも現地点(2018/08/09)ではSafariしか対応していない