単純なマッチで複数回replaceするのと、文字クラスを使って一回replaceするのでは、どちらが速いか

qiitaでこんな記事がありました。

innerText(textContent)/innerHTMLを使わずJavaScriptでHTMLエスケープ - Qiita

で、思い出したのですが「文字クラスでreplaceを一度で済ますより、単純なマッチを直列で繰り返したほうが速い」って話しをどこかで聞いた覚えがあるので、どのぐらい差があるのか、ちょっと試してみました。

念のため、元記事の関数でテーブル参照をしないバージョン（escapeCharClassEx）も用意。

3パターンのescape関数

// 元記事の関数
var escapeCharClass = function(content) {
  var TABLE_FOR_ESCAPE_HTML = {
    "&": "&",
    "\"": """,
    "<": "&lt;",
    ">": "&gt;"
  };
  return content.replace(/[&"<>]/g, function(match) {
    return TABLE_FOR_ESCAPE_HTML[match];
  });
};

// 念のためテーブル参照しないバージョン
var escapeCharClassEx = function(content) {
  return content.replace(/[&"<>]/g, function(match) {
    switch(match){
    case "&": return "&amp;";
    case "\"": return "&quot;";
    case "<": return "&lt;";
    case ">": return "&gt;";
    }
  });
};

// 4回replaceバージョン
var escapeSerial = function(content){
  return content
    .replace(/&/g, "&amp;")
    .replace(/"/g, "&quote;")
    .replace(/</g, "&lt;")
    .replace(/>/g, "&gt;");
};

検証プログラム

以下の様な感じで、入力文字が短い場合と長い場合の双方で速度を比較してみました。

var replicateString = function(text, times){
  var ret = [];
  for(var i = 0; i < times; i++){
    ret.push(text);
  }
  return ret.join("\n");
};

var testEscapeSpeed = function(){
  var text = "hoge&hage>hige<hoge";
  var text_short = replicateString(text, 10);
  var text_long = replicateString(text_short, 100);
  var replace_many = function(text, replace_fn, times){
    times = times || 1000;
    for(var i = 0; i < times; i++){
      replace_fn(text);
    }
  };

  console.time("char class short");
  replace_many(text_short, escapeCharClass);
  console.timeEnd("char class short");

  console.time("char class short ex");
  replace_many(text_short, escapeCharClassEx);
  console.timeEnd("char class short ex");

  console.time("serial short");
  replace_many(text_short, escapeSerial);
  console.timeEnd("serial short");

  console.time("char class long");
  replace_many(text_long, escapeCharClass);
  console.timeEnd("char class long");

  console.time("char class long ex");
  replace_many(text_long, escapeCharClassEx);
  console.timeEnd("char class long ex");

  console.time("serial long");
  replace_many(text_long, escapeSerial);
  console.timeEnd("serial long");
};

検証結果

Chrome40で走らせた結果、以下のような結果になりました。

test name	time
char class short	7.573ms
char class short ex	4.213ms
serial short	1.972ms
char class long	296.516ms
char class long ex	264.621ms
serial long	128.274ms

単純なマッチで4回replaceしたバージョン（escapeSerial）が、短い文字列では4倍程度、長い文字列だと2倍ちょっとぐらい速いという結果でした。

いや、ちょっとおかしい

文字クラスを使った場合の関数は、単にマッチ後のコールバック関数呼び出しのオーバヘッドが入るだけではあるまいか、ということでescapeSerialにおける各replace処理を関数で置換するように変えたら、今度は4回呼び出しのほうがコールバックの回数が増えたぶん、少しだけ遅かったです。

test name	time
char class short	5.004ms
serial short	5.218ms
char class long	2559.319ms
serial long	3020.997ms

ということで、

1. 文字クラスで複数文字を一回でマッチ＆置換させても、それぞれの文字で一回ずつ置換しても速度は殆ど変わらない
2. しかしそれぞれの置換でコールバック関数を呼ぶとパフォーマンスは二倍ぐらい遅くなる
3. 各関数の呼び出しの中でテーブル参照すると更に遅くなる

みたいです。

たぶん1については、4×1と1×4程度の違いなんだと思います。

GADTというものを知った

最近OCamlをようやくversion4系列にアップデートしたのですが。

その際にGADTとかいう言葉が気になったので調べていたら、ちょうどわかりやすいエントリーが。

Detecting use-cases for GADTs in OCaml

上のエントリによると、どうやらGADTというのは「代数型に型の強制を付けるためのもの」らしいです。

どいういうことかというと、例えばとあるexprという代数型を

type expr = 
  | Tint of int
  | Tbool of bool

と宣言した時、exprは中身がintの時もあれば、boolの時もある型ですよ、と宣言しているわけですが…

つまりTint 10もTbool falseも、同じexpr型に属することになりますよ、としているわけですが…

このexpr型を使って構成される「別の代数型」というものを考えた時、単にexpr型とだけ宣言されると、表現としてイマイチになることがあるのですよね。

例えば次のようなAbstract Syntax Treeを定義したとき…

type ast = 
  | Value of expr
  | IfExpr of expr * expr * expr

なんかIfExprのexpr * expr * exprの部分の表現力が乏しくないですか？

exprが３つ並んでるんですけど、それぞれがどういう性質のexprを要求しているのか、よくわからないですよね。

もしこのIfExprを

IfExpr of （bool値のexpr） * （int値のexpr） * （int値のexpr）

みたいなニュアンスで型を制限できたら、安全だし、わかりやすくないですか？

これを、まさに可能にするのがGADTというやつらしく。

ちなみにGADTというのは、Generalized Algebraic Data Typeの略で日本語なら「汎用代数型」とでも訳すのでしょうか？

実際にexprとastをそれぞれGADTを使った型宣言（expr'とast'とする）に書き直すと、こういう感じになります。

type _ expr' = 
  | Gint: int -> expr' 
  | Gbool: bool -> expr'

type _ ast' = 
  | GValue: int expr'
  | GIfExpr: bool expr' -> int expr' -> int expr' -> int expr'

普通の代数型だとofが来る部分に:が来て、右側が「型の関数」みたいな記述になるのが特徴です。

で、構成される代数型に型の制約を付けたい場合はtype _ expr' = ...みたいに宣言します。

アンダースコアの部分は「代数型に何かしらの型アノテーションがつくよ」みたいなニュアンスなんでしょうか？

こうやって作られたGADTを使うと、

let statement_by_gadt : ast' = GIfExpr (Gint 10) (Gint 20) (Gint 30)

は、IfExprの一つ目のexpr'が「bool expr'」じゃないので、コンパイルの段階でエラーになります。

一方で、GADTじゃない、普通の代数型のastを使った場合、次の

let statement_no_gadt : ast = IfExpr (Tint 10) (Tint 20) (Tint 30)

は（型の上では）エラーではありません。

IfExprを構成するメンバーは全てexpr型と規定されているだけなので、型の上では正しいからです。

これを構文エラーにするには、evalするときにundefned patternとして、型エラーを自前で書くしかないわけですが、GADTで制約していればコンパイルの段階でエラーにしてくれます。

nanocのほうがjekyllより良いかも

nanocとは

nanocはRuby製の静的サイトジェネレーターです。

静的サイトジェネレーターとは、固定的な内容のウェブサイトを作るのに使われるサイトジェネレーターです。

ホームページ制作ツールのような複雑なIDEではなく、コマンドラインとエディタでサクっとサイトが作れるので、プログラマーには人気があります。

昨今はそうしたツールでブログを公開する人も珍しくなくなりました。

ちなみにこの記事ではnanocの使い方は説明しません。本家に丁寧な説明があるので、そちらを参照して下さい。

jekyllとの違い

Ruby製の静的サイトジェネレーターといえば、jekyllも有名ですが、最近はnanocを主に使っています。

理由は記事の変換処理を柔軟に扱えるからです。

jekyllでも記事を変換する場合に、独自の処理を設定することは出来ますが、変換エンジン「そのもの」の切り替えしかできません。

しかしnanocでは、変換処理をfilterという単位で分割定義できて、それらを記事の「メタデータ」に応じて自由に組み合わせて適用させることができます。

例えば「コードハイライトの前処理は、プログラミング系の記事にだけ適用する」といった具合にです。

サンプルケース

マークダウンをCSSフレームワークと合わせて使った場合、デフォルトの出力では困ることがありますよね。

例えばタグに、そのCSSフレームワークで使う特別なクラス属性を付けたかったりとか。

でもマークダウンで次のように書くと、

## これはH2

もちろん次のように変換されるわけですが、

<h2>これはH2</h2>

こういう風に出したい時もあるわけじゃないですか。

<h2 class="my-header">これはH2</h2>

こういう場合、そのまま生でタグを打ってもいいのですが、せっかくマークダウンを使っているのですから、楽をしたいものです。

というわけで、nanocのfilterを定義しちゃいましょう。

filterを定義する

要件定義として、次のように宣言したら目的のコードが出力される、としましょう。

[myheader2 これはH2]

要はこのコードをマークダウンにかける前に、正規表現で目的のコードに変換すればいいのです。

そこでlib/filters.rbなどというファイルを作り、次のような処理を書いて、my_headerという識別子のフィルタを定義します。

class MyHeader < Nanoc::Filter
  identifier :my_header
  type :text
  def run(content, params={})
    content.gsub(/\[myheader(\d)\s+(.+?)\]/, "<h\\1 class='my-header'>\\2</h\\1>")
  end
end

次にRulesというファイルで、今作ったmy_headerというfilterを、マークダウン変換の前に差し込みます。

compile '*' do
  if item[:extension] == 'md'
    filter :my_header # <- これを追加！
    filter :kramdown # マークダウン変換処理
    layout 'default'
  end
end

しかしこれだと、全てのマークダウンファイルにmy_headerフィルタを通してしまいますよね。

なので、itemにuse_my_syntaxというメタデータが設定されているときだけ適用させるようにしてみます。

compile '*' do
  if item[:extension] == 'md'
    if item[:use_my_syntax] then # 独自文法使う？
      filter :my_header # <- これを追加！
    end
    filter :kramdown # マークダウン変換
    layout 'default'
  end
end

比較としてjekyllの独自コンバーター定義の方法を抜粋しておきます。

class Jekyll::Converters::Markdown::MyCustomProcessor
  def initialize(config)
    require 'funky_markdown'
    @config = config

  def convert(content)
    ::FunkyMarkdown.new(content).convert
  end
end

上記のconvertという関数を拡張するわけですが、見たらわかるように引数として元記事のcontentしかもらえないわけです。

しかしnanocでは記事に付いたメタデータを見ながら処理を分岐できるので、これは大きなアドバンテージです。

ちなみに記事のメタデータを付ける方法は、記事の先頭に次のようなヘッダーを書くだけです。

---
use_my_syntax: true
---

ヘッダーはYAMLで記述します。

最後に

最後に、nanoc.ymlのpruneについて。

prune:
  auto_prune: true
  exclude: [ '.git', '.hg', '.svn', 'CVS', ".gitignore", "push.sh" ]

auto_pruneを有効にすると、使用されていないファイルを削除してくれます。

デフォルトでは有効になっていませんが、trueに設定することをおすすめします。

これを有効にしてないと、元記事のファイル名を変えた時に、古いファイルが出力先に残り続けてしまいます。

例えばあるときにtop.mdというファイルを、welcome.mdに変えたくなったとしましょう。

そのまま放置してしまうと、出力先にtop/index.htmlというファイルが残ってしまいます（a.mdはa/index.htmlに出力されるのがデフォルトのルール）。

しかしpruneをtrueにしておくとtop/index.htmlは自動で削除されます。

段落ごとにコメントできる縦書き文章の作成サービスを公開しました

Brushup! について

段落ごとにコメントできる縦書き文章の作成サービスBrushup!を作りました。

パスワードを付けることもできるので、特定の人にだけ見せる使い方も可能です。

主に編集や校正の依頼に使えるツールを想定しています。

段落へのコメントを試してみたい方は、お試し用のエントリからどうぞ（コメントを投稿するにはユーザー登録が必要）。

ユーザー登録について

グーグルアカウントで登録できます。

マークアップについて

マークダウンという文法ですが、普通に文章を書く感覚で使っても、大体は思ったとおりの出力になるんじゃないかと思います。

マークダウンについては、ヘルプにも少しだけ説明しましたが、細かいことは各自で調べて下さい。

ちなみに縦書き文庫の記法は基本的にはそのまま使えるはず（全部はまだ試していませんが…）

チップ記法とか台詞記法とかは大丈夫でした。

またルビの記述ですが、Brushup!では簡易記法を用意しました。

[ruby 漢字 かんじ]にルビをふる。

みたいに書けます。多少はタイプ量が減るかと…

活動メモについて

次にプロフィールページにある「活動メモ」というものですが、自分の活動の中で報告したいものを勝手に書き込んで下さい。

サービスの性質上、プロフィールページに公開投稿を自動で一覧表示、みたいな機能は敢えて用意していません。

活動メモを使って、自分の言葉で報告したりしなかったりすればいいと思います。

ちなみに投稿した文章のURLは、連番じゃなくてハッシュ値で作られるので、自分でURLを公開しない限りはアクセスされないと思います。

もちろん非公開にすることも出来ますし、パスワードを付けて公開することも可能です。

datasetにセットしたboolean値について

ちょっとハマったのでメモ。

例えば、

<div id="foo" data-hoge="true"></div>

とかあったとき、以下の結果はどちらもfalse

$("#foo").data("hoge") == "true" // false
$("#foo").data("hoge") === "true"  // false

理由はdatasetにセットした"true" もしくは "false"は、boolean型として評価されるから…

typeof $("#foo").data("hoge"); // "boolean"
$("#foo").data("hoge") === true; // true

ちなみにnehan.jsも、datasetの値はズボラぶっこいて、一律で文字列型のまま返しちゃっていたので、今さっき直しました。

脚本を台詞記法で書く

ちょっとした小ネタですが、縦書き文庫の台詞記法はキャラクタ登録なしでも使えます。

キャラクタ名の部分に、人物の名前をそのまま書けば、キャラクタ画像じゃなくて文字列で表示されます。

なので、ちょっとした脚本は次のような感じで書けます。

[speak 太郎 今日は天皇杯の決勝だね。]
[speak 次郎 去年まで同じJ2で戦ってた同士が決勝って凄いね。]

詳しくは縦書き文庫ヘルプ | 台詞記法を参照して下さい。

チップ記法

わざわざtipタグを書くのが煩わしいので、チップ用の記法を用意しました。

チップについては 縦書き文庫 | チップ記法 を参照のこと

文法

次のように記述します。

[tip タイトル:内容]

注意

• tipとタイトルの間には一つ以上の半角スペースが必要です。
• タイトルと内容の間には半角のコロン:が必要です。

台詞記法で吹き出しの有無を切り替えられるようになりました

台詞記法で、吹き出しの有無を選べるようになりました。

声に出す台詞はspeakを使います。

[speak taro これは声に出して言う台詞！]

心のなかの台詞はthinkを使います。

[think taro これは心のなかの台詞…]

実際に表示させるとこんな風になります。

詳細は縦書き文庫ヘルプ | 台詞記法についてを参照のこと。