2010/01/21
Document Actions
JavaScript的startsWith
closureのgoog.string.startsWithやprototype.jsのString.startsWithではindexOfを呼ぶコードになってます。
goog.string.startsWith = function(str, prefix) {
return str.indexOf(prefix) == 0;
};
これだとstrが長い文字列でしかもprefixがstr内になかった場合に無駄な探索処理をやる羽目になります。
代わりに正規表現やsubstringを使って比較をすれば処理速度の悪化は避けられそうですが、正規表現や文字列のオブジェクト生成コストが気になります。
そこでlastIndexOfを使って書けば無駄な探索もオブジェクト生成も避けられるはずです。
str.lastIndexOf(prefix, 0) == 0;
もちろんendsWithもindexOfで書き換え可能です。
測ってみました。
検証コードstartswith.zip
A: 'abc'.startsWith('ab')を100000回
B: ('x' * 10000)+'abc').startsWith('ab')を10000回
| IE6(A) | IE6(B) | FireFox3.5(A) | FireFox3.5(B) | |
|---|---|---|---|---|
| indexof | 125ms | 266ms | 3ms | 459ms |
| lastindexof | 141ms | 16ms | 5ms | 1ms |
| regexp | 297ms | 47ms | 29ms | 608ms |
| substring | 234ms | 15ms | 15ms | 2ms |
文字列が短いときはindexOf版に及びませんが、予想通り長くなったときの性能悪化はなくなりました。
少し意外だったのはFireFoxの正規表現版がO(n)だったところでしょうか。
CなんかだとcharAtで一文字ずつ調べた方が速そうですが、文字列生成のコストが高そうな気がしたのでやりませんでした。
fujitaさんが測定してくれた結果ではこうなりました。Chorme速いなあ。
| Safari(A) | Safari(B) | Chrome(A) | Chrome(B) | FF(A) | FF(B) | |
|---|---|---|---|---|---|---|
| indexof | 6ms | 97ms | 8ms | 198ms | 3ms | 412ms |
| lastindexof | 6ms | 0ms | 9ms | 1ms | 4ms | 1ms |
| regexp | 21ms | 67ms | 13ms | 1ms | 19ms | 547ms |
| substring | 17ms | 2ms | 14ms | 1ms | 9ms | 0ms |
まあJavaScriptで10000文字もあるような文字列を扱うことは稀でしょうけど。
- Category(s)
- JavaScript
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/uchida/javascript7684startswith/tbping
https://groups.google.com/group/closure-library-discuss/browse_thread/thread/d0eed33a86410
つまり"hogehoge".starttsWith("hoge")がfalseになってしまうと思います。
> つまり"hogehoge".starttsWith("hoge")がfalseになってしまうと思います。
lastIndexOfの第2引数に0を指定してるため、'hogehoge'.lastIndexOf('hoge', 0)の結果が0になります。