пятница, 19 февраля 2010 г.

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

Это перевод 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
переходя от мелкого до глубокого уровня постепенно, вместо того, чтобы постоянно нырять на максимальную глубину и возвращаться обратно.

Комментариев нет:

Отправить комментарий

Можно использовать некоторые HTML-теги, например:

<b>Жирный</b>
<i>Курсив</i>
<a href="http://www.example.com/">Ссылка</a>

Вам необязательно регистрироваться для комментирования - для этого просто выберите из списка "Анонимный" (для анонимного комментария) или "Имя/URL" (для указания вашего имени и ссылки на сайт). Все прочие варианты потребуют от вас входа в вашу учётку (поддерживается OpenID).

Пожалуйста, по возможности используйте "Имя/URL" вместо "Анонимный". URL можно просто не указывать.

Ваше сообщение может быть помечено как спам спам-фильтром - не волнуйтесь, оно появится после проверки администратором.