文字列の置換 †
考え方はこんな感じです。あとは実装するだけ。
サンプルとなる文字列sを"aaaBBaaBBaBBBBaaa"、対象となる文字列tを"BB"、置換する文字列rを"XYZ"とする。
サンプル文字列sの先頭から末尾に向かって順次、対象文字列tを検索し、置換する位置を求める。
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | t | B | B | | | | | | | | | | | | | | | | |
|---|
| s | a | a | a | B | B | a | a | B | B | a | B | B | B | B | a | a | a | |
|---|
|
マッチしないので検索を進める。
は検索開始インデックス。
|
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | t | | | B | B | | | | | | | | | | | | | | |
|---|
| s | a | a | a | B | B | a | a | B | B | a | B | B | B | B | a | a | a | |
|---|
|
マッチしないので検索を進める。
|
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | t | | | | B | B | | | | | | | | | | | | | |
|---|
| s | a | a | a | B
X | B
Y | a
Z | a | B | B | a | B | B | B | B | a | a | a | |
|---|
|
インデックス3でマッチしたのでこの位置に"XYZ"を置き換えればいいのだが・・・
このまま置き換えてしまうとインデックス5の"a"が潰れてしまう。
よって「対象文字列 < 置換文字列」の場合は作業バッファが必要となる。
はマッチした文字列の先頭インデックス。
|
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | t | | | | B | B | | | | | | | | | | | | | |
|---|
| s | a | a | a | B | B | a | a | B | B | a | B | B | B | B | a | a | a | |
|---|
| buf | a | a | a | X | Y | Z | | | | | | | | | | | | |
|---|
|
作業バッファbufを用意して置換を行う。
- 検索開始インデックスからマッチした位置までの文字列をバッファにコピーする。
はコピーした文字列。
- その後ろに置換文字列をくっつける。
は連結した置換文字列。
|
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | t | | | | | | B | B | | | | | | | | | | | |
|---|
| s | a | a | a | B | B | a | a | B | B | a | B | B | B | B | a | a | a | |
|---|
| buf | a | a | a | X | Y | Z | | | | | | | | | | | | |
|---|
|
検索を再開する。
マッチしないので検索を進める。
は検索開始位置。
は前回マッチした位置。
|
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | t | | | | | | | | B | B | | | | | | | | | |
|---|
| s | a | a | a | B | B | a | a | B | B | a | B | B | B | B | a | a | a | |
|---|
| buf | a | a | a | X | Y | Z | a | a | X | Y | Z | | | | | | | |
|---|
|
インデックス7でマッチしたので置換を行う。
は新たにマッチした位置。
- 検索開始インデックスからマッチした位置までの文字列をバッファにコピーする。
はコピーした文字列。
- その後ろに置換文字列をくっつける。
は連結した置換文字列。
以下同様に検索をし、マッチしたら置換を繰り返す。
|
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | t | | | | | | | | | | | B | B | | | | | | |
|---|
| s | a | a | a | B | B | a | a | B | B | a | B | B | B | B | a | a | a | |
|---|
| buf | a | a | a | X | Y | Z | a | a | X | Y | Z | a | X | Y | Z | | | |
|---|
|
|
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | t | | | | | | | | | | | | | B | B | | | | |
|---|
| s | a | a | a | B | B | a | a | B | B | a | B | B | B | B | a | a | a | |
|---|
| buf | a | a | a | X | Y | Z | a | a | X | Y | Z | a | X | Y | Z | X | Y | Z |
|---|
|
|
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | t | | | | | | | | | | | | | | | B | B | | |
|---|
| s | a | a | a | B | B | a | a | B | B | a | B | B | B | B | a | a | a | |
|---|
| buf | a | a | a | X | Y | Z | a | a | X | Y | Z | a | X | Y | Z | X | Y | Z |
|---|
|
これ以上検索しても見つからないとき、最後の検索開始位置から終端までの文字列をコピーする。
がこの作業バッファbuf、現時点で確保した領域をフルにつかってこれ以上連結できません。
（都合上、表に合わせただけなんです。）
（自動確保が効けば問題なしです。）
よって「対象文字列 < 置換文字列」の場合、作業バッファは前もって大きめに確保しておかなければならない。
（大きめ、かつ最低限必要なサイズを求めることもできます。）
|
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | | t | | | | | | | | | | | | | | | B | B | | | | | | |
|---|
| s | a | a | a | B | B | a | a | B | B | a | B | B | B | B | a | a | a | | | | | |
|---|
| buf | a | a | a | X | Y | Z | a | a | X | Y | Z | a | X | Y | Z | X | Y | Z | a | a | a | |
|---|
|
これで全て置換し終えました。
|
作業バッファを使わずスライド法でやってみます。
スライド法というのは自分が勝手につけた名前で一般的ではないです。 -- kz3
上と同様にサンプルとなる文字列を"aaaBBaaBBaBBBBaaa"、対象となる文字列を"BB"、置換する文字列を"XYZ"とする。
まず、"BB"を区切りとして"aaaBBaaBBaBBBBaaa"をSplitにかけると"aaa"、"aa"、"a"、"(空白)"、"aaa"に分割される。
そして分割した文字列同士の間に"XYZ"を入れれば繋げれば簡単に文字列を置換できる。
Splitを利用した置換のサンプル
sreplace.hsp
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
32
33
|
-
|
|
|
|
|
|
!
| #module "srep_module"
#deffunc sreplace var out,str base,str rbase,str rout
sdim srep_array,512,1 srep_str==base split srep_str,rbase,srep_array if length(srep_array)>=2{
srep_str==srep_array(0)
repeat length(srep_array)-1,1
srep_str==srep_str+rout+srep_array(cnt)
loop
out == srep_str
}
return length(srep_array)-1
#global
a=="aaaBBaaBBaBBBBaaa"
sreplace b,a,"BB","XYZ"
mes b
mes ""+stat+"回置換しました"
|
- 自動確保が効くといっても頻繁に自動確保するケースが出てくると、自動確保のための時間が指数的に溜まってくるので、速度重視の場合はやっぱり最初に領域をがぼっと確保したほうがいいと思います。が果たしてこの言い分は本当なのだろうか。 -- kz3
- いろいろと大量の置換対象からのみなるテキスト（64byte*16*16 = 256Kbyte)でテストしてみたけど、検索する対象の文字列が多くなればなるだけ時間はかかりますね。あと演算子による連結はヌル文字を検索するという処理も含まれているからだと思う。連結位置を自己管理してmemcpyでメモリ間コピーすればちょっと早くなるかも？ -- kz3
- もしくはpokeでメモリ間コピー。 -- kz3
- 正確なベンチマーク速度は測っていませんが、段違いに速くなりました。自分でも驚きです。載せたいけどサイズ大きいんですよねぇ・・・＾＾； -- kz3
- これが例のブツです。プリプロセッサでスイッチします。実際のコードは下のほうです。汗。 -- kz3
- 例のブツにループ中の検索位置のカウンタ表示を追加しました。+=演算子による置換の際、カウンタが進むにつれ遅くなっていることが分かると思います。 -- kz3
- あ〜！GENKIさん、『置換さん』というのを作っていたんですね！ -- kz3
- ぐふふ（怪）さっそくreplace.txtのHotSoupProcessor?をHSPに置換しよう！ -- kz3
- ・・・。強制終了・・・。きっとクリップボードのデータが大き過ぎたんだな；； -- kz3
- ･･･。ルーターのADSLランプが異常点滅し、全く回復の兆しがみえないのでchkdskをかけたら直った・・・みたいです。(Aﾟｰﾟ； -- kz3
- やはり純粋にアドレス（のオフセット）とコピーサイズを直に指定するmemsetが３つの中で高速な印象です。
pokeの場合コピー元に指定した文字列変数のサイズを調べてからメモリ間コピーしますがループ中で呼ぶと何度もコピー元の文字列サイズを計算する（計算するのに対象の文字列の先頭からヌル文字までを検索します。）からmemcpyより遅くなるのだと思う。
memcpyは事前に一回計算するだけでループ中では一発で位置を指定しているから無駄がないということかな？ -- kz3
- kz3さんのアルゴリズムをまねて、自前で作ったスクリプトが動きません。 ハハハ -- hiroki?
- 見せてくださ〜い！☆_☆ -- kz3
- 送り方どうやるの？ -- hiroki?
- 上メニューに[添付]というのがあるのでそこから添付フォームを設定してファイルをアップロードできますよ〜。 -- kz3
- 上メニュー以外に下メニューアイコンの、「クリップ付き」アイコンが[添付]と同じです＾＾ -- kz3
- どうしてもオーバーフローになっちまう -- hiroki?
- 確認中〜＾＾ -- kz3
- なんか・・・while-wendのマクロ展開がおかしい？？？ -- kz3
- 分かった。40行目の次回の検索開始位置 index1+=moji2 これが間違っている。moji2じゃなくてmoji2の文字サイズですね〜 -- kz3
- ．．．．は．．恥ずかしい。 でもindex1+=moji2su に直してもオーバーフロー -- hiroki?
- : moji2su=strlen(moji2)と入れると動くけど変な結果だから、調べてみます -- hiroki?
- 分かった。index1とmutchを比較する意味がない。mutchはオフセットだが、index1はmoji1中の検索開始位置、およびpeekの読取位置ですね〜。 -- kz3
- でもpeekしたついでにindex1+ ってしてるんだけど．．．。 -- hiroki?
- index1は置換が進むにつれて増えていきますよね？でもmutchは検索開始位置から見つかった位置までのオフセットなので場合によっては、
index1 : mutch = 130 : 5
ということもあってこの場合、while index1 < mutchはループに入る前に偽りなので・・・ -- kz3
- index1からのスタートなのでmutchがindex1より小さいことはありえないんだけど。 -- hiroki?
- 偽りなので・・・検索開始から見つかった位置までの置換対象外の文字列がコピーされず、置換文字列だけを repeat moji3su ループで連結しているのでXYZXYZ...となる。 -- kz3
- ありえますよ〜〜〜〜！！おおいにありえます；；（どんなサンプル書こうかな） -- kz3
- 例えばこんな感じ。
1
2
3
4
5
6
7
8
9
10
11
|
| s = "abcdefghijklmn"
mutch = instr(s, index1, "e")
mes "index1 : mutch = " + index1 + " : " + mutch
mes strmid(s, index1, mutch)
index1 += mutch+1
mutch = instr(s, index1, "g")
mes "index1 : mutch = " + index1 + " : " + mutch
mes strmid(s, index1, mutch)
|
- みんな最初は間違えるinstr。検索文字中の探した文字列の「絶対位置」ではなくて、検索開始位置からどれだけ離れた位置に見つかったという「オフセット値」なんです。 -- kz3
- 初めてスタート位置からの文字数だとわかりました。 repeat mutch に変えると動きました。 ごめんなさい。 添付します。 -- hiroki?
- いやーー プログラミングって奥が深いしたのしいですね。 -- hiroki?
- やったねｂ＾−＾ -- kz3
- 更新ってどうするんですか -- hiroki?
- 同一ファイルの添付は元を削除しないといけないので、下にある添付ファイルリストの対象ファイルの[詳細]をクリック後に削除を選択できます＾＾ -- kz3
- できました。 あーーー疲れた。 -- hiroki?
- お疲れ様です・・・では恒例（？）「hsp3」64*16*16*16byte->「HotSoupProcessor3」置換速度テスト。爆。 -- kz3
- ０で除算したって怒られた。 すいません出かけます 結果は後ほど -- hiroki?
- 急いでいたので、変数直してなかった。 うまくいきました。 添付します。 では。 -- hiroki?
- v3try_strreplace1b.hspにベンチマークテストのためのタイマー表示を追加しました。こちらをどうぞ。旧バージョンはサイズが大きい（これもだけど）ので削除しました・・・。&ref(): File not found: "v3try_strreplace2b.hsp" at page "String/置換"; -- kz3
- テスト中にマウス移動とか他アプリの処理によって時間は変わってきます。pokeの方がmemcpyより早いという場合もありました＾＾； -- kz3
- なんかpeek-pokeの方が早いんですけど！！！´ﾛ` -- kz3
- （いやいやそんなバカな・・・ﾜﾅﾜﾅ）微妙に早かったり遅かったり。orz
インデックス動かすのに+=で加算するよりインクリメントの方が早いということかな・・・ﾜﾅﾜﾅ
結構文字列置換というベターな話題でも盛り上がりますね＾＾；（僕だけか） -- kz3
- でも、いろんなアルゴリズムがありますよね。 僕なんか速度より簡単な方法を取ってしまいます。 -- hiroki?
- 基本はどれも『追いかけっこ』ですね＾＾ -- kz3
- 勝手に追加してしまいましたが構いませんよね？ 最近追加されたSplitを使った置換、書いておきます。 アルファ版って書いてあるのは中身じゃなくて説明の方です。 -- Alkw_lzy
