Personal tools
You are here: Home ブログ uchida JavaScript的startsWith
« December 2010 »
Su Mo Tu We Th Fr Sa
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
Categories
JavaScript
Go
Ada
Delphi
junk
 
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)
indexof125ms266ms3ms459ms
lastindexof141ms16ms5ms1ms
regexp297ms47ms29ms608ms
substring234ms15ms15ms2ms

文字列が短いときはindexOf版に及びませんが、予想通り長くなったときの性能悪化はなくなりました。
少し意外だったのはFireFoxの正規表現版がO(n)だったところでしょうか。
CなんかだとcharAtで一文字ずつ調べた方が速そうですが、文字列生成のコストが高そうな気がしたのでやりませんでした。

fujitaさんが測定してくれた結果ではこうなりました。Chorme速いなあ。


Safari(A)Safari(B)Chrome(A)Chrome(B)FF(A)FF(B)
indexof6ms97ms8ms198ms3ms412ms
lastindexof6ms0ms9ms1ms4ms1ms
regexp21ms67ms13ms1ms19ms547ms
substring17ms2ms14ms1ms9ms0ms

まあJavaScriptで10000文字もあるような文字列を扱うことは稀でしょうけど。

Category(s)
JavaScript
The URL to Trackback this entry is:
http://dev.ariel-networks.com/Members/uchida/javascript7684startswith/tbping

Re:JavaScript的startsWith

Posted by inoue at 2010-01-22 01:46
すばらしい。Google越えました。

Re:JavaScript的startsWith

Posted by uchida at 2010-01-25 23:30
googleを越えるのはなかなか難しそうです。
https://groups.google.com/group/closure-library-discuss/browse_thread/thread/d0eed33a86410

Re:JavaScript的startsWith

Posted by 2323 at 2010-03-24 16:41
素朴な疑問ですがlastIndexOf()だとstr中にprefixが2回以上ある場合に正しくならないのでは?
つまり"hogehoge".starttsWith("hoge")がfalseになってしまうと思います。

Re:JavaScript的startsWith

Posted by uchida at 2010-04-26 14:51
> 素朴な疑問ですがlastIndexOf()だとstr中にprefixが2回以上ある場合に正しくならないのでは?
> つまり"hogehoge".starttsWith("hoge")がfalseになってしまうと思います。

lastIndexOfの第2引数に0を指定してるため、'hogehoge'.lastIndexOf('hoge', 0)の結果が0になります。
Add comment

You can add a comment by filling out the form below. Plain text formatting.

(Required)
(Required)
(Required)
(Required)
(Required)
This helps us prevent automated spamming.
Captcha Image


Copyright(C) 2001 - 2006 Ariel Networks, Inc. All rights reserved.