XPath の transelate() を JavaScript で実装する

概要

XPath の translate() を JavaScript で実装しました。
XPath の仕様通りに実装した translate.js と機能拡張した translate-by-array.js があります。

translate.js: XPath の仕様通り、String型の値を引数にとります。1文字単位での置換しか行えませんが、array-ver より桁違いに速く置換できます。
translate-by-array.js: 配列を引数に取るバージョンです。XPath の translate 関数との互換性はなくなる代わりに2文字以上の置換を行えます。

ダウンロード

translate.js : XPath の translate() 関数。 ― Gist

パフォーマンス比較

jsPerf で比較テストした範囲では最速になりました。

高速化Tips

ECMAScript の原理上、グローバル変数が遅い(スコープチェーン)のでローカル変数にキャッシュしてます。
ECMAScript の原理上、プロパティアクセス演算子が遅い(プロトタイプチェーン)ので2回以上同じプロパティを参照する場合はローカル変数にキャッシュしてます。オブジェクトで辞書を作る方法も控えました。
同じプロパティ参照でも new Object と new Array では new Array の方が若干速い気がします。ECMAScript 規定上は変化ないはずですが、Firefox は配列だけ特別な実装をしていたとどこかの記事で読んだ覚えが…。(array[i] と object.property で実装が異なる)
String#indexOf も遅くないようです。id:babu_babu_baboo さんは string.split('') で配列化して Array#indexOf していましたが、string版なら String#indexOf だけの方がコストが軽くなるんじゃないかな、と。
Array#push は IE7- だと遅いそうですが、最近の実装は逆なのであえて Array#push を使用しています。動作保証に IE7- を含めるなら条件付きコンパイルを使うと良いかも。
置換文字列の ToString() は Array#join で処理されるので String() を省略しました。
検索文字列長が置換文字列長より大きい場合に削除する方法に ToString(undefined) === '' を利用しています。Array#join 時に空文字に変換されます。

参考URL

id:babu_babu_baboo さんのブログに寄せされた情報を参考にさせていただきました。gtlt さんにはいつもお世話になってます。m(_ _)m

Twitterログ

think49 think49

#XPath の translate() 関数。/
translate - MDC Docs
http://goo.gl/QgDLs

think49 think49

図解付きでわかりやすい。/
たのしいXML: XPathとXSLTの関数 translate
http://www6.airnet.ne.jp/manyo/xml/functions/step23.html #XPath

think49 think49

translate() - XML Path Language (XPath)
http://goo.gl/0Ll42 #XPath #W3C

think49 think49

#JavaScript で実装してみた。/
translate.js : XPath の translate() 関数。 — Gist
https://gist.github.com/966219 #ECMAScript

think49 think49

なるほど。string.split('') すれば処理を効率化できるんだなー。やってみよう。/
2011-05-11 - babu_babu_babooのごみ箱
http://goo.gl/OFRFz

think49 think49

更新。https://gist.github.com/966219

think49 think49

jsPerf でベンチマークテストしてみる。gtlt さんのコードが最速。さすがだなあ…。
http://jsperf.com/translate-function-of-xpath #JavaScript #XPath

think49 think49

名前を変えて再テスト。gtlt さんのコードは Google Chrome だと爆速だなあ。よく読んでみよう。
http://goo.gl/oUCbI #JavaScript #XPath

think49 think49

translate.js を更新。(@version 1.1.1) https://gist.github.com/966219 #JavaScript #XPath

think49 think49

ようやく最速に出来ました。http://goo.gl/DY6Iw #jsPerf #JavaScript

think49 think49

http://goo.gl/u4VUN で指摘を受けた予約語について調べてみる。"char" が予約語かどうか？

think49 think49

調べようとした矢先に gtlt さんからレスが！http://goo.gl/PyTmL
たった今、"char" が #ES3 の「将来の予約語」であることを確認したところです、はいｗ
http://goo.gl/0HUIQ

think49 think49

現行版では _char として予約語を回避。「translate() の文字数一致」についても調べよう。

think49 think49

<q>For example, translate("--aaa--","abc-","ABC") returns "AAA".</q>
<cite> http://goo.gl/0Ll42 </cite> #XPath

think49 think49

@think49 なるほど、'-' は削除するのか。

think49 think49

i と index を間違えていた恥命的なミスを修正…。
https://gist.github.com/966219 #JavaScript #XPath

think49 think49

translate("--aaa--","abc-","ABC") === 'AAA'; // true

think49 think49

検索文字列長が置換文字列長より長いとき削除するようにした。(@version 1.1.3)
https://gist.github.com/966219 #JavaScript #XPath

think49 think49

@think49 #jsPerf も更新。あり得ないほどに速くなっているのはなぜ？桁が違いすぎる…。
http://goo.gl/DY6Iw #JavaScript

think49 think49

@think49 あまり数を多くするのもどうかと思って、@version 1.1.1 のコードを @version 1.1.3 のコードに置き換えたのだけど、#jsPerf の revision (URL) は変わらないのね。前回の記録が消えてしまった…。

think49 think49

@think49 while で無限ループしてしまう不具合を修正。(@version 1.1.4)
translate-by-array.js を追加した。
https://gist.github.com/966219 #JavaScript #XPath

think49 think49

#jsPerf で速度をみると「version 1.1.3 >>> version 1.1.4」になるのだけど理由がさっぱりわからない…。
http://goo.gl/Y2Tk9

think49 think49

version 1.1.3 から一部のコードを削除した版が version 1.1.4 だから version 1.1.4 の方が速いと思ってた。あり得ないぐらいに version 1.1.3 が速いけどバグ持ちだから使う気にはなれないなあ…。

azu_re azu

@think49 http://jsperf.com/translate-function-of-xpath/5 こう測るのが自然かと。さっきのrev4はtranslate_2(hankaku, hankaku, zenkaku);が呼ばれてなかったので、早くて当たり前になってた

think49 think49

@azu_re ありがとうございます。version 1.1.3 は [[Call]] してなかったんですね…。速いわけです。OTL

think49 think49

改めて version 1.1.3 を削除して #jsPerf でテスト。http://goo.gl/dOWTK

think49 think49

array版も #jsPerf でテスト。候補が2つだけですが、とりあえず最速。
http://goo.gl/lGcqQ #JavaScript #XPath