用于使用 id 和 string 进行搜索的变量类型

Question

我需要在内存中存储 3 个字段的大约 500-1000 个条目，并通过 int 和 str 值进行快速有效的搜索。搜索以大约 300-500 个请求的快速爆发形式进行。我不确定如何有效地做到这一点。

存储的数据由 3 个字段组成：

ID - 整数，不是连续的。 IE。它会像 (3, 5, 12, 55)，但不是 (1, 2, 3, 4, 5)。
名称 - 字符串。
标签 - 字符串。

有 3 种可能的情况：

按姓名获取 ID。
通过 ID 获取名称。
按 ID 获取标签。

目前，我使用两种不同的类型：

带密钥对“%s=%i”的 THashedStringList 按名称搜索。
按其他搜索的 ID 排序的记录数组。

我发现这非常低效，目前正在寻找新的想法。有什么提示吗？

Answer 1

正如 David Heffernan 所建议的，您可能需要为此使用适当的数据库。

但是，如果您想要一个更轻量级的解决方案，并且具有出色的性能，您可以使用一个对象列表来存储您的所有项目和两个分别通过 ID 和名称引用这些项目的字典。

举个例子，考虑一只青蛙：

type
  TFrog = class
    ID: Integer;
    Name: string;
    Address: string;
  end;

与您的示例一样，此 class 具有一个整数和两个字符串成员。我们假设每只青蛙都有一个唯一的 ID 和一个唯一的名字。（但两只或更多只青蛙可能共享同一个地址。）

为了能够测试性能，我们创建了一个原始的青蛙生成函数：

function CreateRandomFrog: TFrog;
const
  FrogFirstNames: array[0..11] of string =
    ('Luke', 'Smith', 'John', 'Maggie', 'Rose', 'Bill', 'Edward', 'Harry',
     'Andrew', 'Michael', 'Molly', 'Arthur');
  FrogLastNames: array[0..7] of string =
    ('Jones', 'Stone', 'Rock', 'Hill', 'Waterfall', 'Sky', 'Flower', 'Rain');
  FrogInitials: array[0..25] of Char = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  FrogAddressesPrefixes: array[0..3] of string =
    ('Tree', 'Swamp', 'Lawn', 'Lake');
begin
  Result := TFrog.Create;
  try
    Result.ID := Random(10*N);
    Result.Name := FrogFirstNames[Random(Length(FrogFirstNames))] + #32 +
      FrogInitials[Random(Length(FrogInitials))] + '.' +
      FrogInitials[Random(Length(FrogInitials))] + '.' +
      FrogInitials[Random(Length(FrogInitials))] + '.' + #32 +
      FrogLastNames[Random(Length(FrogLastNames))];
    Result.Address := FrogAddressesPrefixes[Random(Length(FrogAddressesPrefixes))] +
      #32 + Random(Byte.MaxValue).ToString;
  except
    Result.Free;
    raise;
  end;
end;

这会创造出像

这样的青蛙

ID: 123
Name: Bill D.H.H. Rock
Address: Tree 52

我们还定义了一个常量

const
  N = 1000000;

这是我们将同时创建的青蛙数量。

现在，一些操作：定义一个 class

type
  TFrogFarm = class
    Frogs: TObjectList<TFrog>;
    FrogsByID: TDictionary<Integer, TFrog>;
    FrogsByName: TDictionary<string, TFrog>;
    constructor Create;
    destructor Destroy; override;
    procedure TrySearchFarm;
  end;

想法是 Frogs 列表拥有青蛙对象，而 FrogsByID 和 FrogsByName 字典只引用青蛙对象而不拥有它们。这些是使用 ID 和名称作为键的字典。

像这样实现它：

{ TFrogFarm }

constructor TFrogFarm.Create;
var
  Frog: TFrog;
begin

  // Create the list that owns the frog objects
  Frogs := TObjectList<TFrog>.Create;

  // Create the dictionaries that refer to the frog objects without owning them
  FrogsByID := TDictionary<Integer, TFrog>.Create;
  FrogsByName := TDictionary<string, TFrog>.Create;

  // Create N random frogs with unique IDs and names
  repeat
    Frog := CreateRandomFrog;
    if not FrogsByID.ContainsKey(Frog.ID) and not FrogsByName.ContainsKey(Frog.Name) then
    begin
      Frogs.Add(Frog); // transfer of ownership
      FrogsByID.Add(Frog.ID, Frog);
      FrogsByName.Add(Frog.Name, Frog);
    end
    else
      Frog.Free; // if this weren't a simple test project, we'd protect this better
  until Frogs.Count = N;

end;

destructor TFrogFarm.Destroy;
begin
  FreeAndNil(FrogsByName);
  FreeAndNil(FrogsByID);
  FreeAndNil(Frogs);
  inherited;
end;

procedure TFrogFarm.TrySearchFarm;
var
  Frog: TFrog;
  S1, S2: string;
  c1, c2, f: Int64;
begin

  QueryPerformanceFrequency(f);
  QueryPerformanceCounter(c1);

  if FrogsByID.TryGetValue(100, Frog) then
    S1 := 'There is a frog with ID 100.'#13#10'He or she lives at ' + Frog.Address + '.'
  else
    S1 := 'There is NO frog with ID 100.';

  if FrogsByName.TryGetValue('Maggie A.M.D. Flower', Frog) then
    S2 := 'There is a frog named "Maggie A.M.D. Flower".'#13#10'She lives at ' + Frog.Address + '.'
  else
    S2 := 'There is NO frog named "Maggie A.M.D. Flower".';

  QueryPerformanceCounter(c2);

  ShowMessage(S1 + sLineBreak + sLineBreak + S2 + sLineBreak + sLineBreak +
    'Execution time: ' + Round(1000000*(c2 - c1)/f).ToString + ' µs');

end;

要尝试这个，做

begin
  Randomize;
  while True do
    with TFrogFarm.Create do
      try
        TrySearchFarm;
      finally
        Free;
      end;
end;

在字典中查找元素是一个 O(1) 操作，因此即使在非常大的集合中也很快。而且，事实上，农场里有 100 万只青蛙 (N = 1000000)，在我的系统上查找大约需要 2 微秒：

Answer 2

我根据 Andreas Rejbrand 的建议整理了这个答案，作为他的对比基于字典的答案。它不太可能表现得那么好，但在某些方面设置起来更简单。

它显示了基于 TDataSet 的方法在许多方面的局限性，主要其中之一是需要为字符串字段设置最大字段大小。 FireDAC 支持 ftWideString 字段，但这并不意味着您应该使用它们来存储 Delphi “巨大” 字符串。

对于搜索，我使用了标准数据集 Locate 函数，但如果您优化后，为不同的设置索引可能会更好搜索类型和 select 正确的搜索类型运行-时间。

我不确定您打算如何使用标签字段。如果你想拥有一个每条记录有任意数量的标签，最好将它们放在数据集中与 FDMemTable1 的主从关系的细节侧。留作练习对于 reader.

procedure TForm2.FormCreate(Sender: TObject);
var
  AField : TField;
  i : Integer;
begin
  AField := TIntegerField.Create(Self);
  AField.FieldName := 'ID';
  AField.DataSet := FDMemTable1;

  AField := TStringField.Create(Self);
  AField.FieldName := 'Name';
  AField.Size := 80;
  AField.DataSet := FDMemTable1;

  AField := TStringField.Create(Self);
  AField.FieldName := 'Tags';
  AField.Size := 80;
  AField.DataSet := FDMemTable1;

  // FDMemTable1.IndexFieldNames := 'Name;ID';
  FDMemTable1.CreateDataSet;

  FDMemTable1.DisableControls;
  try
    for i := 1 to 1000 do
      FDMemTable1.InsertRecord([i, 'Frog' + IntToStr(i), Chr(Ord('A') + Random(26))]);
  finally
    FDMemTable1.EnableControls;
  end;
end;

function TForm2.FindByName(const AName : String) : Boolean;
begin
  Result := FDMemTable1.Locate('Name', AName, []);
end;

function TForm2.FindByID(const AID: Integer) : Boolean;
begin
  Result := FDMemTable1.Locate('ID', ID, []);
end;

用于使用 id 和 string 进行搜索的变量类型

Variable Type for searching both with id and string

delphi

delphi-10-seattle