JavaScript
Chrome
最適化
高速化

最速のreplaceAll()を求めて

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しか対応していない