Поиск в отсортированном TStringList записи с префиксом (StartsText)

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

Используя код TStringList.Find () в качестве отправной точки, я создал функцию, которая, на мой взгляд, является решением, но я хочу быть уверенным. Не беспокойтесь о том, что следующее не является членом класса (FList - это экземпляр TStringList, в котором выполняется поиск), а StartsFilename работает так же, как StartsText:

  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], aFolder) then begin
        Result:=TRUE;
        Exit;
      end;

      C := FList.CompareStrings(FList[I], S);
      if C < 0 then
        L := I + 1
      else begin
        H := I - 1;
        if C = 0 then begin
          Result := True;
          if FList.Duplicates <> dupAccept then L := I;
        end;
      end;
    end;
  end;

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

Обратите внимание, что переключение с TStringList не является вариантом.

Будет ли этот метод работать?

Спасибо


delphi tstringlist
person Mick    schedule 16.08.2012    source источник
comment
Это сработает? Разве ты не можешь просто попробовать и узнать? Этот код мог бы быть проще, но если вам просто нужна критика вашего кода, вы можете вместо этого перейти на сайт обзора кода Stack Overflow. В противном случае я не уверен, о чем вы на самом деле просите.   -  person Rob Kennedy    schedule 16.08.2012
comment
Я написал процедуру тестирования, чтобы проверить это, и, похоже, она работает. Думаю, я действительно просто спрашиваю, есть ли какие-нибудь очевидные дыры или лучший / более быстрый способ сделать это (в условиях сохранения TStringList). Такс.   -  person Mick    schedule 16.08.2012
comment
Важна ли эффективность? Переход на бинарный поиск может быть быстрой победой в этой области.   -  person boileau    schedule 16.08.2012
comment
@Boileau, этот код уже является бинарным поиском.   -  person Rob Kennedy    schedule 16.08.2012
comment
Упс, я неправильно прочитал код! Я такой глупый. В таком случае я проголосую за ваше решение.   -  person boileau    schedule 16.08.2012
comment
Интересно, что вы имеете в виду под TFilenameUtils.StartsFilename работает так же, как StartsText. StartText - быстрая и нетривиальная реализация, StartsStr - тривиальная и медленная. Как вы реализовали свой собственный StartsText?   -  person Arioch 'The    schedule 16.08.2012

Ответы (1)


arrow_upward
9
arrow_downward

Если TFilenameUtils.StartsFilename совпадает с StartsText (и ваш первый абзац предполагает, что это может быть), тогда вы можете выполнить всю функцию в одном операторе, используя TStringList.Find вместо его копирования:

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

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

Если вы хотите сохранить текущий код, вы можете упростить его, удалив условие, которое проверяет C = 0. Это условие никогда не должно возникать, если только ваша StartsFilename функция не нарушена. Но если функция действительно не работает и C может быть равным нулю, то вы можете по крайней мере прекратить выполнение цикла в этот момент, поскольку вы нашли то, что искали. В любом случае вам не нужно проверять Duplicates, поскольку ваша функция не имеет того же требования, что и Find, по возврату индекса найденного элемента.

person Rob Kennedy    schedule 16.08.2012
comment
Я предполагаю, что .Size на самом деле должен быть .Count? - person Mick; 16.08.2012