Эффективный бинарный поиск элементов в `TStringList` с определённым префиксом в Delphi

Delphi , Компоненты и Классы , Списки

Эффективный бинарный поиск элементов в TStringList с определённым префиксом в Delphi

При работе с большими объемами данных в Delphi важно использовать эффективные алгоритмы поиска. В данном случае рассматривается задача поиска элементов в отсортированном списке TStringList, которые начинаются на определенный префикс. Это может быть полезно, например, при проверке наличия файлов в подпапке.

Описание проблемы

У нас есть отсортированный TStringList, содержащий уникальные имена файлов, который может содержать сотни тысяч записей. Нам необходимо проверить, есть ли в списке элементы, начинающиеся на определенную строку, то есть, находятся ли файлы в подпапке. Простой последовательный поиск с использованием метода StartsText может быть неэффективен для больших списков.

Решение

Разработчик предложил функцию ShortcutFind, которая использует алгоритм бинарного поиска для решения поставленной задачи. Функция проверяет, начинается ли элемент списка на указанный префикс, прежде чем переходить к следующему элементу. Это позволяет улучшить производительность поиска по сравнению с линейным сканированием списка.

function ShortcutFind(const S: string): Boolean;
var
  L, H, I, C: Integer;
begin
  Result := False;
  L := 0;
  H := FList.Count - 1;
  while L <= H do begin
    I := (L + H) shr 1;
    if TFilenameUtils.StartsFilename(FList[I], S) then begin
      Result := TRUE;
      Exit;
    end;
    C := FList.CompareStrings(FList[I], S);
    if C < 0 then
      L := I + 1
    else begin
      H := I - 1;
      // Проверка на дубликаты не требуется, так как функция ищет префикс, а не точное совпадение
    end;
  end;
end;

Подтвержденный ответ

После обсуждения на форуме было предложено упростить функцию, используя метод Find из TStringList. Также было отмечено, что проверка на дубликаты не требуется, так как функция ищет элементы с определенным префиксом, а не точные совпадения.

var
  I: Integer;
begin
  Assert(not FList.CaseSensitive);
  Result := FList.Find(S, I) or ((I < FList.Count) and TFilenameUtils.StartsFilename(S, FList[I]));
end;

Этот подход использует информацию о том, где должен был бы находиться искомый элемент, если бы он был в списке, для определения наличия элементов с префиксом.

Заключение

Бинарный поиск является эффективным решением для поиска элементов в отсортированном списке TStringList с определенным префиксом. Предложенные функции могут быть использованы в проектах на Delphi для ускорения работы с большими объемами данных.

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

В Delphi рассматривается задача эффективного бинарного поиска элементов в отсортированном списке `TStringList` с определённым префиксом для работы с большими объемами данных.

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

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

:: Главная :: Списки ::