大量の文字列データは処理に時間がかかるものです。
ここでは、速度的に“賢い”文字列操作の例をいくつか紹介します。
「行ごとに区切られた文字列」というのはおそらく最も見慣れた文字列でしょう。
目にする機会が多いがゆえに、スクリプトからも使う機会も多くなります。
その需要に応じてか、HSPにはメモリノートパッド機能という一連の命令群がありますね。
しかし、それらを使わない方がよい場面もあるのです。
次のような簡単な例を考えてみましょう。
// noteget 版 text = {" りんご ごりら らっぱ "} notesel text // 行数だけ繰り返す repeat notemax // 第 cnt 行の文字列を lineStr に代入する noteget lineStr, cnt mes strf("#%2d: ", cnt) + lineStr loop noteunsel stop
この例の場合は、何も問題ありません。
しかし、このスクリプトには潜在的に無駄があるのです。
noteget 命令は、notesel 命令によって与えられたバッファの、先頭から一行目、二行目、三行目……と順々に数えていき、指定された行の文字列を取り出す、という処理をしています。
この例では、ループの2周目で2行目を探して取り出し、ループの3周目では2行目を探してから次に3行目を探して取り出し、4周目では……
「いやいや、4行目は3行目の次だろ！」
もう少し一般的に、元となる文字列データ txt の行数を m (= notemax) としましょう。
1回のループにつき、noteget 命令は文字列データの cnt 番目の行を見つけるまで、「次の行を探す」処理を行います。ループ全体でみると、「次の行を探す」操作は 1 + 2 + ... + m = (m^2 - m)/2 回程度行われます。(m^2 は m * m という意味。)
そのため、文字列の行数 m が大きくなると、かかる時間は体感できるほど長くなってしまうのです。
そこで、賢い処理をして時間短縮をするには、getstr を使います。
// getstr 版 text = {" りんご ごりら らっぱ "} // 文字列の中の「位置」を覚えておく変数 index = 0 repeat // 次の行を取り出して、sLine に代入する getstr lineStr, text, index index += strsize if ( strsize == 0 ) { break } // 何も取り出せない => 終端 // 各行についての処理 mes strf("#%2d: ", cnt) + lineStr loop stop
getstr 命令も文字列の一部を取り出す関数ですが、「どこから取り出すのか」を選ぶことができ、さらに「どこまで取り出したのか」を取得することができます。
そのため「cnt 行目の次」の位置を記憶していくことで、その次の行の取り出しをすぐに行うことができるのです。
さきほどと同様に文字列データの行数を m とすると、1回のループにつき「次の行を探す」処理が 1 回だけ行われます。ループ全体では 1 + 1 + ... + 1 = m 回です。
noteget を使うのと同じことをしているのに、実行する処理の回数が大幅に減りましたね。[脚注]
ところで、そもそも今までの例のように、noteadd のような文字列の変更操作をしないのであれば、もっと単純に split を使うという方法もあります。
// split 版 text = {" りんご ごりら らっぱ "} split text, "\n", allLines repeat length(allLines) mes strf("#%2d: ", cnt) + allLines(cnt) loop stop
とても便利ですね。メモリノートパッド命令とは一体なんだったのか……！
さて、実際のところ、これらの方法はそれぞれどのくらい時間がかかるのでしょうか。
少し計測してみましょう。
注意：次のスクリプトは、実行するのにとても時間がかかる可能性があります。
// 行に分けるのにかかる時間を計測する // 「benchmark lb」……ラベル lb を実行するのにかかる時間を測って、表示する命令 mes "とても行数の多い文字列を作ります……" lb = *LMakeLongLongString : benchmark lb lineStr = "" // それぞれの方法で文字列を区切る mes "noteget 版" : lb = *LNotegetVer : benchmark lb mes "getstr 版" : lb = *LGetstrVer : benchmark lb mes "split 版" : lb = *LSplitVer : benchmark lb stop // とても行数の多い文字列を作る *LMakeLongLongString CountLines = 7000 // 本来は #define を使うべき sdim text, ((16 + 2) * CountLines) + 1 repeat CountLines text += "0123456789ABCDEF\n" loop return // noteget を使うバージョン *LNotegetVer notesel text repeat notemax noteget lineStr, cnt // 何もしない loop return // getstr を使うバージョン *LGetstrVer index = 0 repeat getstr lineStr, text, index : index += strsize if ( strsize == 0 ) { break } // 何も取り出せない => 終端 // 何もしない loop return // split を使うバージョン *LSplitVer split text, "\n", allLines repeat length(allLines) // lineStr = allLines(cnt) // 何もしない loop return #include "d3m.hsp" // for d3timer() #module #deffunc benchmark var lbProc // 現在時刻を記録 time = d3timer() gosub lbProc // かかった時間を表示する mes "" + (d3timer() - time) + "ミリ秒" return #global
僕のパソコンで試したところ、次のような結果でした：
| 方法 | 時間 (ミリ秒) |
|---|---|
| noteget | 312 |
| getstr | 3 |
| split | 221 |
全部ほぼ 0 秒だという方は、CountLines の数値を大きくしてみてください。
前述の通り、noteget が一番遅く、split, getstr が速い、という結果になると思います。
実は split も内部的には getstr 版と同様に、行数回だけ反復する処理なのですが、切り出した文字列を配列変数に入れていくのに時間がかかっているのだと思います。
ところで、上のスクリプトにも無駄があります。
長い文字列を作る部分に、それなりの時間がかかったはずです。
文字列などのデータが書き込まれる領域のことをバッファといい、そのバッファに書き込めるデータの大きさ(文字列の長さ)の限界をキャパシティ(capacity; 許容量)といいます。
1つバッファの大きさ(キャパシティ)は基本的に変えられないので、キャパシティぎりぎりまで文字列が書かれているバッファに、「文字列を末尾に追加する」ことはできません。
HSPの文字列型の変数では、追加の書き込みができないとき、自動的に広くて新しい新居(バッファ)を持ってきて、そこに元々あった文字列と新しい文字列を書き込む、という手順を取ります。[脚注]
バッファを確保するのにかかる時間、元々あった文字列をコピーするのにかかる時間、が余分にかかるわけですね。
// 「バッファの移動」を起こす sdim s // HSPの文字列型のバッファの初期値は 64 バイト // s のバッファのメモリアドレス[脚注]を表示 mes varptr(s) // s にバッファを超える量の文字列を代入する repeat 7 s += "0123456789" loop mes strlen(s) //=> 70 // 再び、s のバッファのアドレスを表示 // さっきとは違う値になっていることがある mes varptr(s) stop
「バッファの移動」を避けるには、「キャパシティを超えてしまう」ことがないようにすれば十分です。
文字列を追加した後の長さが分かっている場合、初めからそれより多くのキャパシティを用意しておけば、バッファの移動は起こりません。
// 「バッファの移動」を起こさない sdim s, 70 + 1 // 十分な量のキャパシティを用意する // s のバッファのアドレスを表示 mes varptr(s) // s にバッファを超えない量の文字列を代入する repeat 7 s += "0123456789" loop mes strlen(s) //=> 70 // 再び、s のバッファのアドレスを表示 mes varptr(s) stop
実のところ、バッファの移動は行われる回数自体が少ないので、それほど時間的負荷にはならないことが多いです。[脚注]
さて、この「+=」という演算子は、さきほどの noteget と同じような問題を抱えています。
「+=」を行うたびに「文字列の最後尾を探す」[脚注]という処理を何度も行うことになるのです。
そこで、これまたさきほどの getstr のように、文字列上の位置をスクリプト側で指定することができる命令、poke を使うことで高速化できます。[脚注]
ただし、poke には変数のバッファを自動で拡張する機能がないため、エラー[脚注]を起こさないためには、自前でキャパシティを管理する必要があります。
// ちょっと賢い、文字列の追加書き込み // 書き込みたい文字列 (横着のため例が良くない) s = "a", "bc", "d" // バッファ sdim buf // 書き込み処理 len = 0 // buf にある文字列の長さ capa = 64 // キャパシティ repeat length(s) // 追加する文字列の長さを先に調べておく lenToAppend = strlen(s(cnt)) // もしキャパシティを超えてしまうなら、バッファを拡張する if ( len + lenToAppend >= capa ) { capa = (len + lenToAppend + 1) * 2 // 倍以上に拡張しておく memexpand buf, capa } // 書き込みを行う poke buf, len, s(cnt) len += lenToAppend loop mes buf mes "len = " + len mes "capa = " + capa stop
これは書くのがめんどくさいので、モジュール化しておきましょう。
参照：「MCLongString.as」
また、バッファ移動が絶対に起こらないような方法を思いついたので、ついでに試してみます。
キャパシティが足りなくなったら、新しいバッファに移動するのではなく、新しくバッファを持ってきて、それを「元々あった文字列の続き」だと思い込む、という方法です。[脚注]
参照：「MCRope.as」
// 文字列の連結にかかる時間を計測 #include "MCLongString.as" #include "MCRope.as" #define benchmark(%1) _lb = (%1) : benchmark_v _lb #define CountItems 5000 #define StringUnit "0123456789ABCDEF" sdim buf benchmark *LAppendVerAuto : mes "(+=)版 (自動拡張): " + refstr benchmark *LAppendVerManual : mes "(+=)版 (事前確保): " + refstr benchmark *LPokeVer : mes "poke版 :\t" + refstr benchmark *LLongStrVer : mes "LongStr版:\t" + refstr benchmark *LRopeVer : mes "Rope版 :\t" + refstr stop *LAppendVerAuto sdim buf repeat CountItems buf += StringUnit loop return *LAppendVerManual sdim buf, (CountItems * strlen(StringUnit)) + 1 repeat CountItems buf += StringUnit loop return *LPokeVer sdim buf len = 0 capa = 64 repeat CountItems lenToAppend = strlen(StringUnit) if (len + lenToAppend >= capa) { capa = (len + lenToAppend + 1) * 2 memexpand buf, capa } poke buf, len, StringUnit len += lenToAppend loop return *LLongStrVer LongStr_new ls repeat CountItems LongStr_add ls, StringUnit loop LongStr_tobuf ls, buf return *LRopeVer Rope_new rope repeat CountItems Rope_add rope, StringUnit loop Rope_tobuf rope, buf return #include "d3m.hsp" // for d3timer #module #deffunc benchmark_v var lb time = d3timer() gosub lb return "" + (d3timer() - time) + " ms" #global
僕のパソコンで試したところ、次のような結果でした[脚注]：
| 方法 | 時間 (ミリ秒) |
|---|---|
| (+=), 自動拡張 | 142 |
| (+=), 事前確保 | 141 |
| poke | 3 |
| LongStr | 7 |
| Rope | 13 |
多少の差はあると思いますが、「+=」を使う場合は「バッファの移動」が起こらなくても十分遅いことが分かります。
逆に、MCRope はバッファの移動を起こしませんが、小細工を要する分だけ MCLongString に劣ってしまっているようです。
poke はほぼ最速なものの、記述量が大きいというデメリットがあります。その兼ね合いを考えると、MCLongString を使うのは現実的といえるでしょう。
HSPはそもそも速い言語ではなく、速さを追求するのには全く向いていません。むしろスピードのことを考えること自体ナンセンス、という意見も聞きます。
しかし、具体的に計測するまでもなく、noteget や「+=」はかなり遅いため、処理量がある程度大きくなれば、体感できるほどの差が出てしまいます。
ツールやゲームなど、作品の形で発表するスクリプトなら、このくらいの大雑把な最適化はしておきたいところです。