Оптимизированный поиск в StringList

[tsar_]

Здравствуйте.
Пишу программу типа словарь, ориентированную на пользователей, которые изучают английский язык и которым требуется вести свой словарь слов или терминов.

В проге реализован производный от TObject класс TBase, который управляет двумя списками строк: один для списка словарей, другой для хранения списка содержимого текущего словаря, каждая строка ("словарная статья") представляет собой пары "термин"="перевод".

Для каждого списка на форме имеется свой ListBox в режиме Virtual. Для поиска подходящего термина в списке на форме имеется также один компонент Edit.
Требовалось реализовать поиск первого подходящего термина в списке словарных статей.

Для этого был создан новый класс TStringListPlus от TStringList, в который добавлен новый метод FindItem поиска номеров строк по содержимому. Код класса приведен ниже:

unit StringListPlus;
//-----------------------------------------------------------------------------
//Предок - TStringList.
//Добавлены методы:
//FindItem - оптимизированный поиск номера строки в сортированном
//           (методом деления пополам);
//-----------------------------------------------------------------------------
//Автор: tsar_
//16.01.2014
//-----------------------------------------------------------------------------

interface

uses SysUtils, Classes;

type                               //тип для указания элемента поиска:
  TSearchItem = (seString,         //строка целиком,
                 seName,           //имя целиком,
                 seFirstSymb);     //первые совпадающие символы строки

type TStringListPlus = class(TStringList)
public
  //поиск номера строки
  function FindItem(const str: string; const SearchItem: TSearchItem): integer;
end;

implementation

function TStringListPlus.FindItem(const str: string;
  const SearchItem: TSearchItem): integer;
var StrLen, index1,index2,index: integer;
    uStr: string;
begin
  result:=-1;                            //сразу задаем выходное значение
  if (GetCount = 0) or (str = '') then   //если список пуст, выходим
    exit;

  index1:=0;             //устанавливаем границы интервала неопределенности
  index2:=GetCount-1;
  uStr:=AnsiUpperCase(str);   //приводим строку-образец к верхнему регистру

  //пока длина интервала > 1, сокращаем его делением пополам
  while (index2-index1 > 1) do
    begin
    index:=(index1+index2) div 2;  //определяем номер среднего элемента
    //если str "меньше" текущей строки списка, то
    if (uStr < AnsiUpperCase(Strings[index])) then
      index2:=index                //рассматриваем левый подинтервал
    else
      index1:=index;               //иначе - правый
    end;

  case SearchItem of               //определяем, что хотят искать
    seString: begin
              //анализируем границы интервала:
              //если левая граница совпадает со строкой str, то
              if (uStr =  AnsiUpperCase(Strings[index1])) then
                result:=index1    //выдаем левый индекс
              else
                //а если то же с правой границей, то
                if (uStr =  AnsiUpperCase(Strings[index2])) then
                  result:=index2;   //выдаем правый индекс
              end;
    seName: begin
            //если имя левой границы совпадают со строкой str, то
            if (uStr =  AnsiUpperCase(Names[index1])) then
              result:=index1   //выдаем левый индекс
            else
              //а если то же с правой границей, то
              if (uStr =  AnsiUpperCase(Names[index2])) then
                result:=index2;   //выдаем правый индекс
            end;
    seFirstSymb: begin
                 StrLen:=length(uStr);     //определяем длину строки str
                 //если первые символы левой границы совпадают со str, то
                 if (uStr =  AnsiUpperCase(Copy(Strings[index1],1,StrLen))) then
                   result:=index1   //выдаем левый индекс
                 else
                   //а если то же с правой границей, то
                   if (uStr =  AnsiUpperCase(Copy(Strings[index2],1,StrLen))) then
                     result:=index2;   //выдаем правый индекс
                 end;
  end;
end;

end.

Метод работает по методу (тавтология ) половинного деления и годится только для отсортированного списка. Первый параметр метода - искомая строка, второй указывает на то, что следует анализировать: первые символы строки, термин (свойство Name для TStringList) или всю строку целиком. Результатом является индекс первой соответствующей строки, если такая есть, или же -1.

Пробовал эту процедуру в упомянутой программе на файле размером более 13МБ с более чем 170000 строк - тормозов нет вообще (файл был от словаря QDictionary - там тоже используется хранение статей в виде "термин"="перевод").

Выкладываю сие творение потому, что в инете такого не находил (не скрою - искал не долго), ну и может кому-то пригодится. Также буду рад комментариям.

[Serge_Bliznykov]

у TStringList есть метод .Find

function Find(const S: string; var Index: Integer): Boolean;

для поиска в сортированном списке.

Чем Вас этот метод не устроил?

[tsar_]

у TStringList есть метод .Find

Чем Вас этот метод не устроил?

Насколько я помню, метод Find ищет номер полностью совпадающей строки, а мне необходимо было в первую очередь реализовать поиск первого подходящего термина (при наборе первых символов, как в Lingvo) и поиск имени (свойство Name для TStringList, это нужно, потому что в списке статьи хранятся в виде "термин"="перевод", а в виртуальный ListBox выводятся только термины). Позже пришлось добавить и поиск полностью совпадающей строки.

[Аватар]

Ещё пригодится поиск типа FindNearest - выдать результат даже если точный поиск не удался. Например есть строки 'abcd' и 'abcf', а ищем 'abce', тогда вернуть индекс строки 'abcf', как похожей или точно найденной строки, если есть таковая. Не важно полный поиск или по началу. Ну еще вариант поиска типа LIKE '%та-та-та%', но это уже перебор с начала

[tsar_]

Ещё пригодится поиск типа FindNearest

Да, в принципе нужно над этим покумекать. В том же Lingvo, помнится, так и сделано.

[Serge_Bliznykov]

tsar_ , в любом случае правильно сделали, что выложили свой код.
Вполне возможно, он окажется кому-то полезным!

[tsar_]

Раз уж разговор зашел за метод Find, попробую сравнить его скорость со скоростью FindItem. Я как-то смотрел исходник модуля с реализацией Find, там если правильно помню реализован поиск обычным перебором (сейчас компилятора нет под рукой).
По результатам отпишусь.

[Serge_Bliznykov]

Сообщение от tsar_

Раз уж разговор зашел за метод Find, попробую сравнить его скорость со скоростью FindItem. ...
По результатам отпишусь.

Ага, это было бы любопытно!

[Аватар]

Да точно также - методом деления пополам

[tsar_]

Да точно также - методом деления пополам

Да, вы правы. Вчера внимательнее посмотрел - в Find действительно метод половинного деления. Поэтому в принципе не вижу смысла серьезно сравнивать Find и FindItem: вчера прогнал их на файле размером ~130МБ (~1 млн строк) - все моментально и на глаз одинаково.
Таким образом, FindItem отличается от Find, в первую очередь, функциональностью, ну и немного другой технической реализацией.