如何在通用TList中搜索具有特定字段值的记录？

Question

如何在通用TList中搜索具有特定字段值的记录？

6

关于通用的 TList 一切。我有以下结构：

Type
  TExtract = record
    Wheel: string;
    Extract: array [1..5] of Byte;
  end;

  TExtractList = TList<TExtract>

  TEstr = record
    Date: TDate;
    Extract: TExtractList;
  end;

  TEstrList = TList<TEstr>;

主列表是 TExtrList，在这个列表中我有所有的日期，每个日期都有与该日期相应的轮子。我想要查找日期是否存在。如果不存在，我将从 TEstr 中提取信息并添加到子列表 TExtractList 中。当我从 TExtrList 搜索时，Delphi 会询问 TEstr 类型。我需要仅搜索 Date 字段。那么如何在通用的 TList 中搜索单个字段呢？

注：我删除了上一篇文章，因为在这里我尝试更好地解释。

- Marcello Impastato

6

没错，你删除了最后一篇帖子，就在我编辑我的答案向你展示如何使用二分查找算法搜索日期之后。这样做不太好。 - Cosmin Prund

你的列表有多大？搜索方法将取决于你是否在处理小型列表（几十个项目）或大型列表。如果你的列表很小，线性搜索将是最易读且可能是最佳解决方案。 - jpfollenius

补充Smasher的评论：如果您只需要搜索列表几次，线性搜索方法是首选。使用智能搜索（二分搜索）需要相当多的工作来对列表进行排序。另一方面，如果您要执行数千个列表查找，则BinarySearch将具有优势，并且排序将非常有用。如果您进行更多的搜索，您可能希望使用TDictionary<Date，Integer>来使搜索更快。 - Cosmin Prund

@Marcello 我尝试改进了一下这个问题，但保留了类型名称不变。我认为你对 TEstr、TExtr、TExtrList 和 TEstrList 有些混淆（它们在代码和解释上有所不同）。如果您能编辑这些内容，那就太好了。 - Heinrich Ulbricht

5个回答

2

你可以声明一个辅助类来避免比较的左右两侧必须是特定类型的 IComparer 的要求，例如：

type
  TLeftComparison<T> = reference to function(const Left: T; var Value): Integer;

  TListHelper<T> = class
  public
    class function BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
      Comparison: TLeftComparison<T>; Index, Count: Integer): Boolean; overload;
    class function BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
      Comparison: TLeftComparison<T>): Boolean; overload;
    class function Contains(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Boolean;
    class function IndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
    class function LastIndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
  end;

class function TListHelper<T>.BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
  Comparison: TLeftComparison<T>; Index, Count: Integer): Boolean;
var
  L, H: Integer;
  mid, cmp: Integer;
begin
  Result := False;
  L := Index;
  H := Index + Count - 1;
  while L <= H do
  begin
    mid := L + (H - L) shr 1;
    cmp := Comparison(Instance[mid], Value);
    if cmp < 0 then
      L := mid + 1
    else
    begin
      H := mid - 1;
      if cmp = 0 then
        Result := True;
    end;
  end;
  FoundIndex := L;
end;

class function TListHelper<T>.BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
  Comparison: TLeftComparison<T>): Boolean;
begin
  Result := BinarySearch(Instance, Value, FoundIndex, Comparison, 0, Instance.Count);
end;

class function TListHelper<T>.Contains(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Boolean;
begin
  Result := IndexOf(Instance, Value, Comparison) >= 0;
end;

class function TListHelper<T>.IndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
var
  I: Integer;
begin
  for I := 0 to Instance.Count - 1 do
    if Comparison(Instance[I], Value) = 0 then
      Exit(I);
  Result := -1;
end;

class function TListHelper<T>.LastIndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
var
  I: Integer;
begin
  for I := Instance.Count - 1 downto 0 do
    if Comparison(Instance[I], Value) = 0 then
      Exit(I);
  Result := -1;
end;

然后你可以像这样使用它：

// TComparison (requires instances on both sides)
function CompareEstr(const Left, Right: TEstr): Integer;
begin
  if Left.Date < Right.Date then
    Exit(-1);
  if Left.Date > Right.Date then
    Exit(1);
  Result := 0;
end;

// TLeftComparison: requires instance only on the left side    
function CompareEstr2(const Left: TEstr; var Value): Integer;
begin
  if Left.Date < TDateTime(Value) then
    Exit(-1);
  if Left.Date > TDateTime(Value) then
    Exit(1);
  Result := 0;
end;

procedure Main;
var
  Date: TDate;
  Comparer: IComparer<TEstr>;
  List: TEstrList;
  Item: TEstr;
  Index: Integer;
  I: Integer;
begin
  Comparer := nil;
  List := nil;
  try
    // create a list with a comparer
    Comparer := TComparer<TEstr>.Construct(CompareEstr);
    List := TEstrList.Create(Comparer);
    // fill with some data
    Date := EncodeDate(2011, 1, 1);
    for I := 0 to 35 do
    begin
      Item.Date := IncMonth(Date, I);
      List.Add(Item);
    end;
    // sort (using our comparer)
    List.Sort;

    Date := EncodeDate(2011, 11, 1);
    Item.Date := Date;

    // classic approach, needs Item on both sides   
    Index := List.IndexOf(Item);
    Writeln(Format('TList.IndexOf(%s): %d', [DateToStr(Date), Index]));
    List.BinarySearch(Item, Index);
    Writeln(Format('TList.BinarySearch(%s): %d', [DateToStr(Date), Index]));
    Writeln;

    // here we can pass Date directly
    Index := TListHelper<TEstr>.IndexOf(List, Date, CompareEstr2);
    Writeln(Format('TListHelper.IndexOf(%s): %d', [DateToStr(Date), Index]));
    TListHelper<TEstr>.BinarySearch(List, Date, Index, CompareEstr2);
    Writeln(Format('TListHelper.BinarySearch(%s): %d', [DateToStr(Date), Index]));
    Readln;
  finally
    List.Free;
  end;
end;

这当然不太类型安全（由于未经过类型定义的右侧比较参数），但需要允许对不同类型的值进行通用比较。如果小心处理，这应该不是问题。否则，您也可以为大多数需要比较的常用类型编写重载版本。

- Ondrej Kelle

我不喜欢这种方法。TCompare<T> = function(const L, R: T): Integer; 更有效，没有任何有趣的接口。 - user3764855

同时，在XE6中使用“reference to”会影响性能，原始回调是最快的。 - user3764855

2

我发现只有一种方法可以按特定值搜索列表。

我将重用Cosmin Prund的示例：

uses Generics.Defaults; // this provides TDelegatedComparer
uses Math; // this provides Sign()

function SearchList(Date:TDate; Sort:Boolean; List:TList<TEstr>): Integer;
var Dummy : TEstr;
begin
  // If the list is not sorted, sort it. We don't know if it's sorted or not,
  // so we rely on the "Sort" parameter
  if Sort then List.Sort(TDelegatedComparer<TEstr>.Construct(
    function (const L, R: TEstr): Integer
    begin
      Result := Sign(L.Date - R.Date);
    end
  );

  // Call BinarySearch() to look up the record based on Date alone
  if not List.BinarySearch(Dummy, Result, TDelegatedComparer<TEstr>.Construct(
      function (const L, R: TEstr): Integer
      begin
         //By implementation, the binarySearch Dummy parameter is passed in the "R" parameter of the Comparer function. (In delphi 2010 at least)
        Result := Sign(L.Date - Date); //Use the Date parameter instead of R.Date
      end) then
    Result := -1;
end;

然而，这种方法只在实现时有效，而不是在设计时（据我所知）。换句话说，它容易在Delphi版本之间发生错误。因此，建议仅在需要创建“性能昂贵”的项目时使用此方法。如果您这样做，我强烈建议在代码中添加类似以下的内容。

{$IF RTLVersion > *YourCurrentVersion*}
   {$MESSAGE WARNING 'Verify if BinarySearch implementation changed'}    
{$IFEND}

这样，下次您在更高版本的Delphi中构建此代码时，您将自动收到警告，提示您确保代码仍按预期工作。但是，如果您的代码需要同时支持多个版本的Delphi，则仍可能会导致问题。

- Ken Bourassa

1

我认为你可以在TDynArrayHashed中找到这个函数，这里有一个帖子作为例子。

- philnext

0

它真的需要是TList吗？在我看来，二分搜索对于这个问题来说太复杂了。也许你可以简单地使用一个TDictionary：

type
  TEstrCollection = TDictionary<TDate, TEstr>;

var
  EstrCollection: TEstrCollection;
begin
  EstrCollection := TEstrCollection.Create;

  // Add an item
  EstrCollection.Add(Date, TExtractList.Create)

  // Search
  ExtractList := EstrCollection[Date];
end;

现在，这需要日期字段是唯一的，因为它是字典的关键。此外，项目没有特定的顺序。

如果顺序很重要，我会结合数据结构。例如，您可以有一个TList仅按顺序保存项目，再加上一个TDictionary执行搜索等操作。

唯一的问题是记录不是指针。要将相同的记录添加到两个不同的数据结构中，您需要为它们创建指针。

PEstr = ^TEstr

或者直接使用对象，因为它们已经是指针了。您可以使用 TObjectList 和 TObjectDictionary，通过集合自动管理项目的生命周期（只需记住如果一个对象在多个集合中，则只有一个集合管理对象的生命周期）。

- Rafael Piccolo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cosmin Prund · Accepted Answer

我们再来一次。

即使TList<T>.BinarySearch()函数要求以TEstr记录作为参数，您也应该使用内置的函数。您需要首先使用TList<T>.Sort()函数按照与搜索相同的标准对列表进行排序，然后调用BinarySearch()函数查找记录。

以下是同时执行排序和搜索的函数：

uses Generics.Defaults; // this provides TDelegatedComparer
uses Math; // this provides Sign()

function SearchList(Date:TDate; Sort:Boolean; List:TList<TEstr>): Integer;
var Comparer: IComparer<TEstr>;
    Dummy: TEstr;
begin
  // Prepare a custom comparer that'll be used to sort the list
  // based on Date alone, and later to BinarySearch the list using
  // date alone.
  Comparer := TDelegatedComparer<TEstr>.Construct(
    function (const L, R: TEstr): Integer
    begin
      Result := Sign(L.Date - R.Date);
    end
  );

  // If the list is not sorted, sort it. We don't know if it's sorted or not,
  // so we rely on the "Sort" parameter
  if Sort then List.Sort(Comparer);

  // Prepare a Dummy TEstr record we'll use for searching
  Dummy.Date := Date;

  // Call BinarySearch() to look up the record based on Date alone
  if not List.BinarySearch(Dummy, Result, Comparer) then
    Result := -1;
end;

BinarySearch 假设列表已排序（这就是二分搜索的本质！）。在第一次调用时，您需要设置 Sort=True，以便正确排序列表。在后续调用中，Sort 应为 False。当然，在实际使用中，您可能会为搜索和排序编写单独的例程，并将它们作为从 TList<TEstr> 下降的类的方法（以使事情更容易）。我将两者放在同一个程序中以进行演示。