Javascriptでは文字を全置換するビルトイン関数が存在しないので、よりよいreplaceAll()はどれか調べました。
replaceAll()の引数には文字列をとるものとします。
正規表現オブジェクトやエスケープされた文字列を渡すのは無しです。
この記事ではFoo.protoype.barはFoo::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は正規表現リテラルを使っているので予め正規表現がコンパイルされているのですが1、R1では置き換えを実行するたびに正規表現オブジェクトを生成しているのでR2ではそこを改善しました。
str.replaceAll(before, after)でstrの値は変わってもbeforeとafterが変わることは多くはないのではないかということで固定しました。(そもそも一回しか実行しないならどの関数だろうが誤差レベルでしょうし、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などすればできなくはない)
ObjectとMapの二種類用意してありますが、前のprototypeとclassと同じ理由です。
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::indexOfとString::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で十分だとは思います。
もっと速くなる！！！って方法がありましたら是非コメントを！！
-
効く形でも現地点(2018/08/09)ではSafariしか対応していない ↩