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 続き

http://dev.ariel-networks.com/Members/uchida/javascript7684startswith/
文字列が短いときはindexOf版に及びませんが、
私はこれを単に、lastIndexOf版はindexOf版より引数が増えたため範囲チェック等の処理が増えたんだろうと思っていました。
がendsWithを調べたところ、どうもそれだけではないようです。

goog.string.endsWith = function(str, suffix) {
var l = str.length - suffix.length;
return l >= 0 && str.lastIndexOf(suffix, l) == l;
};
closureのendsWithはご覧のとおりlastIndexOfを読んでいます。

startsWithでは逆にこれをindexOfに書き換えれば無駄な探索がなくなる、しかも引数の数が同じなので見つけた場合の速度も変わらないはず。

で、これが結果です。
fujitaさんにJSLitmus.jsというツールを教えてもらったのでそれを使ってます。数字が大きいほど速い処理になります。


lastIndexOfindexOf
abcdefghi endsWith hi162055378256192
abcdefghi endsWith h*108768037332453
abcdefghijklmnopqrstyuwx endsWith wx130900527744009
abcdefghijklmnopqrstyuwx endsWith w*65863347931452
abcdefghijklmnopqrstyuwxyzABCDEFGHIJKLM endsWith LM147261986611250
abcdefghijklmnopqrstyuwxyzABCDEFGHIJKLM endsWith L*51857137813253

前回はあまりに極端なパターンだったのでstartsWithの方も測り直しています。
startswith-endswith-benchmark-20100123.zip
startswith-endswith-benchmark-results-20100123.zip

文字数が少ない場合にindexOf版endsWithが遅くなるのは予想外でした。
分岐予測の失敗でもしているのでしょうか?
アルゴリズムから見ればlastIndexOf版startsWithやindexOf版endsWithの方が速くなりそうに見えるんですが。
なんか納得いかないなあ。

Category(s)
JavaScript
The URL to Trackback this entry is:
http://dev.ariel-networks.com/Members/uchida/javascript7684startswith-7d9a304d/tbping
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.