改行コードを変換する関数(超高速文字列処理)
|
| 55 |
HighSpeedStringConvertCRLF |
動作確認 |
Delphi2007 |
更新日 |
2008/01/30(水) |
改行コードがCRLF,CR,LFのテキストを
CRLFに変換するのはVCL標準で AdjustLineBreakes という関数があります。
(D6からクロスプラットホーム向けに
LFのみの改行コードにも変換できるようになっています)
でも、Macで使われるCRのみの改行コード変換には使えないので
どんな改行コードのテキストでも
CRLF,CR,LF の改行コードに変換してしまう関数を作りました。
その際に文字列を扱う上で高速化する手法が
非常に勉強になりましたのでまとめておきます。
※2chで教えてもらいました。ありがとう名無しのみなさん。
仕様としては
・改行コードをCRLF,CRのみ,LFのみの形式の文字列にして出力する
・LFCRというコードが出てきたら一つの改行コードとして判断する
・文字列中に CR,LF,CRLF,LFCR が混在していても改行コードをそろえる
こんな感じです。
まずは eXtreme Programming (=XP)のテストコードです。
XPではテストを先に書く事が推奨されます。
これで文字列変換の細かな仕様が確認できます。
────────────────────
type
TTextLineBreakStyleMultiPlatform = (tlbsmpCRLF, tlbsmpCR, tlbsmpLF);
//CRLF:Windows LF:Unix/Linux CR:Mac
//XPテスト
procedure Check(A, B: String);
begin
if not(A = B) then
begin
raise Exception.Create('エラーです ' + A + ':' + B);
end;
end;
procedure testChangeLineBreakes;
//総当りする関数
procedure CheckFunc(Source, CRLFResult, CRResult, LFResult: String);
begin
Check(CRLFResult, ChangeLineBreakes(Source, tlbsmpCRLF));
Check(CRResult , ChangeLineBreakes(Source, tlbsmpCR));
Check(LFResult , ChangeLineBreakes(Source, tlbsmpLF));
Check(CRResult , ChangeLineBreakes(CRLFResult, tlbsmpCR));
Check(LFResult , ChangeLineBreakes(CRLFResult, tlbsmpLF));
Check(CRLFResult, ChangeLineBreakes(CRResult , tlbsmpCRLF));
Check(LFResult , ChangeLineBreakes(CRResult , tlbsmpLF));
Check(CRLFResult, ChangeLineBreakes(LFResult , tlbsmpCRLF));
Check(CRResult , ChangeLineBreakes(LFResult , tlbsmpCR));
end;
begin
//普通に変換
CheckFunc(#10#13+'あいう'+#10#13+'えお'+#10#13,
#13#10+'あいう'+#13#10+'えお'+#13#10,
#13 +'あいう'+#13 +'えお'+#13,
#10 +'あいう'+#10 +'えお'+#10);
//混在
CheckFunc(#13#10+'123'+#10#13+'ABC'+#13 +'あいう'+#10 ,
#13#10+'123'+#13#10+'ABC'+#13#10+'あいう'+#13#10,
#13 +'123'+#13 +'ABC'+#13 +'あいう'+#13 ,
#10 +'123'+#10 +'ABC'+#10 +'あいう'+#10 );
//連続
CheckFunc(#10#13#10#13+'ABC'+#10#13#10#13+'あいう'+#10#13#10#13,
#13#10#13#10+'ABC'+#13#10#13#10+'あいう'+#13#10#13#10,
#13#13 +'ABC'+#13#13 +'あいう'+#13#13 ,
#10#10 +'ABC'+#10#10 +'あいう'+#10#10 );
//混在して連続
CheckFunc(#10#13#13 +'123'+#13#13#10 +'ABC'+#10#10#13 ,
#13#10#13#10+'123'+#13#10#13#10+'ABC'+#13#10#13#10,
#13#13 +'123'+#13#13 +'ABC'+#13#13 ,
#10#10 +'123'+#10#10 +'ABC'+#10#10 );
CheckFunc(#10#13#13 +'123'+#13#10#13 +'あいう'+#10#13#10 ,
#13#10#13#10+'123'+#13#10#13#10+'あいう'+#13#10#13#10,
#13#13 +'123'+#13#13 +'あいう'+#13#13 ,
#10#10 +'123'+#10#10 +'あいう'+#10#10 );
//改行数のチェック
CheckFunc(#10#13#10#13+
'ABC'+#10#13#10#13#10#13+
'123'+#10#13#10#13#10#13#10#13+
'あいうえ'+#10#13#10#13#10#13#10#13#10#13,
#13#10#13#10+
'ABC'+#13#10#13#10#13#10+
'123'+#13#10#13#10#13#10#13#10+
'あいうえ'+#13#10#13#10#13#10#13#10#13#10,
#13#13 +
'ABC'+#13#13#13 +
'123'+#13#13#13#13 +
'あいうえ'+#13#13#13#13#13 ,
#10#10 +
'ABC'+#10#10#10 +
'123'+#10#10#10#10 +
'あいうえ'+#10#10#10#10#10 );
end;
────────────────────
このテストコードを通過する ChangeLineBreakes 関数なら
実装はどんなものでもよいとします。
これで心おきなくリファクタリングできるわけです。
始めは全く高速化など考えずにコーディングしてみました。
AdjustLineBreakesを行って
文字列をCRLFに変換してからCRだけかLFだけを削除するコードです。
────────────────────↓相当遅いコード
function ChangeLineBreakes(const S: String; Style: TTextLineBreakStyleMultiPlatform): String;
const
CR: Char = #$D; //#13
LF: Char = #$A; //#10
//改行コードを削除します
//LineBreakesには#13か#10を指定
function DeleteCRLF(S: string; LineBreakes: Char): string;
var
Id: Integer;
begin
while True do begin
Id := AnsiPos(LineBreakes, S);
if Id = 0 then break;
Delete(S, Id, 1)
end;
Result := S;
end;
//改行コードがLFCRになっている場合CRLFに変換するコード
//この関数はまあまあ高速だと思います。
function LFCRConvertCRLF(S: String): String;
var
Id: Integer;
i: Integer;
begin
//↓単独でLFCRが存在するときだけCRLFに変換する
// (CRLFCRLFの時LFCRを変換されては困る)
if ( S[1]= LF ) and
( S[2]= CR ) then
begin
S[1] := CR;
S[2] := LF;
end;
for i := 2 to Length(S)-2 do
begin
if ( S[i-1]<>CR ) and
( S[i ]= LF ) and
( S[i+1]= CR ) then
begin
S[i ] := CR;
S[i+1] := LF;
end;
end;
i := Length(S) -1;
if ( S[i-1]<>CR ) and
( S[i ]= LF ) and
( S[i+1]= CR ) then
begin
S[i ] := CR;
S[i+1] := LF;
end;
Result := S;
end;
begin
Result := LFCRConvertCRLF(S);
Result := AdjustLineBreaks(Result);
case Style of
tlbsmpCRLF:
Result := Result;
tlbsmpLF:
Result := DeleteCRLF(Result, CR);
tlbsmpCR:
Result := DeleteCRLF(Result, LF);
else
Assert(False, '');
end;
end;
────────────────────↑相当遅いコード
AdjustLineBreaksはLFCRの改行コードを二つの改行と
認識してしまうので先にLFCRをCRLFに変換する処理をいれました。
テストは通過するのですが、とりあえずこのやり方は動作があまりにも遅く
数百KBのテキストを変換するのに、待ち時間がかなりあるので困りました。
文字列に対して1文字削除処理や
新しい文字列を定義してコピーしたりすると
その都度メモリが確保されて遅くなっている
ということがわかりまして、
それを改善して高速化するために
戻り値の文字列に対して
最初に一度SetLengthをして
元の文字列から改行コードを変換したものを
代入していき、処理が終わったら
最後に改めてSetLengthを行って文字列長を調整する
というコードに改善してみました。
────────────────────↓かなり速いコード
function ChangeLineBreakes(const S: String; Style: TTextLineBreakStyleMultiPlatform): String;
const
CR =#$D; //#13
LF =#$A; //#10
//改行がいくつあるかをカウントする
function CountCRLF(S: String): Integer;
var
i: Integer;
begin
Result := 0;
for i := 1 to Length(S)-1 do
begin
case S[i] of
CR: begin
//CRで次がLFじゃないなら
if not (S[i+1]=LF) then
Inc(Result);
end;
LF: begin
//LFで次がCRじゃないなら
if not (S[i+1]=CR) then
Inc(Result);
end;
else ;
end;
end; //for i
end;
var
ReadIndex, WriteIndex, i: Integer;
ReplaceStr: String;
label putCRLF;
begin
case Style of
tlbsmpCRLF: ReplaceStr := CR+LF;
tlbsmpCR : ReplaceStr := CR;
tlbsmpLF : ReplaceStr := LF;
end;
ReadIndex:=1;
WriteIndex:=1;
//現在の文字列長と最悪改行の数だけバイト数増えた分をメモリ確保
SetLength(Result,Length(S)+CountCRLF(S));
while ReadIndex<=Length(S) do begin
case S[ReadIndex] of
CR: begin
//見ているのが最後の文字じゃなくて
if not (ReadIndex=Length(S)) then
//次の文字がLFなら
if S[ReadIndex+1] =LF then inc(ReadIndex);
//ReadIndexで見る場所を一つ飛ばす
goto putCRLF;
end;
LF: begin
//見ているのが最後の文字じゃなくて
if not (ReadIndex=Length(S)) then
//次の文字がCRなら
if S[ReadIndex+1] =CR then inc(ReadIndex);
//ReadIndexで見る場所を一つ飛ばす
//Resultの文字を改行コードの所だけ入力する
putCRLF:
for i:=1 to Length(ReplaceStr) do Result[WriteIndex+i-1]:=ReplaceStr[i];
inc(WriteIndex,length(ReplaceStr));
end;
else begin
//CRでもLFでもない文字はそのまま移動
Result[WriteIndex]:=S[ReadIndex];inc(WriteIndex);
end;
end;
inc(ReadIndex);
end; //while
SetLength(Result,WriteIndex-1);
end;
────────────────────↑かなり速いコード
これでいきなり前のものと比べて1000倍近く高速化されました。
それから更に高速化を目指すことが可能です。
教えてもらった事ですが
ポイントとして3つあります。
１、Length(S) は const S と定義した変数を使ったとしても
関数に展開されるのでループ内で毎回Length(S)を行うと遅い。
一度、A:=Length(S)として変数に代入して
必要ならAの内容を見るべき。
２、文字列への Moji[ i ]:= という代入は内部で関数に置換されてしまう
高速化するなら文字列ではなく文字配列にするといい(ポインタでもいい)
type StrArray = array[1..$10] of char;
//この場合$10は無視されるので適当な宣言でよいらしい
var PStr: ^StrArray;
PStr := @S[1]; として準備しておく。
既存コードの S[ReadIndex] を PStr^[ReadIndex] と記述変更するべき
３、ReplaceStr[0]=CR; ReplaceStr[1]=LF;などの時
ループ内の改行コードを代入するコードの部分が
for i:=1 to Length(ReplaceStr) do Result[WriteIndex+i-1] := ReplaceStr[i];
ここで遅くなっている。
var ReplaceStr: array[0..1]of char; と宣言しなおして
1.Result[WriteIndex ] := ReplaceStr[0];
2.Result[WriteIndex+1] := ReplaceStr[1];
として改行コードを代入すると高速。
ReplaceStrがCR単独の時は[2.]の部分は無駄なコピーだけど
比較して禁止するにもコードが必要なので比較コードも書かない。
ループ中に最終文字列かどうかをチェックする
条件判断コードも取り除く工夫をして
上記を踏まえてより高速化を行ってみました。
これで先ほどのコードより3倍ほど高速化されます。
────────────────────↓ものすごく速いコード
{-------------------------------
//文字列の改行コードをそろえます
機能: 改行コードを
WinCRLF形式 MacCR形式 UnixLF形式
で相互変換します
引数説明: S: 元の文字列
Style: 変換する形式指定
戻り値: 変換された文字列
備考:
履歴: 2002/03/16
//------------------------------}
function ChangeLineBreakes(const S: String; Style: TTextLineBreakStyleMultiPlatform): String;
type StrArray = array[1..$10] of char;
const
CR = #$D; //#13
LF = #$A; //#10
//CRとLFがいくつあるかをカウントする
function CountCRLF(const S: String): Integer;
var
i: Integer;
PS: ^StrArray;
begin
Result := 0;
PS := @S[1];
for i := 1 to Length(S) do
begin
case PS^[i] of
CR: begin
Inc(Result);
end;
LF: begin
Inc(Result);
end;
else ;
end;
end; //for i
end;
var
ReadIndex, WriteIndex, SourceLength: Integer;
ReplaceStrLen: Integer;
ReplaceChar: array[0..1] of Char;
PResultStr, PSourceStr: ^StrArray;
begin
if S = '' then begin Result := ''; Exit; end;
SourceLength := Length(S);
case Style of
tlbsmpCRLF:
begin
ReplaceChar := CR+LF;
ReplaceStrLen := 2;
SetLength(Result, SourceLength+CountCRLF(S));
//↑最大で改行コードの数だけ
// 文字列長が増加する可能性があるので
// メモリを確保している
end;
tlbsmpCR:
begin
ReplaceChar := CR+#0;
ReplaceStrLen := 1;
SetLength(Result, SourceLength);
end;
tlbsmpLF:
begin
ReplaceChar := LF+#0;
ReplaceStrLen := 1;
SetLength(Result, SourceLength);
end;
else
ReplaceStrLen := 0;
Assert(False, '');
end;
PResultStr := @Result[1];
PSourceStr := @S[1];
ReadIndex := 1;
WriteIndex := 1;
while (ReadIndex <= SourceLength-1) do
begin
case PSourceStr^[ReadIndex] of
CR: begin
if PSourceStr^[ReadIndex+1]=LF then
Inc(ReadIndex);
//改行コード挿入コードへ
end;
LF: begin
if PSourceStr^[ReadIndex+1]=CR then
Inc(ReadIndex);
//改行コード挿入コードへ
end;
else
PResultStr^[WriteIndex] := PSourceStr^[ReadIndex];
Inc(WriteIndex);
Inc(ReadIndex);
Continue;
end; //case
//改行コード挿入
PResultStr^[WriteIndex ] := ReplaceChar[0];
PResultStr^[WriteIndex+1] := ReplaceChar[1];
inc(WriteIndex, ReplaceStrLen);
Inc(ReadIndex);
end; //while
if ReadIndex = SourceLength then
begin
case PSourceStr^[SourceLength] of
CR, LF: begin
//改行コード挿入
PResultStr^[WriteIndex ] := ReplaceChar[0];
PResultStr^[WriteIndex+1] := ReplaceChar[1];
Inc(WriteIndex, ReplaceStrLen);
end;
else
PResultStr^[WriteIndex] := PSourceStr^[SourceLength];
Inc(WriteIndex);
end; //case
end;
//SourceLength < ReadIndex の場合
//=文字の最後が???CRLFか???LFCRの場合
//何もしない
SetLength(Result,WriteIndex-1);
end;
//------------------------------
────────────────────↑ものすごく速いコード
最初に出てくるSetLengthの時に
SetLength(Result, SourceLength+CountCRLF(S));
このような事をしている所がありCountCRLFを行う事で
少し時間が余計にかかっています
これはメモリをなるべく少なく使うようにしているからなので単純に
SetLength(Result, SourceLength*2);
などとすると更に少し高速化するかもしれませんが
メモリを多く食い過ぎるので使わない方がいいでしょう。
これをより高速化しようとすると
アセンブラでチューニングするという方法もあるらしいですが
それでもここから10倍も高速化するという事は不可能なようです。
文字列処理を行う時に高速化が必要なら参考にしてください。
|