スポンサーサイト
投稿日時 : -------- --:--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
-------- --:-- | スポンサー広告
Javascriptの各メソッドによる行数の数え方と処理速度比較
投稿日時 : 2008-05-25 18:43
行数の数え方: Days on the Moon
 
HTMLのtextareaのvalueやテキストファイルの行数を数えるには改行コード「\n」の数を数えばいいわけですが、どうやって数えるかによって処理速度に大きな差が出るという話です。実験環境はSpiderMonkeyJScript
 
Days on the Moon
行数カウントの実行時間 (10000 回、単位はミリ秒)
改行を含む文字列改行を含まない文字列
SpiderMonkey1.8JScript5.7SpiderMonkey1.8JScript5.7
charAt46816563891360
Array4631047382859
split1081727863
match5022037378
match
(番兵)
543250185110
indexOf952501331
replace446948262
 
 
以下は実験で使用されているコードの説明。
 

■charAt

Days on the Moon
// charAt
var lines = 1;
for (var i = 0, n = s.length; i < n; i++)
if (s.charAt(i) == "\n")
lines++;
charAtで1文字ずつ取り出して\nかどうか調べている。JScriptがなぜこんなに遅いのか分からないがとりあえず避けるべき方法と言える。
 

■Array

Days on the Moon
// Array
var lines = 1;
var chars = s.split("");
for (var i = 0, n = chars.length; i < n; i++)
if (chars[i] == "\n")
lines++;
var chars = s.split("");で1文字ずつ配列に格納する。charAtの時と違ってchars[i]で各配列の値が\nかどうかを調べる。見た目的にはcharAtと大して変わらないがJScriptではこれだけでもそれなりに速くなる。
 

■split

Days on the Moon
// split
var lines = s.split("\n").length;
\nでsplitして得られたArrayオブジェクトのlengthを調べる。速度的にも速いし非常に読みやすく理解しやすい。
 

■match

Days on the Moon
// match
var lines = (s.match(/\n/g) || []).length + 1;
matchを使って\nをグローバル検索し得られたArrayオブジェクトのlengthを調べる。「|| []」があるのは\nが見つからなかった場合に返されるオブジェクトがArrayオブジェクトではなく、lengthプロパティを参照しようとするとエラーになってしまうのでそれを回避するため。ちなみに「[].length」は0が返される。
 
 

■match(番兵)

Days on the Moon
// match (番兵)
var lines = (s + "\n").match(/\n/g).length;
さっきのmatchに番兵を置いたバージョン。「|| []」とする代わりに「\n」を文字列sの末尾に追加し、確実に一つはArrayオブジェクトが生成されるようにし、lengthプロパティ参照でエラーが起こりえないようにしている。
 

■indexOf

Days on the Moon
// indexOf
var lines = 1;
var i = -1;
while ((i = s.indexOf("\n", i + 1)) >= 0)
lines++;
indexOfで\nを検索、見つからなかった場合に返される-1になるまでwhileでループする。意外にもほぼ最速。しかし後述するが検索対象の文字列の内容によって速度が大きく変化するのでいつでも最速というわけにはいかないようです。
 

■replace

Days on the Moon
// replace
var lines = s.length - s.replace(/\n/g, "").length + 1;
sの全体のlengthから\nを削除した文字列のlengthを引くことで\nの数を判定。
 
 

■もう少し詳細に

この行数の数え方: Days on the Moonの記事を受けてトラックバックに
 
文字列処理の性能に関する考察 - blanket-log
 
というのがあってより詳しく調べてくれています。

■charAtとArrayは本当はArrayが断然速い

上記の実験ではArrayとcharAtがどちらも遅く、大して変わらないという印象でしたが、ArrayバージョンではsplitによるArrayオブジェクトへの変換に時間がかかっているだけで、ループ内の処理はcharAtと比べて断然速いようです。
 

■indexOfは検索対象文字数とループ数、時間が比例する

最速かと思われたindexOfですが、文字列中に含まれる検索対象文字(\n)が多くなると一気に速度が落ちるようです。これは改行数に比例してループ数が多くなるため時間もそれに応じて多くかかってしまうから。しかしループ数が少ない場合は新たなオブジェクトの生成などが発生しないぶんだけ非常に高速になる。
 

■splitとmatchは似ている

splitはもとの文字列への参照を持つArrayオブジェクトが生成されるだけで、内部で新たな文字列にコピーが行われるといったことがないので高速になるということらしい。matchも生成されるのはArrayオブジェクトなので、内部処理はsplitと同じようものだろうということらしいです。
 

■実はreplaceが最速

改行数が多い場合はreplaceが最速という結果になるようです。走査処理はsplitと似ているが、最終的に生成されるのが文字列というのがspilitとの違いで、そのArrayオブジェクトとStringオブジェクトの生成コストの差が性能の差になっているようです。
 
 

■まとめ

各方法にはそれぞれ得意とする分野があるので、対象文字列の内容がどのようなものかによって使い分けるのがいいと思われます。charAtは論外ですが。予想できない場合は無難にsplitを使ってれば安心かも。splitが一番可読性が高い気がするし。  
 
スポンサーサイト
2008-05-25 18:43 | Javascript | Comment(0) | Trackback(0)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。