×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

  1. トップ
  2. HSP講座
  3. >ここ

文字列の扱い

大量の文字列データは処理に時間がかかるものです。
ここでは、速度的に“賢い”文字列操作の例をいくつか紹介します。

  1. 各行に対する処理
  2. 文字列を足す
  3. おわりに

各行に対する処理

「行ごとに区切られた文字列」というのはおそらく最も見慣れた文字列でしょう。
目にする機会が多いがゆえに、スクリプトからも使う機会も多くなります。
その需要に応じてか、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 や「+=」はかなり遅いため、処理量がある程度大きくなれば、体感できるほどの差が出てしまいます。
ツールやゲームなど、作品の形で発表するスクリプトなら、このくらいの大雑把な最適化はしておきたいところです。