2

我有这个代码

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两次最好的方法是什么？我也应该跳过检查任何元素是否为空值。

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

谢谢

4

4 回答 4

9

为了玩算法的乐趣；如果原始数组大到足以使天真的O(n^2)算法不切实际，并且由于 OP 使用的是具有泛型的 Delphi 版本，我建议使用 anTDictionary<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;

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

与基于排序和字典的算法一样，需要使用真实数据进行测试。例如，如果我在 OP 的问题中使用短字符串进行测试，TDict 和 sort 之间就不会有竞争：即使对于微不足道的长度数组，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

于 2013-01-25T16:23:59.827 回答
6

不需要释放动态数组。它们是托管类型，编译器确保当不再引用该对象时，该对象被销毁。

至于检测重复，你可以这样做：

function HasDuplicates(const arr: array of string): Boolean;
var
  i, j: Integer;
begin
  for i := 0 to high(arr) do
    if arr[i]<>'' then
      for j := i+1 to high(arr) do
        if arr[i]=arr[j] then
          exit(True);
  Result := False;
end;

我假设当您说“null”时，在字符串的上下文中您的意思是该字符串为空。

这是一个复杂度为 O(n^2) 的算法。如果数组很大，那是个坏消息。

如果您的数组是有序的，您可以使用 O(n) 算法进行测试。

function OrderedHasDuplicates(const arr: array of string): Boolean;
var
  i: Integer;
begin
  for i := 0 to high(arr)-1 do
    if arr[i]<>'' then
      if arr[i]=arr[i+1] then
        exit(True);
  Result := False;
end;

自然地，这些函数可以很容易地修改以识别哪个索引是重复的：

function IndexOfDuplicate(const arr: array of string): Integer;
var
  i: Integer;
begin
  for Result := 0 to high(arr) do
    if arr[Result]<>'' then
      for i := Result+1 to high(arr) do
        if arr[Result]=arr[i] then
          exit;
  Result := -1;
end;
于 2013-01-25T15:06:14.757 回答
4

要检查一个字符串是否存在两次，请使用 TStringList 的功能。创建一个 TStringList 对象，添加数组的所有元素（字符串），将 Sorted 属性设置为 True，然后从头到尾循环检查当前元素是否等于最后一个元素，如果相等则您找到了复制。

使用 TStringList 的主要优点是提供的排序功能。

于 2013-01-25T15:11:04.683 回答
2

TArray 类型是泛型风格的经典动态数组。此类型由 Delphi 管理，因此您无需手动释放所涉及的内存。如果您存储对象或其他动态创建的变量，您仍然有责任释放该内存，但同样，不是数组本身。

特别是在 TArray 上，它们都是托管类型，您根本不关心内存。

要检查无序数组中的重复项，您必须遍历它并对每个元素进行循环，与数组的其余部分进行比较，如下所示：

var
  arr: TArray<string>;
  e1, e2, e3, e4: string;
  I, J: Integer;
begin
  e1 := 'val1';
  e2 := 'val2';
  e3 := 'val3';
  e4 := 'val4';

  arr := TArray<string>.Create(e1, e2, e3, e4);
  //check for duplicates
  for I := low(arr) to High(arr) do
    for J := I + 1 to High(arr) do
      if arr[I] = arr[J] then
        ShowMessage('A duplicate was found');

最后，字符串不能为空，因此您不必检查空元素。

准确地说，任何空字符串 ( '') 实际上都是一个 nil 指针，但这是故事的另一面。

于 2013-01-25T15:05:15.193 回答