Delphi - THashedStringList добавочный поиск

Question

У меня есть THashedStringList с почти 200 тысячами элементов (строк и объектов). Этот список будет активно использоваться при поиске предметов на нем. В некоторых случаях мне нужен дополнительный поиск по нему. Я написал элементарный пример для инкрементального поиска с использованием подпрограммы 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', Ваши частичные совпадения заканчиваются этим пунктом. Если такого элемента не существует, совпадений нет.