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

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 提供。非常感谢马塞洛。
我接受了 Svein 的回答，因为它直接回答了我的问题“如何让我的比较函数更快”和“没有必要让它更快”。
目前我实现了肮脏且快速实现的解决方案:当我有不到 200 个文件时，我使用我的慢速代码来检查重复项。如果文件超过 200 个，我会使用 dwrbudr 的解决方案(速度太快了)，考虑到如果用户有这么多文件，那么顺序是无关紧要的(人脑无法跟踪这么多项目)。

我要感谢大家的想法，尤其是 Svein 揭示了真相:(Borland 的)视觉控制太慢了!

Answer 1

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

当您使用它时，请忘记 SameFile 函数。算法的改进将使您在那里取得的任何成就相形见绌。

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

您可以执行保序 O(n log(n)) 重复数据删除，如下所示:

1. 对列表的副本进行排序。
2. 识别重复的条目并将其复制到第三个列表以及它们的重复计数减一。
3. 根据您的原始版本向后遍历原始列表。
4. 在内部 (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 := ... 循环更有效，但考虑到重复项很少见，差异应该可以忽略不计。