字符串匹配的算法问题 (100分)

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #21

同意 shenloqi，定长 Name 会提高效率的，如果你的 Name 长度相差不大的话
(以免空间浪费)，一个乘法，一个寻址就搞定了。而且可以利用同样是线性的
内存映射进一步提高速度。

不过我不理解的是你嫌 Values 数组太大了，那么你怎么存放 Values？

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #22

哦，定长 Name 没有什么意义，定长 Value 才能提高效率：）

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #23

Value不知道能不能定长
定长Name的话，可以不要Pos了
如果两者都定长了，自然会很快了，就是似乎有一些……

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #24

//定长Name的话，可以不要Pos了
那你怎么找？？[]

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #25

我是说取Value和Name的时候就不用Pos了，并且可以用我提供的ScanStr来替代Pos的。

 

A

Adnil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #26

定长Name无意义，定长Value好主意！ 差不多准备接受答案了 ：）

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #27

强烈建议采用排序后的TStringList——它采用二分法查找，时间复杂度最小！

var
SL:TStringList;
procedure TForm1.Button1Click(Sender: TObject);
var
i,n,m:Integer;
Value:String;
TWord;
begin
T:=GetTickCount;
with SL do
for i:=1 to 10000 do
begin
n:=IndexOf(IntToStr(i));
if n>=0 then
begin
m:=Integer(Objects[n])
// original index is here
Value:=VALUES[m]
// Get Value !
end;
end;
Caption:=IntToStr(GetTickCount-T);
end;

procedure TForm1.FormCreate(Sender: TObject);
var
i:Integer;
begin
SL:=TStringList.Create;
SL.Sorted:=true
//Here *****************
for i:=1 to 10000 do
SL.AddObject(IntToStr(Random(100000)),TObject(i))
//将原始顺序信息存入Objects数组
Caption:=IntToStr(SL.Count)
//由于排除了重复值，实际的字符串数量要小一些...
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
SL.Free;
end;

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #28

分要到手了[]

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #29

我说的定长Name和Value的前提是把两个字符串合并为一个字符串，这样效率肯定会很高的。
在使用同一个字符串的前提下：
我觉得如果不能定长Value的时候，定长Name还是有意义的，用ScanStr找到分隔的PChar
然后直接取出Name来比较，而之后的Value也可以直接从Name的长度开始取得
如果不是Value定长，需要用两次ScanStr（很快），把返回PChar相减得到总长度，
如果定长了Value和Name就用beta的方法（乘）。

我知道beta他们的意思是使用两个字符串的，自然定长Value有用了。

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #30

creation-zy 兄，楼主说了，访问次数不多，那么你的 TStringList 的创建、添加、排序
的时间就。。。。。。

shenloqi 兄，明白你的意思，不过这样的话用 ScanStr 似乎没有必要，直接用 Pos 不是
更好？

 

张

张无忌

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #31

ScanStr效率显然要高一些

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #32

to:beta
Pos的效率应该不会比scanstr的效率高的，而且Pos返回的是整数，而ScanStr返回的是得到的
PChar，我觉得你下面要判断Name是否相同，当然是直接得到PChar的效率高，不知你以为呢？

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #33

那到是，多谢 shenloqi 兄指点：）

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #34

to:beta
你的心得(ExecuteRoutine)让我见识不少，很是佩服阿，希望今后多看到你的心得出现：）
to:Adnil
不知道你的程序应用于什么环境，要求这么严格啊？
最好能够测试一下Stringlist是不是真的很慢，我觉得要求不严格的情形下creation-zy的
方法倒是可行的？


另外如果Objects要存储String类型，可能比较麻烦，我是这么使用的，
不知道大家有没有更好的方法？
//保存引用计数，返回指向该字符串的指针
function RefString(const S: string): Pointer;
var
Local: string;
begin
Local := S
// 增加引用计数
Result := Pointer(Local)
// 保存指针
Pointer(Local) := nil
// 悬空指针，离开生存期时Delphi不再减少引用计数
end;

//释放由RefString引用的字符串（其实是减少引用计数，当计数为0，Delphi会释放它）
procedure ReleaseString(P: Pointer);
var
Local: string;
begin
Pointer(Local) := P;
// 离开生存期时Delphi会减少Local指向的String的引用计数
end;

var
P: Pointer;
begin
...
P := RefString('测试字符，保存在Objects[]里');
Strings.AddObject('测试字符', P);
...
end;

//调出保存在Strings.Objects[]里面的字符串
StrPas(PChar(Strings.Objects))

//清空字符串列表以及的Objects[]引用的字符串
procedure Clears(var ss:TStrings);
var
i: Integer;
begin
Assert(Assigned(ss));
for i := ss.Count - 1 downto 0 do
begin
ReleaseString(ss.Objects);
ss.Delete(i);
end;
end;

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #35

大富翁论坛的邮件通知是不是不起作用了？
我还以为我的信箱坏了呢，发了一封测试信才知道信箱好得很……

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #36

>>存取次数多不是很多
既然是这样，那么采用高效算法也就没有什么意义了。在程序中耗时小于10%的地方优化
没有什么效果的。楼主最开始的循环遍历每次耗时不会超过0.1ms吧，在“存取次数多不是
很多”的条件下，总耗时也不会超过1ms，就算你能够优化到原来耗时的1%，顶多只能提速
0.99ms而已，个人以为意义不大...

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #37

有跟creation-zy相同的想法：）

 

D

DarwinZhang

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #38

同意 creation-zy， 查找字符常用的也就三种办法，
顺序查找(规模<=4)，折半查找(4<规模<=128)，散列表查找((规模>128))。

要是搞着玩，我也可以出个主意：
NAMES = 'dffff,0,sssdffff,1, ....'
在字符后面跟上一个数字，然后pos以后就找后面的数字，StrToInt，呵呵。

另外：
to creation-zy兄：
应该是这样：
......
for i:=1 to 10000 do
SL.AddObject(IntToStr(Random(100000)),TObject(i))
//将原始顺序信息存入Objects数组
SL.Sorted:=true
//Here *****************
......
是插入排序和快速排序的区别呵，大约是笔误吧？
btw:只面试，不笔试，^_^，轻松了不少。 []

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #39

to shenloqi 兄：

访问 Objects 中的字符串时没有必要用 StrPas 调用，它其实也是直接返回的，
你用强制类型转换可以节省一个函数调用的开销（反正都是为了欺骗编译器）
ShowMessage(string(PChar(TheList.Objects)));
当然，其实对于需要 string 的地方基本都可以用 PChar 代替，所以这个转换
在很多时候也是没有必要的。

 

爱

爱元元的哥哥

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #40

用Hash，我以前写反黄软件，可以实现从50万个IP里查找到一个IP！