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

A

Adnil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-25

• #1

const
MAXITEM = 1000;
NAMES: array[0..MAXITEM] of string = ('dffff','sssdffff'......);
VALUES: array[0..MAXITEM] of string = ('dffff1','sssdffff1'......);

现已有一sName变量，需要匹配每个Name得到对应的Value
通常这样做
for i := 0 to MAXITEM do
if sName = Names then
begin
result := values;
break;
end;

我发现这样效率比较低，如果把NAMES的定义改成
NAMES = 'dffff,sssdffff....' //每个item用逗号分隔
然后使用Pos(sName + ',', NAMES)可提高1/3左右的搜索效率，但接下来取得对应的
Value则成了一个问题。

请算法高手指点一二，尽可能增加运行速度，减少内存占用（虽然这两者是矛盾的）。

 

U

ugvanxk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #2

用tstringlist的 name＝value的形式，没用过，你试试

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #3

对阿，TStrings的IndexOfName()，Values[]，Names[]很不错，就是开销大一些，
你先看看它能不能符合你的条件

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #4

取value：（假设你的value也是以逗号分隔的一个字符串）

function GetNthValue(const Values: string
N: Integer): string;
var
Walker, LastPos: PChar;
i: Integer;
begin
if N = 1 then // 取第一个，直接取
begin
Result := Copy(Values, 1, Pos(',', Values) - 1);
Exit;
end
else
Result := '';

Walker := PChar(Values);
i := 1;
while i < N do
begin
LastPos := Walker;
Walker := StrScan(Walker, ',');
if Walker <> nil then
begin
Inc(Walker)
// 跳过 ','
Inc(i)
// 共跳过了 i - 1 个 ',' 即处于第 i 个 value
end
else
Exit;
end;
SetString(Result, LastPos, Walker - LastPos - 1);
end;

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #5

//TStrings的IndexOfName()，Values[]，Names[]
其内部实现和楼主原来的办法一样的，效率较低

 

张

张无忌

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #6

用KPM匹配算法还可以提高速度

 

A

Adnil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #7

tstringlist的就不用再提了，效率基本跟我写的一致，另外还要增加对象创建，内容填充，
对象销毁的开销，速度只会更慢。

beta兄的又增加O(N)的时间复杂度来进行搜索，合起来效率还是前面说的快。

 

A

Adnil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #8

张无忌，能详细说说吗？ KPM匹配算法应该只是字符串搜索的算法吧？ 我现在关注的是
如果将搜索和Name/Value匹配有效的结合起来。

 

张

张无忌

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #9

哈，你这不是哈希表的最合适应用吗？

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #10

哦，呵呵
不过要是你的数组中的数据是编译时候定下来的，那么可以这样：
Names 用一个逗号分隔的字符串存放，而 Values 用数组存放，那么到时候
从 Names 中找到序号的时候就可以直接通过这个索引去访问数组中的 Value
[]

 

张

张无忌

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #11

用beta的办法不错...

 

原

原野飞侠

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #12

然后使用Pos(sName + ',', NAMES)可提高1/3左右的搜索效率，但接下来取得对应的
如下不用循环取
Nam:=Copy(Names,Pos(sName + ',', NAMES)-1,Length(Names));
Nam:=Copy(Nam,1,Length(sName));

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #13

to 原野飞侠:
人家的 Name 和 Value 可不一定是一样长的哦

 

A

Adnil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #14

来自：beta, 时间：2003-3-27 11:04:00, ID：1714205
哦，呵呵
不过要是你的数组中的数据是编译时候定下来的，那么可以这样：
Names 用一个逗号分隔的字符串存放，而 Values 用数组存放，那么到时候
从 Names 中找到序号的时候就可以直接通过这个索引去访问数组中的 Value
[]

这样考虑过啊，呵呵，就是这个数组太大了一点，数组大小跟Length(Names)一样。


to 原野飞侠：要取对应的Value, Name已经有了，还要取干什么？

 

B

bbs-wqt

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #15

学习

 

B

beta

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #16

//就是这个数组太大了一点
你总得存那么多数据啊，跟用什么格式存放没有关系吧？：）
事实上我曾经为了追求速度单独写了一个工具将 10K 左右的二进制数据生成
字符串格式的 Delphi 代码，然后 Copy 过来作为数组。

看你的应用要求了，数组很大，还有呢？存取次数多吗？

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #17

那你直接把
NAMES = 'dffff,sssdffff....'
改为
NameValues = 'dffff dffff的值,sssdffff sssdffff的值,...'
前面的Names定长，后面是值，找到Name就得到了Value了。
Stringlist里面存储的结构并不是跟楼主说的一样，楼主是两个数组，Stringlist是一个
用=分割，比较的时候速度是比较慢。
但是如果我说的这种定长的Name应该就会快的多，
只是不知道楼主允不允许这个结构

据说Strscan还不如
function ScanStr(ToScan: PChar
Sign: Char): PChar;
begin
Result := nil;
if ToScan <> nil then
while (ToScan^ <> #0) do
begin
if ToScan^ = Sign then
begin
Result := ToScan;
break;
end;
inc(ToScan);
end;
end;
快，后者可以提高40%的效率，尽管Strscan是用汇编写的

 

A

Adnil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #18

存取次数多不是很多，所以不想做类似初始化这样的操作把东西都塞到某个“高效”容器中。

NAME_VALUES = 'Name1:Value1,Name2:Value2,.......';
这样的结构其实可以考虑
iPos := Pos(sName + ':', NAME_VALUES);
if iPos > 0 then
for i := iPos + Length(sName) to Length(NAME_VALUES) do
begin
if NAME_VALUES = ',' then break;
sValue := sValue + NAME_VALUES
//这里还能优化掉
end;

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #19

楼上：其实定长Name应该比用分隔符分割速度要快啊

 

原

原野飞侠

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-27

• #20

我靠，我真的没看清楚
那只能用循环了