如何高效地操作字符串（三）： 第二篇中涉及内容的源代码(0分)

  • 主题发起人 Another_eYes
  • 开始时间
Another_eYes: 记得搞定了过后给我一份哦：）谢谢
 
我大概用BM算法实现了一下，速度快了近10倍，我也不知是不是真的，给出代码。
我用了10M的文件，用了时间大概就是：0.14 seconds左右，所以大家看看。说不定有错，呵。
----------------------------------
const
MAX_CHAR = 256;
SizeInt = SizeOf(Integer);
type
PByteArr = ^TByteArr;
TByteArr = array [0..MaxInt - 1] of Byte;
PCharArr = ^TCharArr;
TCharArr = array [0..MaxInt - 1] of Char;
procedure FindSubStrPos(Stream: TMemoryStream;
const TextStr,
SubStr: string;
IgnoreCase: Boolean = False);
var
Text, Sub: PByte;
Buffer: array [0..MAX_CHAR - 1] of Integer;
I, J, Pos, CurrPos, SubLen, TextLen: Integer;
begin
Stream.Clear;
SubLen := Length(SubStr);
TextLen := Length(TextStr);
if SubLen > TextLen then
Exit;
Sub := @SubStr[1];
Text := @TextStr[1];
if IgnoreCase then
begin
GetMem(Sub, SubLen);
Move(SubStr[1], Sub^, SubLen);
Sub := PByte(StrUpper(PChar(Sub)));
end;

for I := 0 to MAX_CHAR - 1do
Buffer := SubLen;
for I := 0 to SubLen - 2do
Buffer[PByteArr(Sub)^] := SubLen - I - 1;
CurrPos := SubLen - 1;
try
while CurrPos < TextLendo
begin
I := CurrPos;
J := SubLen - 1;
while (J >= 0) and
((PByteArr(Text)^ = PByteArr(Sub)^[J]) or
(IgnoreCase and (UpCase(PCharArr(Text)^) = PCharArr(Sub)^[J])))do
begin
Dec(J);
Dec(I);
end;
if -1 = J then
begin
Pos := CurrPos - SubLen + 1;
Stream.WriteBuffer(Pos, SizeInt);
end;
if IgnoreCase then
Inc(CurrPos, Buffer[Byte(UpCase(PCharArr(Text)^[CurrPos]))])
else
Inc(CurrPos, Buffer[PByteArr(Text)^[CurrPos]]);
end;
finally
if IgnoreCase then
FreeMem(Sub);
end;
end;

function StringReplace(const S, OldPattern, NewPattern: string;
IgnoreCase: Boolean;
ReplaceCount: PInteger = nil): string;
var
R: PChar;
P: PCharArr;
PPos: PInteger;
Stream: TMemoryStream;
CurrPos, Count, RetLen, OldLen, NewLen, SourceLen: Integer;
begin
Stream := TMemoryStream.Create;
try
FindSubStrPos(Stream, S, OldPattern, IgnoreCase);
Count := Stream.Size div SizeInt;
if Assigned(ReplaceCount) then
ReplaceCount^ := Count;
if Count = 0 then
Exit;
P := @S[1];
PPos := Stream.Memory;
OldLen := Length(OldPattern);
NewLen := Length(NewPattern);
CurrPos := 0;
SourceLen := Length(S);
SetLength(Result, SourceLen - OldLen * Count + NewLen * Count);
R := @Result[1];
while Count > 0do
begin
RetLen := PPos^ - CurrPos;
if RetLen > 0 then
begin
Move(P^[CurrPos], R^, RetLen);
Inc(R, RetLen);
end;
if NewLen > 0 then
begin
Move(NewPattern[1], R^, NewLen);
Inc(R, NewLen);
end;
Inc(CurrPos, RetLen + OldLen);
Inc(PPos);
Dec(Count);
end;

if CurrPos <> SourceLen then
Move(P^[CurrPos], R^, SourceLen - CurrPos);
finally
Stream.Free;
end;
end;

function StringRepalceFromFile(const FileName, OldPattern,
NewPattern: string;
IgnoreCase: Boolean;
ReplaceCount: PInteger = nil): string;
var
Count: Integer;
Source: string;
begin
with TFileStream.Create(FileName, fmShareDenyNone)do
try
Count := Size;
SetLength(Source, Count);
ReadBuffer(Source[1], Count);
Result := StringReplace(Source, OldPattern, NewPattern,
IgnoreCase, ReplaceCount);
SetLength(Source, 0);
finally
Free;
end;
end;

procedure TForm1.Button3Click(Sender: TObject);
var
S: string;
Count: Integer;
Start: Cardinal;
begin
if not OpenDialog1.Execute then
Exit;
Count := 0;
Start := GetTickCount;
S := StringRepalceFromFile(OpenDialog1.FileName,
OldEdit.Text, NewEdit.Text, True, @Count);
Caption := Format('Replace Time: %f, Replace Count: %d',
[(GetTickCount - Start) / 1000, Count]);
{ 下面是将数据加载到Memo1中，时间比较长，如果不想加载到Memo中，请注解掉下面的}
Start := GetTickCount;
Memo1.Lines.begin
Update;
Memo1.Lines.Text := S;
Memo1.Lines.EndUpdate;
SetLength(S, 0);
Caption := Caption + Format(',Add to Memo Time: %f',
[(GetTickCount - Start) / 1000]);
end;

窗体很简单，一个Memo,两个Edit,一个OpenDialog外加一个Button。
我是按Another_eyes说的，第一找位置（FindSubStrPos），第二替代。
方法不同，我都是些流或指针操作，我对着汇编头就比较大，所以上面
的代码也就没仔细看了。
[:D][:D]
 
hehe,顶一下，有好久没有看到这样的帖子了。
eyes你还活着呀，现在在做什么呢？
 
这么靠后的帖子也让你翻出来了，厉害：）
 
不靠后呀，是11月发的呢，呵呵，
 
收藏！
 
踢一下
 
谢谢
 
:copy_paste 你好,
var
S, OldPattern, NewPattern: string;
Start, Count: Cardinal;
begin
OldPattern := 'a';
// OldEdit.Text;
NewPattern := 'b';
// NewEdit.Text;
Count := 0;
S := StringOfChar('a', $200000);
Start := GetTickCount;
StringReplace(S, OldPattern, NewPattern, false, @Count);
Caption := Caption + Format(',Add to Memo Time: %f',
[(GetTickCount - Start) / 1000]);
Error: Out of memory while expanding memory stream.
才 $200000 就不行了, 不要说 10M.
我的内存也不小啊. 128+256M的, 而且用的是Win98
 
樓主的其他幾篇都收藏了。
這篇以前怎麼沒發現。
 
我有一个关于Replace部分的想法, 用空间换时间:
1.新建开一块内存(保存结果),
SetLength(Result, Len(Source) + (Len(NewPattern) - Len(OldPattern)) * MatchCount);
2.然后
ResultPos := MatchPoses[0];
Move(Result[1], Source[1], ResultPos);
// 没有被替换的内容
Move(Result[ResultPos], NewPattern[1], NewPatternLen);
// 替换内容
如是重复.
最后释放 Source.
 
不过我用java实现想法的时候, 总是比jdk1.4的那个replaceAll慢了一倍.
谁愿意帮我看看为什么这么慢? 问题主要出在哪里?
public static String replaceString(String src, String strFrom, String strTo){
if (src == null) return null;
StringBuffer result = new StringBuffer();
int begin
= 0;
int end = 0;
while (begin
< src.length()){
begin
= src.indexOf(strFrom, begin
);
if (begin
>= 0){
result.append(src.substring(end, begin
));
result.append(strTo);
end = begin
+ strFrom.length();
begin
= end;
} else
{
if (end < src.length()) result.append(src.substring(end));
break;
}
}
return result.toString();
}
 
jdk很多函数使用了C＋＋来实现。你的效率当然比不上他的。
 
只是内部实现的差别? 我想应该是算法上的差异才会导致慢一倍.
 
好帖子，收藏
 
第四篇呢？不是说有第四篇 的吗？
 
您必须登录或注册才可回复。

Similar threads

I
Delphi 代码优化-字符串篇
回复
0
查看
760
import
I
I
如何用函数名字符串来调用函数？
回复
0
查看
647
import
I
I
一个检测本机网卡号（物理地址）的程序源码
回复
0
查看
595
import
I
3
生成大量的随机字符串，代码已贴出，但我觉得不够高效！(200)
回复
4
查看
660
32881
3
X
应部分网友要求，公开 myfunctions 单元，里面有很多有用的函数(0)
回复
10
查看
4K
yczjs
Y
顶部