Ускорение поиска в больших наборах данных: оптимизация использования `THashedStringList` в Delphi

Delphi , Базы данных , Поиск

Ускорение поиска в больших наборах данных: оптимизация использования THashedStringList в Delphi

Введение

В статье рассматривается проблема эффективного поиска в больших наборах данных, используя компонент THashedStringList в среде разработки Delphi. THashedStringList представляет собой структуру данных, которая позволяет быстро находить элементы по ключу, благодаря использованию хеш-функции. Однако, при необходимости выполнения поиска с частичным совпадением, стандартные методы хеш-структур становятся неэффективными.

Проблема

Разработчик столкнулся с необходимостью реализации инкрементного поиска в THashedStringList, содержащем почти 200 тысяч элементов. Использование рутин StartsText для проверки начала строки привело к неэффективному перебору всех элементов списка, что существенно замедляет поиск.

Решение

В качестве решения предлагается отказаться от использования THashedStringList и перейти к использованию TDictionary<K, V>, который обеспечивает более чистый интерфейс и лучшую производительность. Однако, учитывая требование к поиску с частичным совпадением, хеш-структуры не подходят. В этом случае необходимо использовать другую структуру данных.

Альтернативное решение

Для эффективного поиска с частичным совпадением можно использовать упорядоченный список. В этом случае поиск можно выполнять с использованием бинарного поиска (bisection). Поскольку требуется поиск с частичным совпадением, необходимо реализовать собственный алгоритм бинарного поиска, так как стандартные средства RTL предназначены для поиска отдельных элементов.

Примерный алгоритм поиска:

1. Найти наибольший элемент, который меньше заданной подстроки.
2. Найти наибольший элемент, который начинается с заданной подстроки.
3. Все элементы между этими двумя элементами будут соответствовать критерию поиска.

Пример реализации

unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Edit1: TEdit;
    Memo2: TMemo;
    procedure FormCreate(Sender: TObject);
    procedure Edit1Change(Sender: TObject);
  private
    FStringList: TStringList;
  public
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure BinarySearch(List: TStringList; const Prefix: string; var Start, End: Integer);
var
  Low, High: Integer;
begin
  Low := Start;
  High := End - 1;

  while Low <= High do
  begin
    var Mid := Low + (High - Low) div 2;
    if List[Mid] = Prefix then
    begin
      Low := Mid + 1;
      break;
    end
    else if List[Mid] < Prefix then
      Low := Mid + 1
    else
      High := Mid - 1;
  end;

  Start := Low;
end;

procedure TForm1.BinarySearchPrefix(List: TStringList; const Prefix: string; var Start, End: Integer);
begin
  BinarySearch(List, Prefix, Start, List.Count);

  if Start >= List.Count then
    Exit;

  High := Start;
  BinarySearch(List, Prefix + '#', Start, High);

  if High = Start then
    Dec(High)
  else
  begin
    Dec(High);
    while High >= Start do
      if not List[High].StartsWith(Prefix)
        Dec(High);
  end;

  End := High + 1;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  FStringList := TStringList.Create;
  // Загрузка данных в FStringList
  // ...
  FStringList.Sort;
end;

procedure TForm1.Edit1Change(Sender: TObject);
var
  Start, End: Integer;
begin
  if Edit1.Text = '' then
    Exit;

  BinarySearchPrefix(FStringList, Edit1.Text, Start, End);

  Memo2.Clear;
  for var i := Start to End - 1 do
    Memo2.Lines.Add(FStringList[i]);
end;

end.

Заключение

Для ускорения поиска в больших наборах данных в Delphi, следует отказаться от использования THashedStringList в пользу TDictionary<K, V> или, при необходимости поиска с частичным совпадением, использовать упорядоченный список и реализовать собственный алгоритм бинарного поиска. Это позволит значительно повысить скорость работы приложения, особенно при работе с большими объемами данных.

Создано по материалам из источника по ссылке.

Статья рассматривает оптимизацию поиска в большом количестве данных на языке программирования Delphi, сравнивая использование `THashedStringList` и `TDictionary`, а также предлагает алгоритм бинарного поиска для эффективного поиска с частич

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Поиск ::