Ширина иногда лучше чем глубина

Это перевод Breadth is sometimes better than depth. Автор: Эрик Липперт.

Совсем недавно Scripting Guys писали об использовании рекурсии для поиска всех файлов в папке и всех её под-папках. Вы можете заметить, что в этом очень стандартном подходе к этому вопросу используется принцип "сначала в глубину".

Иными словами, этот способ перечисляет файлы так:

c:\xyz.txt
c:\foo\bbb.txt
c:\foo\abc\def.txt
c:\foo\bar\baz.txt
c:\foo\bar\blah.txt
c:\qaz\zaq.txt
c:\qaz\lll\ggg.txt

Он берёт ветку (путь) и следует вдоль неё так глубоко, как сможет, перечисляя каталоги вдоль пути, откатываясь назад на минимально возможную глубину, выбирая следующую ветку и снова ныряя в глубину - и так далее, пока не пройдёт всё дерево. Теперь вы видите, почему это называется "поиском-в-глубину".

Вам не нужно использовать рекурсию для этого; рекурсия - это просто элегантный способ решить проблему. Суть алгоритма в том, что информация о следующем узле для обработки сохраняется в стеке. Алгоритм прост: взять элемент со стека; найти все подпапки и запихнуть их в стек снова; повторять, пока стек не опустеет. Рекурсия просто позволяет вам записать этот алгоритм без явного оперирования со стеком; стеком в этом случая является процессорный стек (стек вызовов), а выполнение рекурсивного вызова автоматически создаст в стеке для вас запись. Мы можем с лёгкостью сделать это и без рекурсии, используя стек явно:

type
  TStringStack = class helper for TStringList
  public
    procedure Push(const AStr: String);
    function Pop: String;
  end;

{ TStringStack }

procedure TStringStack.Push(const AStr: String);
begin
  Add(AStr);
end;

function TStringStack.Pop: String;
begin
  Result := Strings[Count - 1];
  Delete(Count - 1);
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Stack: TStringList;
  CurDir: String;
  SR: TSearchRec;
begin
  Stack := TStringList.Create;
  try
    Stack.Push('.');

    while Stack.Count > 0 do
    begin
      CurDir := IncludeTrailingPathDelimiter(Stack.Pop);
      if FindFirst(CurDir + '*.*', faDirectory, SR) = 0 then
      try
        repeat
          if (SR.Name <> '.') and (SR.Name <> '..') then
          begin
            if (SR.Attr and faDirectory) <> 0 then
              Stack.Push(CurDir + SR.Name);
          end;
        until FindNext(SR) <> 0;
      finally
        FindClose(SR);
      end;

      if FindFirst(CurDir + '*.*', faAnyFile, SR) = 0 then
      try
        repeat
          if (SR.Attr and faDirectory) = 0 then
            Memo1.Lines.Add(CurDir + SR.Name);
        until FindNext(SR) <> 0;
      finally
        FindClose(SR);
      end;
    end;

  finally
    FreeAndNil(Stack);
  end;
end;

Примечания переводчика: я использовал класс-хэлпер только для упрощения кода. На практике не стоит использовать классовые хэлперы, так как это исключительно средство для обратной совместимости (как ни странно). Вместо хэлперов используйте дочерний класс или (что лучше) реализацию стека из какой-нибудь библиотеки (наверняка в JCL или DeHL есть что-то такое, а с появлением генериков может даже в штатной поставке что-то есть - мне лениво смотреть).

Но на следующий день у меня появилась проблема - несколько недель ранее я написал небольшую тестовую программу, которую я закинул куда-то недалеко в свою иерархию каталогов, но я не помнил куда именно. Я уже имел программу поиска выше, так что я легко мог модифицировать её, чтобы добавить поиск по регулярному выражению. Однако, у меня было несколько очень глубоко вложенных каталогов, в которых я точно знал, что программы быть не может, но поиск в них занимал очень большое количество времени. Я мог бы добавить проверки на пропуск этих каталогов, но был и другой способ решить проблему: поскольку я знал, что файл лежит где-то неглубоко, то мне вообще не нужно было делать тогда поиск-в-глубину. Вместо этого мне был нужен поиск-в-ширину. Т.е. поиск всех файлов в корне, затем поиск всех файлов на первом уровне, потом поиск во всех папках второго уровня, потом третьего и т.д.

Отличная новость: мы можем использовать практически тот же самый алгоритм, с минимальным изменением. Вместо выполнения LIFO (стека) нужно делать FIFO (очередь) - и вы волшебным образом получите поиск-в-ширину:

type
  TStringQueue = class helper for TStringList
  public
    procedure Push(const AStr: String);
    function Pop: String;
  end;

{ TStringQueue }

procedure TStringQueue.Push(const AStr: String);
begin
  Add(AStr);
end;

function TStringQueue.Pop: String;
begin
  Result := Strings[0];
  Delete(0);
end;

Тогда этот способ расположит файлы в таком порядке:

c:\xyz.txt
c:\qaz\zaq.txt
c:\foo\bbb.txt
c:\qaz\lll\ggg.txt
c:\foo\abc\def.txt
c:\foo\bar\baz.txt
c:\foo\bar\blah.txt

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