现在流行写心得， 俺也来一篇。 如何高效地操作字符串。 给初学者一点帮助。 （鲜花和板砖都欢迎）(0分)

S

soul

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #61

那么岂不是第三种方案会多pos很多长度？
为什么看上去效率还可以呢？
还是奇怪，难道查内存不耗时间。

 

A

Another_eYes

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #62

老哥， 第二种方法哪里用到pos啦？ 就是字符串从头到底一次循环呀。
查内存当然耗时间。 第一种方法对内存可不是只查一次呀（查找一次， 复制又一次， 且不论分配内存过程中还要自动复制一次， 再加上释放内存的消耗）。 而且是完全没必要的。

 

J

JohnSun2002

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #63

精彩[8D]

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #64

// 那么岂不是第三种方案会多pos很多长度？
呵呵，soul 啊，你想过没有，除了最后一次之外，每次都是在字符串结束之前找到匹配
的吧。在那些查找里面，虽然你传了个很大的长度(字符串负偏移)进去，但是人家根本
就没有抵达那个长度就找到匹配然后退出了啊。即使有浪费时间的地方，也只是最后一
次而已，可相对于前面那么多次查找……
所以虽然出了这个错误，效率仍然没有什么影响的：）

 

D

ddev

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #65

我曾经写过一个断词函数，第一次写的时候是：
function wordbrk(const s: string;
strings: TStrings;
const white_spac: string = ''): Longint;
这是一种比较通常的处理表达，担由于涉及到 TStrings 类，效率上来讲，
大量的复制操作可能对于长串会有很大的影响。后来改为：
function wordbrk(const s: string;
arr: array of longint;
const white_spac: string = ''): Longint;
也就是说：用一个数组来存放每行的断词个数（ASCII-DBCS 分别算作1和2个字节），这样
可以通过 s 的偏移+字符数来得到每行的串，但不久又发现，与其需要分配一个
动态数组，还不如直接在串本身上作文章，于是又改为：
function wordbrk(const s: PChar;
const white_spac: PChar = nil): PChar;
也就是说：返回结果为下一个断取位的偏移，这样调用例程本身是采用复制还是
其它什么操作，仅依赖于调用例程,而与 wordbrk 本身已经没有关系，wordbrk
函数本身的效率达到最好，如果函数需要连续获取，则只要将返回的串指针作为
wordbrk 的 s 实参就可以了。并且这个函数的通用性也最好（实际上，后来我
已经把它转换成 C 代码进入 DLL 了）。
三种处理都能够达到相同的处理目标，但从效率来讲，由于最后一种处理没有串
复制，没有不必要的内存分配，所以说效率较好。而从程序的代码简洁度来讲，
却又是第一个函数方式最好(Delphi 调用)，第二个函数对于断取字符计数比较
方便。
我举这个例子是说明：代码本身处理中存在的技术缺陷，是不能作为判断算法优
劣的依据，这仅仅是一个程序员的功底问题。典型的就是：
for (int i = 0;
i <= 1000;
i++)
for (int j = 0;
j <= 5;
j++)
...

这也可以解释为什么在 pascal/c 中允许 asm ，这仅仅是因为 asm 是基于指令
级的处理，要比一般的 pascal/c 代码少了许多冗余，直接以周期来衡量或改进
函数的运行效率了。这不能成为算法依据，因为即便是 asm ，也要有算法的本
身优化，没有合理的算法，asm 也帮不了忙。

 

王

王公子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #66

收藏

 

S

soul

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #67

beta：你已经超过我了。佩服。

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #68

ddev: 我理解你的意思，你是指应该顺序搜索法和 KMP 算法之间比较吧。
可那有必要吗？那是已经有定论的东西，需要大费周章来讨论吗？不。
现在我们的意思显然是在已经确定使用顺序搜索法的前提下，如何尽可
能的提高速度。难道这不应该吗？要是没有这样的关于具体实现的讨论，
就算你用 KMP 算法也不见得写出效率更高的代码。

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #69

soul 你太抬举我了，只是我闲工夫比较多，所以琢磨的更仔细一点而已：）
何况就算是，那也仅局限于这一个问题而已，其他方面呢？我还差很远啊！

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #70

不过话又说回来，ddev，您的那个 wordbrk 的函数的思想的确值得学习。
把决定权交给用户，的确是个好办法，因为用户说不定有更好的方法呢。
我前段时间看 DX 的时候也发现了该思想。有时间应该好好刷新一下了：）

 

D

dirk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #71

同意ddev，算法的效率应该是基于同一个级别的，如果抛开这一点，大家都用汇编得了[8D]，
拿飞机和自行车比较本身就是很可笑的，就像拿泰森和我比较谁拳击更厉害一样，显然是泰森，
应该那泰森和刘易斯去比较才对。
--个人看法，鲜花和板砖都不欢迎，呵呵呵……[8D][8D][8D]

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #72

dirk 请注意看我后面的回复（ID 为 1429192）。
为什么拿 泰森 跟 我 比？因为有很多人需要找打手的时候不是找泰森，而是来找我。
明白我的意思吗？

 

D

dirk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #73

beta，我觉得你的1429192只理解了ddev的一层意思，ddev的本意是：
代码本身处理中存在的技术缺陷，是不能作为判断算法优劣的依据，这仅仅是一个程序员的功底问题。
难道你还不明白吗？即便一种高效的算法，如果在其中加入大量无效的代码，也会使其执行效率
比普通的算法还要低，第一个函数的“技术缺陷”是用了串拷贝，所以：
来自：ddev, 时间：2002-11-13 0:08:00, ID：1428410
作者提供的算法大有问题：
Source := copy(Source, pos(SubStr, Source)+Length(SubStr), $7FFFFFFF);
与
if (Source=SubStr[1])
and CompareMem(@(Source), Pointer(SubStr), len1) then

是所谓效率的关键地方，第一个函数用了串拷贝，而第二个函数直接采用 PChar
串比较，无论从空间还是时间，都已经不是在同一个级别上作比较。因此效率的
说法是不存在的。
我认为ddev说的没有错。

 

一

一个过客

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #74

你们争论的就是“选择正确的函数”是否算是“算法”吗？

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #75

// 不能作为判断算法优劣的依据。。。难道你还不明白吗？
我当然明白，不过我认为理解错误的仍是您和 ddev，难道我们前面一直在讨论“算法”
的优劣吗？还是在讨论“方法”的好坏？
我那个回复里面已经说的很清楚了，我们已经地选择了一个算法，现在研究实现该算法的
更好的方法。并没有因此而贬低其他的算法，也没有必要那样去做！
// 即便一种高效的算法，如果在其中加入大量无效的代码，也会使其执行效率
// 比普通的算法还要低
关键是现在有很多人像这样用，就算是让您用更好的算法，要是您加入大量无效的代码，
您的效率能高的起来吗？贴主的意思就是要告诉大家避免这种错误。这样看来，是您们不
明白，还是我们不明白？
呵呵，Another_eYes，现在你知道我发心得过后的感受了吧：）

 

A

Another_eYes

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #76

我更喜欢这篇现在这样的讨论。

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-13

• #77

呵呵，我是都喜欢。因为我喜欢抬杠：）

 

C

copy_paste

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-14

• #78

我测试了一下我写的，比如在这个贴子上我回复了多少次，2M文件，就是AddFile函数生成的，
花了0.2秒左右。[][]
我是跟CSDN的推荐了Another_eYes的这篇文章，有人(就是上面的BCB_FANS)提出有更好的方法
做这种事，就是BM(Boyer-Moore)，然后到Google找到了相关链接代码，然后转成这样。
**************************************************************************
// 原来的有错，删除再改成现在下面的情况，[]
const
MAX_CHAR = 256;
type
PByteArr = ^TByteArr;
TByteArr = array [0..MaxInt - 1] of Byte;
PCharArr = ^TCharArr;
TCharArr = array [0..MaxInt - 1] of Char;
function CountSubStr(const TextStr, SubStr: string;
IgnoreCase: Boolean = False): Integer;
var
Text, Sub: PByte;
I, J, CurrPos, SubLen, TextLen: Integer;
Buffer: array [0..MAX_CHAR - 1] of Integer;
begin
SubLen := Length(SubStr);
TextLen := Length(TextStr);
if SubLen > TextLen then
begin
Result := -1;
Exit;
end;

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;
Result := 0;
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
Inc(Result);
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 FindInFile(const FileName, Find: string;
IgnoreCase: Boolean = False): Integer;
var
Count: Integer;
Source: string;
begin
with TFileStream.Create(FileName, fmShareDenyNone)do
try
Count := Size;
SetLength(Source, Count);
ReadBuffer(Source[1], Count);
Result := CountSubStr(Source, Find);
SetLength(Source, 0);
finally
Free;
end;
end;

const
TEST_SIZE = 10024 * 1000;
procedure AddFile(FileName: string);
var
Buffer: Pointer;
FileSize, Count: Integer;
begin
with TFileStream.Create(FileName, fmOpenReadWrite)do
try
FileSize := Size;
Count := FileSize;
GetMem(Buffer, Count);
try
ReadBuffer(Buffer^, Count);
Inc(FileSize, Write(Buffer^, Count));
while TEST_SIZE > FileSizedo
Inc(FileSize, Write(Buffer^, Count));
finally
FreeMem(Buffer);
end;
finally
Free;
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
Count: Integer;
Start: Cardinal;
begin
if OpenDialog1.Execute then
begin
Start := GetTickCount;
Count := FindInFile(OpenDialog1.FileName, Edit1.Text);
Caption := Format('Find Count: %d, Time spend: %f', [Count, (GetTickCount - Start) / 1000]);
end;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
if OpenDialog1.Execute then
AddFile(OpenDialog1.Filename);
end;

 

C

copy_paste

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-14

• #79

我们也在灌水，Another_eYes还有各位大虾不妨来过来一灌。[][]
BCB:
http://expert.csdn.net/Expert/topic/1171/1171303.xml?temp=.8061182
Delphi:
http://expert.csdn.net/Expert/topic/1171/1171056.xml?temp=.6299097
[][]

 

C

copy_paste

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-14

• #80

发现丢人了，[!]，程序我只是随便测试了一下，感觉有Count返回来就以为正确了。
还有很多错，我上面写的程序中。随便找两Edit，输入后，再删掉一些，就读不正确了。
还在测试中。。。