真正快速的功能来比较两个文件的名称(完整路径)

Question

我必须检查我是否在FileListBox中有重复的路径(FileListBox具有某种作业列表或播放列表的角色).使用Delphi的SameText,CompareStr,CompareText需要6秒.所以我带了我自己的比较功能,它(更快)但速度不够快.任何想法如何改进它？

function SameFile(CONST Path1, Path2: string): Boolean;
VAR i: Integer;
begin
 Result:= Length(Path1)= Length(Path2);                                         { if they have different lenghts then obviously are not the same file }
 if Result then
  for i:= Length(Path1) downto 1 DO                                             { start from the end because it is more likely to find the difference there }
   if Path1[i]<> Path2[i] then
    begin
     Result:= FALSE;
     Break;
    end;
end;

我这样使用它:

 for x:= JList.Count-1 downto 1 DO
  begin
   sMaster:= JList.Items[x];
   for y:= x-1 downto 0 DO
    if SameFile(sMaster, JList.Items[y]) then
     begin
      JList.Items.Delete (x); { REMOVE DUPLICATES }
      Break;
     end;
  end;

注意:重复的可能性很小,因此不经常调用Delete.此外,列表无法排序,因为项目是由用户添加的,有时订单可能很重要.

更新:
问题是我失去了代码的优势,因为它是Pascal.如果比较循环(Path1 [i] <> Path2 [i])将被优化以使用Borland的ASM代码,那将是很好的.

---

Delphi 7,Win XP 32位,测试完成了列表中的577项.从列表中删除项目不是问题,因为它很少发生.

---

结论

正如Svein Bringsli指出的那样,我的代码很慢,不是因为比较算法,而是因为TListBox.最佳解决方案由Marcelo Cantos提供.非常感谢Marcelo.
我接受了Svein的答案,因为它直接回答了我的问题"如何使我的比较功能更快","没有必要让它更快".
目前我实现了脏和快速实现的解决方案:当我有200个文件时,我使用慢速代码来检查重复项.如果有超过200个文件,我使用dwrbudr的解决方案(这很快),考虑到如果用户有这么多文件,那么顺序无关紧要(人脑无法跟踪这么多项目).

我要感谢大家的想法,特别是Svein揭露真相:(Borland的)视觉控制非常缓慢!

Answer 1

不要浪费时间优化汇编程序.您可以从O(n ²)到O(n log(n)) - 将时间缩短到毫秒 - 通过对列表进行排序,然后对重复项进行线性扫描.

当你在它时,忘记SameFile函数.算法改进将使您在那里实现的任何事情都相形见绌.

编辑:根据评论中的反馈...

您可以按如下方式执行保留订单的O(n log(n))重复数据删除:

1. 对列表的副本进行排序.
2. 识别复制的条目并将其复制到第三个列表,同时复制计数减一.
3. 按照原始版本向后移动原始列表.
4. 在inner(for y := ...)循环中,遍历复制列表.如果外部项匹配,则删除它,减少重复计数,如果计数达到零,则删除重复项.

这显然更复杂,但它仍然会快几个数量级,即使你做了可怕的脏事,比如将重复计数存储为字符串C:\path1\file1=2,并使用如下代码:

y := dupes.IndexOfName(sMaster);
if y <> -1 then
begin
    JList.Items.Delete(x);
    c := StrToInt(dupes.ValueFromIndex(y));
    if c > 1 then
        dupes.Values[sMaster] = IntToStr(c - 1);
    else
        dupes.Delete(y);
end;

旁注:二元斩比for y := ...循环更有效,但考虑到重复很少,差异应该可以忽略不计.

Answer 2

使用您的代码作为起点,我修改它以在搜索重复项之前获取列表的副本.时间从5,5秒到约0.5秒.

vSL := TStringList.Create;
try
  vSL.Assign(jList.Items);
  vSL.Sorted := true;
  for x:= vSL.Count-1 downto 1 DO
  begin
   sMaster:= vSL[x];
   for y:= x-1 downto 0 DO
    if SameFile(sMaster, vSL[y]) then
     begin
      vSL.Delete (x); { REMOVE DUPLICATES }
      jList.Items.Delete (x);
      Break;
     end;
  end;
finally
  vSL.Free;
end;

显然,这不是一个好方法,但它表明TFileListBox本身很慢.我不相信你可以通过优化比较功能获得很多.

为了演示这一点,我用以下内容替换了你的SameFile函数,但保留了其余的代码:

function SameFile(CONST Path1, Path2: string): Boolean;
VAR i: Integer;
begin
  Result := false; //Pretty darn fast code!!!
end;

时间从5,6秒到5.5秒.我不认为在那里获得更多:-)