两个字符串列表的比较的算法(50)

To:QQ在线你的方法我也试了,速度非常不理想.我又试了一下建两个表用inner jion 查询,s1为1万条,s2为30万条数据,结果只需要10秒钟,看来还是sql语句快.现在的问题是我把s2建一个表,s1我就不想建表了,因为s1经常变化,想直接在s2建的这个表中来inner jion要查询的身份证号的txt文件,可以吗?

你将你写的DoFilter代码贴来看看。

我测试那代码，S1有1W条，S2有30W条，如果S2全部包含S1里的数据，基本要30s或更久，如果S2只有几条，则不用0.5s这说明，这算法思路是对的，但最终显示耗时，要换另一种方法来显示，这个你就自己写吧。

function PosInFile(Str,FileName:string):integer; var Buffer:array[0..1023]of char; BufPtr,BufEnd:integer; F:File; Index:integer; Increment:integer; c:char; function NextChar:char; begin if BufPtr>=BufEnd then begin BlockRead(F,Buffer,1024,BufEnd); BufPtr := 0; Form1.ProgressBar1.Position := FilePos(F); Application.ProcessMessages; end; Result := Buffer[BufPtr]; Inc(BufPtr); end; begin Result := -1; AssignFile(F,FileName); Reset(F,1); Form1.ProgressBar1.Max := FileSize(F); BufPtr:=0; BufEnd:=0; Index := 0; Increment := 1; repeat c:=NextChar; if c=Str[Increment] then Inc(Increment) else begin Inc(Index,Increment); Increment := 1; end; if Increment=(Length(Str)+1) then begin Result := Index; Break; end; until BufEnd = 0; CloseFile(F); Form1.ProgressBar1.Position := 0;

再给你来一个，不支持中文：function FastPosNoCase( const aSourceString, aFindString : String; const aSourceLen, aFindLen, StartPos : integer ) : integer;Pascal// Remove by SunLujiang{var SourceLen : integer;begin SourceLen := aSourceLen; SourceLen := SourceLen - aFindLen; if (StartPos-1) > SourceLen then begin Result := 0; Exit; end; SourceLen := SourceLen - StartPos; SourceLen := SourceLen +2;}// Remove end asm push ESI push EDI push EBX // Add by SunLujiang Mov ECX, aSourceLen Mov EAX, aFindLen Sub ECX, EAX Jo @Result0 Mov EAX, StartPos Dec EAX Sub ECX, EAX Jo @Result0 Inc ECX Inc ECX // Add end mov EDI, aSourceString add EDI, StartPos Dec EDI mov ESI, aFindString // Remove by SunLujiang// mov ECX, SourceLen // Remove end Mov Al, [ESI] // Add by SunLujiang Cmp Al,97 Jb @NotLowerCase1 Cmp Al,122 Jnb @NotLowerCase1 // Add end // Make Al lowercase. and Al, $df // Add by SunLujiang @NotLowerCase1: // Add end @ScaSB: Mov Ah, [EDI] // Add by SunLujiang Cmp Ah,97 Jb @NotLowerCase2 Cmp Ah,122 Jnb @NotLowerCase2 // Add end // Make Ah lowercase. and Ah, $df // Add by SunLujiang @NotLowerCase2: // Add end cmp Ah,Al jne @NextChar @CompareStrings: mov EBX, aFindLen dec EBX //add by ShengQuanhu Jz @EndOfMatch //add end @CompareNext: mov Al, [ESI+EBX] mov Ah, [EDI+EBX] // Add by SunLujiang Cmp Al,97 Jb @NotLowerCase3 Cmp Al,122 Jnb @NotLowerCase3 // Add end // Make Al and Ah lowercase. and Al, $df // Add by SunLujiang @NotLowerCase3: Cmp Ah,97 Jb @NotLowerCase4 Cmp Ah,122 Jnb @NotLowerCase4 // Add end and Ah, $df // Add by SunLujiang @NotLowerCase4: // Add end cmp Al, Ah Jz @Matches Mov Al, [ESI] // Make Al lowercase. and Al, $df Jmp @NextChar @Matches: Dec EBX Jnz @CompareNext //add by Shengquanhu @EndOfMatch: //add end mov EAX, EDI sub EAX, aSourceString inc EAX mov Result, EAX jmp @TheEnd @NextChar: Inc EDI dec ECX jnz @ScaSB //add by SunLujiang @Result0: //add end mov Result,0 @TheEnd: pop EBX pop EDI pop ESI// Remove by SunLujiang// end;// Remove endend;

这个东西着眼点不同，会产生不同的讨论方向。比如说，这个功能是某个大型系统的一部分，那么使用导入到数据库，利用数据库查询手段获得结果就是比较合理的。而如果这是某个小型应用的一部分，完全不能或者根本不希望利用到数据库，那么利用大致可以接受的任意方法完成任务，也不失为一种解决办法。纯技术地讨论的话，首先会想到把问题分解成怎么样的数据结构。按照S2的情况，可以非常快地分离出“身份证”字段的内容：type TS2Rec = record NameCardOrd:string[18]; Other:string[238]; end;这个结构实际上定义了一块 256 字节大小的内存块，利用 Move 函数，可以快速地提取出S2前面的 18 个字节的“身份证”号码，至于 18 个字节后面的内容，实际上已经不需要关心，所以也不必考虑 238 字节是否可以放下。这时候再来看这个“身份证”号码的特征，假如直接使用前面讨论的哈希方法，存在一个很大的缺点，就是S1也是一个上万数量的列表，循环一遍也很费时。于是可以考虑分段，分段方式是把“身份证”的前6个字节分成2段，第一段4个数字，第二段2个数字，并把前面4个数字从字符串转换为真正的数字表示。这样处理后的结果，从S2分解出来的“身份证”就形成了以4个数字为前缀的数据：1234 01 1111111111111 2222222222222 02 1111111111111 2222222222222前面的4个是数字，那么当循环获取S1中每个号码做比较时，每取出一个，只要也拿前4个数字当做指标，设法直接跳到相对应的数据里再去做小循环就可以节省大量的循环次数。这时候，再考虑对余下的12位字符（18-6=12）加入哈希检索，整个比对算法就会快很多。

谁说Pos慢!Pos里面就是asm编的啊!另外:用指针把s2模拟为String就可以Pos啊!

Pos确实慢,Delphi自带的Pos没有写好.小雨哥的方法很不错,保存时如果能固定长度,循环时直接MOVE指针查找指定位置的数据就可以了.这样估计效率会比较高

切 太繁琐 我推荐个简单点的j:=s2.indexof(s1)j>=0 找到

2 zkktom:复杂问题简单化是写程序首要考虑问题，但也要把简单问题为什么要复杂化搞清楚。2 all:我觉得pos来处理这个问题已经没必要再考虑，使用循环不断Pos，已经先天速度搞慢了，只能换个思路。这个已经不是Pos慢不慢，快不快的问题，举个例子：1: for i := 0 to s1.count - 1 do2: if pos_func(s1, srcdata) > 0 then ... // find it第2步，每次pos_func需耗时: 0.1s, 则s1.count=1w, 需时1000s pos_func优化0.01s, 还是需要100s， 大家觉得pos_func还能优化到0.001s吗？ 请注意：srcdata=30W以上的行，最起码有7,8M的数据，光循环7,8M的数据都不止0.01s了。第二种循环21: for i := 0 to s2.count - 1 do [ s := s2.no; //取出s2的号码 22: if pos_func(s, s1text) > 0 then ... // find it ] s1比s2 text低一级别，但循环高一级别，跟上面差不多。不说了。小雨哥的方法，应该是二级或N级hash检索的方法了，我只是觉得二级以上的hash检索一般应用于100M或上G的数据处理。而楼主的问题看来不会超过50M 另：楼主的问题是检索出:s1中的某一条是否在s2中一条的内容中。 举例：s1 text:1234...s2 text1234,xxx,xx...则表明s1的1234在s2存在所以，我觉得小雨哥上面所说的检索方法的顺序有些不对，应该是将s1的数据进行hash处理，而不是处理s2的数据，数量级不同。

同意 QQ在线 的思考。另：QQ在线？不会就是专门发送“某某您已经中奖”的那位吧？-开个玩笑我的本意是这样想的：主要是先要减少循环，所以我思考可以采取分段的办法，把数据分布到各自有特征的地方去，为什么是6个数字呢，我想，身份证前4位是指出地区，5、6位指出的是地区中更小范围的位置，也就是说，前4位大概可以把30W的数据分成W级别（正态最佳状态下），后2位可以分解到千，这样就把循环的数量级降下来了，然后对之后的12位进行哈希。哈希是这样的，不仅是S2，S1也要采取相同的哈希才能检索匹配。因此是2者都是需要哈希的，只是哈希的时机各不相同而已。

tstringlist的text属性根本就是以#13#10分割的一个大字符串而已。你就把这个text赋给一个String STR， 用pos找到s1中字符串的位置 Integer x，根据这个x 在S2中找前后的#13#10 也就找到了S2中这个包含S1的String,就解决了。我觉得用这个技巧就行了，不用很复杂的算法，而且速度还行吧。

數據量大的時候已經不是 pos 可以解決的問題了~~~~~當數據量到達一個界限的時候，應該儘量將自己的思想向數據結構和算法的方面考慮。。。。