arrays - Delphi - 检查元素是否在 TArray 中存在两次

Question

我有这个代码

var
arr: TArray<string>;
e1, e2, e3, e4: string;
begin

e1 := 'val1';
e2 := 'val2';
e3 := 'val3';
e4 := 'val4';

arr := TArray<string>.Create(e1, e2, e3, e4);

我现在需要检查上面的数组中是否存在 e1 到 e4 两次，最好的方法是什么？我还应该跳过检查任何具有空值的元素。

另外请告知我是否应该手动释放这个数组

谢谢

Answer 1

为了玩算法的乐趣；如果原始数组足够大，可以使天真 O(n^2)算法不切实际，并且由于 OP 使用的是具有泛型的 Delphi 版本，我建议使用 TDictionary<string, integer>跟踪所有字符串而不排序，并识别重复项。

由于多种原因，这将是有效的:

• TDictionary 提供恒定时间插入，几乎是 O(n) .我们从一开始就知道数组的大小，所以我们可以使用 TDictionary从来没有种植过它。这使得整个算法 O(n) .
• 由于字符串已经在一个数组中，并且 Delphi 字符串是引用计数的，将字符串放入数组并不会真正复制字符串!
• 使用这个算法，数组只被遍历一次。

代码:

type
  TZeroWidthRecord = record
  end;

function FindFirstDuplicate(const ArrayOfString: array of string): Integer;
var Dict: TDictionary<string, TZeroWidthRecord>;
    i: Integer;
    ZW: TZeroWidthRecord;
begin
  Dict := TDictionary<string, TZeroWidthRecord>.Create(Length(ArrayOfString));
  try
    for i:=0 to High(ArrayOfString) do
      try
        Dict.Add(ArrayOfString[i], ZW);
      except on E:Exception do
        Exit(i);
      end;
  finally Dict.Free;
  end;
  // No duplicates found:
  Result := -1;
end;

---

为了回答 David 的评论，我制作了一个简短的测试程序来比较这个 TDictionary基于算法到sort-and-search算法。我创建了随机字符串数组，然后尝试找到第一个重复项。我的数组不包含重复项，如果有重复项，则 TDictionary 的运行时间将与平均首次命中重复项成正比。例如，如果平均而言 TDictionary 会在数组中间找到重复项，那么 TDict 算法的平均运行时间将为一半。基于排序的算法需要对整个数组进行排序，而排序是最耗时的。

与排序和基于字典的算法一样，需要使用真实 数据进行测试。例如，如果我在 OP 的问题中使用短字符串进行了测试，则 TDict 和排序之间不会存在竞争:即使对于微不足道的长度数组，Dict 也会更快。但是当平均字符串长度增加时，基于排序的算法开始变得更好；但话又说回来，这取决于字符串:例如，如果大多数字符串共享一个长前缀，那么排序算法中的“比较”阶段将花费更长的时间，从而再次使 TDictionary 看起来更好!

测试表1，无重复

*==========*===========================*
|          | Number of strings         |
| Avg str  | in the Array for          |
| length   | TDictionary to be faster  |
*======================================*
| 7        | 33                        |
| 10       | 73                        |
| 13       | 73                        |
| 16       | 163                       |
| 19       | 163                       |
| 22       | 366                       |
| 25       | 366                       |
| 28       | 549                       |
| 37       | 2776                      |
| 40       | 2776                      |
| 43       | 2776                      |
| 46       | 4164                      |
| 49       | 9369                      |
| 52       | 9369                      |
| 55       | 9369                      |
| 58       | 21079                     |
*==========*===========================*

测试表2，在数组的1/2处复制

如果恰好在数组的中间找到第一个重复项，这将是结果。请注意平均字符串长度 58 的巨大差异:

*==========*===========================*
|          | Number of strings         |
| Avg str  | in the Array for          |
| length   | TDictionary to be faster  |
*======================================*
| 30       | 109                       |
| 33       | 163                       |
| 36       | 163                       |
| 58       | 366                       |
*==========*===========================*

测试表 3，在 1/4 处重复

如果在数组的 1/4 左右找到第一个重复项，就会发生这种情况:

*==========*===========================*
|          | Number of strings         |
| Avg str  | in the Array for          |
| length   | TDictionary to be faster  |
*======================================*
| 29       | 73                        |
| 32       | 73                        |
| 38       | 73                        |
| 57       | 109                       |
*==========*===========================*

这是测试应用程序:http://pastebin.com/vDznwKtZ