|
Pascal で文字列を効率良く扱う（例：文字列を逆順にする）。
|
ＭＬの全体がコーディングの勉強ですが、[Delphi-ML:42129] から始まる一連のスレッド「文の逆」は、Pascal で文字列（文）を効率良く扱う様々なコーディングの例が示されています。いろいろな方法があることがわかりますね。勉強になります。
実装で気をつけるのは、２バイト文字と、CR/LF の順を入れ替えないようにしなければならないというところです。
(1) 何も考えないで作る
function StrReverse(s: string): string;
var i: Integer;
LeadBytes: set of Char;
begin
i:= 1;
Result:= '';
LeadBytes:= SysUtils.LeadBytes + [#13];
while i<=Length(s) do begin
if s[i] in LeadBytes then begin
Result:= Copy(s,i,2) + Result;
i:= i+2;
end else begin
Result:= Copy(s,i,1) + Result;
i:= i+1;
end;
end;
end;
この関数が、ループ中で何百回も一度に呼ばれるとは考えにくいので、実はこれで十分かもしれませんが、後学のために工夫の余地を考えてみることにしましょう。
(2) [Delphi-ML:42142] 基本的な形です。（ただし、処理速度を考慮しています。）
function StrReverse(const s: string): string;
var
i, L: integer;
begin
L := Length(s);
SetLength(result, L);
i := 1;
while i <= L do
begin
if (s[i] in SysUtils.LeadBytes) or
((s[i] = #13) and (S[i+1] = #10))
then
begin
result[L-i] := s[i];
result[L-i+1] := s[i+1];
Inc(i, 2);
end
else
begin
result[L-i+1] := s[i];
Inc(i);
end;
end;
end;
コード(1)も同じなんですが、実はこれデータによっては s[Length(s)+1] を参照してしまいます。不正な文字列の場合は無視するにしても、改行を常に #13#10 と仮定して(1)のように比較部分を単純化するか、i=Length(s) のときには s[i+1] を参照しないか、どちらかにしないと意味が無いです。
ま、それは置いといて、、、
文字列の生成回数を減らす（Copy 関数は値を返すのに string を生成する）
文字列の足し算の回数を減らす（足し算も内部で新しい文字列を作る）
関数の呼び出しを最小限にする（Length の値を L にキャッシュ）
i:=i+1 の代わりに Inc 関数を使う（C での ++ 演算子と同等）
引数に const をつける（これも文字列の生成を押さえられる）
などが高速化部分。効果が大きい順に並べてみました。今回の目的には後ろの３つはたいした違いは生みません。特に、Length 関数のコストはそれほど大きくないことは覚えておいても良いと思います。逆に文字列の連結は時間がかかるので注意。
(3) [Delphi-ML:42157] ポインタの使い方の見本のような例ですね。
function StrReverse(const s: string): string;
var
p, pn, pr: PChar;
begin
SetLength(Result, Length(s));
p := PChar(s);
pr := PChar(Result) + Length(s);
while p^ <> #0 do begin
if (p^ = #13) and ((p+1)^ = #10) then
pn := p + 2
else
pn := CharNext(p);
System.Move(p^, (pr-(pn-p))^, pn-p); Dec(pr, pn-p);
p := pn;
end;
end;
コード(2)から、さらに [ ] の使用を無くして高速化を図ったものです。Pascal の [ ] は C の [ ] に比べてかなり時間がかかります。CharNext という関数も覚えていてよさそうですね。でも高々２バイトの転送に System.Move を使うよりは、(2) のように SysUtils.LeadBytes を使って判定して１バイトずつ ^ で転送した方がずっと速いでしょう。
２バイト文字の判断で２バイト目が #0 でないことを確認しないと、不正なデータが与えられた時に、メモリを破壊してシステムをハングアップさせる危険性があります。p_end:=PStr(s)+Length(s); としておいて、while の比較を、p<=p_end とすればハングアップを防ぎつつさらに高速化にもなりますね。
(4) [Delphi-ML:42148] ポイントは再帰ですね。
function StrReverse(const s: string): string;
var
L: integer;
begin
result := '';
L := Length(s);
if L = 0 then
exit;
if IsDBCSLeadByte(Byte(s[1])) then
result := StrReverse(copy(s, 3, L-2)) + s[1] + s[2]
else
result := StrReverse(copy(s, 2, L-1)) + s[1];
end;
コードはすっきりしますが、速度的には(1)よりずっと悪いです。なにより、長〜い文字列を渡すと再帰が深くなりすぎて、スタックオーバーフローを起こしかねないので、この目的には使えません。えっと、この例だけ改行文字を考慮していないですね。
(5) [Delphi-ML:42155] WideStringを使う発想です。
function StrReverse(s: WideString): WideString;
const
WCharCR : WideChar = #$0d;
WCharLF : WideChar = #$0a;
var
i : Integer;
begin
SetLength(Result, Length(s));
for i:=1 to Length(s) do begin
if (s[i] = WCharCR) and (s[i+1] = WCharLF) then begin
s[i] := WCharLF; s[i+1] := WCharCR;
end;
Result[Length(s)-i+1] := s[i];
end;
end;
WideString を使うことで、２バイト文字を考えなくても良くなります。もし、改行文字が含まれないことが分かっていれば、if 文は必要無くなりますから、非常にすっきりしたコードになります。WideString <-> string の変換はキャストの必要無く自動で行われます。変換は時間がかかりますが、初めと終わりの２回だけなので、この場合には気にする必要は無いでしょう。美しいコードです。
(6) [Delphi-ML:42173] 文字列の両端から交換していこうというアイディア
function StrReverse(const s: string): string;
var
len, i : integer;
L, R : pchar;
tmp : char;
p : pchar;
begin
Result := s;
len := length(s); if len = 0 then exit ;
p := PChar(Result);
L := p; R := L + len - 1;
while L < R do
begin
if (L^ in Sysutils.LeadBytes) or
((L^ = #13) and ((L+1)^ = #10)) then
begin
tmp := L^; L^ := (L+1)^; (L+1)^ := tmp;
inc(L, 2);
end
else
inc(L);
end;
L := p; R := L + len - 1;
for i := 1 to (len div 2) do
begin
tmp := L^; L^ := R^; R^ := tmp;
inc(L); Dec(R);
end;
end;
うーん何やら複雑。改行文字や２バイト文字が無くて、なおかつ関数が
procedure StrReverse(var s: string): string;
のように、直接引数を書きかえるものなら、メリットはあるかもしれません。。。この場合には、ほぼ最後の for 文だけになってしまいます。
基本的に、ループの中で何度も繰り返し呼ばれるので無ければ、実行速度を求めて読みにくいコードを書くのは愚とされます。したがって、この問題に限って言えば、(1) や (5) のように分かりやすく書けるものがお勧めです。
ただし、実行効率を考慮しないといっても限度があり、(4) のように、長い文字列を渡すとスタックオーバーフローを起こすようなコードは、いかに見やすくても不適当でしょう。
あなたならどう書きますか？ アイデアある方はどんどん加筆して下さい。
|
|
