Delphi

Question

我有一个 THashedStringList，上面有将近 20 万个项目（字符串和对象）。该列表将大量用于搜索其中的项目。在某些情况下，我需要对其进行增量搜索。我已经使用 StartsText 例程

为增量搜索编写了一个基本示例

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs,
  System.IniFiles, Vcl.StdCtrls,
  System.StrUtils;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Edit1: TEdit;
    Memo2: TMemo;
    procedure FormCreate(Sender: TObject);
    procedure Edit1KeyUp(Sender: TObject; var Key: Word; Shift: TShiftState);
  private
    { Private declarations }
  public
  ahsStrLst : THashedStringList;
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

function generate(cantidad: integer): string;
const
  letras_mi = 'abcdefghijklmnopqrstuvwxyz';
 var
  i: Integer;
begin
  Result := '';
  for I := 0 to cantidad-1 do
    Result := Result + letras_mi[Random(Length(letras_mi)) + 1];
end;

procedure TForm1.Edit1KeyUp(Sender: TObject; var Key: Word; Shift: TShiftState);
var iPos: Integer;
begin
 Memo2.Clear;
 Memo2.Update;
 for ipos := 0 to ahsStrLst.Count-1 do
  if StartsText(Edit1.Text,ahsStrLst[iPos]) then
   Memo2.Lines.Add(ahsStrLst[iPos])
end;

procedure TForm1.FormCreate(Sender: TObject);
var ipos:Integer;
begin
  ahsStrLst := THashedStringList.Create;
  for iPos := 0 to 50000 do
   ahsStrLst.AddObject(generate(4),TObject(ipos));//here there will be diffent type of objects
  for iPos := 0 to 50000 do
   ahsStrLst.AddObject(generate(6),TObject(ipos));
  for iPos := 0 to 50000 do
   ahsStrLst.AddObject(generate(8),TObject(ipos));
  for iPos := 0 to 50000 do
   ahsStrLst.AddObject(generate(10),TObject(ipos));

   Memo1.Lines.AddStrings(ahsStrLst);
end;

end.

有什么方法可以加快这种增量搜索的速度吗？

Answer 1

首先，您应该停止使用 THashedStringList。一旦你得到了带有泛型的 Delphi ，你应该使用 TDictionary<K,V> 来代替。它提供了一个更简洁的界面，并且性能更好。然而，在这种情况下，对部分匹配的需求使得基于散列的查找变得无能为力。你需要一个不同的数据结构。

为了高效的部分匹配查找，您可以考虑维护一个有序列表。然后您可以使用二分法执行查找。因为您正在执行部分匹配，所以您必须制作自己的二分法，因为 RTL 提供的所有工具都用于搜索单个项目。

假设您正在搜索 'abc'。首先找到最大值< 'abc'。您的部分匹配项从后面的项目开始。然后找到以'abc'开头的最大值。您的部分匹配项以该项目结束。如果不存在这样的项目，则没有匹配项。

Delphi - THashedStringList 增量搜索

Delphi - THashedStringList incremental search

delphi-xe2

incremental-search