Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

end;

{обработка последнего буфера завершена}

FSyncObj.StopConsuming(FID);

end;

И, наконец, рассмотрим подпрограмму копирования потоков, код которой показан в листинге 12.21.

Листинг 12.21. Копирование потоков с применением модели "производитель-потребитель"

procedure ThreadedMultiCopyStream(aSrcStream : TStream;

aDestCount : integer;

aDestStreams : PStreamArray);

var

i : integer;

SyncObj : TtdProduceManyConsumeSync;

Buffers : TQueuedBuffers;

Producer : TProducer;

Consumer : array [0..pred(MaxConsumers) ] of TConsumer;

WaitArray : array [0..MaxConsumers] of THandle;

begin

SyncObj nil;

Buffers nil;

Producer :=nil;

for i := 0 to pred(MaxConsumers) do

Consumer[i] := nil;

for i := 0 to MaxConsumers do

WaitArray[i] := 0;

try

{создать объект синхронизации}

SyncObj : * TtdProduceManyConsumeSync.Create(20, aDestCount);

{создать объект буфера с очередью}

Buffers := TQueuedBuffers.Create(20, aDestCount);

{создать поток производителя и сохранить его дескриптор}

Producer := TProducer.Create(aSrcStream, SyncObj, Buffers);

WaitArray[0] := Producer.Handle;

{создать потоки потребителей и сохранить их дескрипторы}

for i := 0 to pred(aDestCount) do

begin

Consumer [ i ] := TConsumer.Create(

aDestStreams^[i], SyncObj, Buffers, i);

WaitArray[i+1] := Consumer[i].Handle;

end;

{запустить потоки}

for i := 0 to pred(aDestCount) do

Consumer[i].Resume;

Producer.Resume;

{ожидать завершения потоков}

WaitForMultipleObjects(l+aDestCount, @WaitArray, true, INFINITE);

finally Producer.Free;

for i := 0 to pred(aDestCount) do

Consumer[i].Free;

Buffers.Free;

SyncObj.Free;

end;

end;

Большая часть кода предназначена для выполнения тех же рутинных задач, что и в модели с одним потребителем, представленной в листинге 12.14, за исключением того, что на этот раз необходимо заботиться о нескольких потребителях. Полный код подпрограммы находится в файлах TstNCpy.dpr и TstNCpyu.pas на Web-сайте издательства, в разделе материалов.

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

Существует множество программ, выполняющих подобные функции. В их числе и программа diff, которую можно считать прародительницей всех программ сравнения файлов. Пакет Microsoft Windows SDK содержит программу, названную WinDiff. Программа Visual SourceSafe, поставляемая компанией Microsoft, также предоставляет функцию, которая позволяет выбрать две версии файла, хранящиеся в базе данных, и просмотреть различия между ними.

-------

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

-------

Потратим несколько минут, и попытаемся определить требуемый для выполнения этой задачи алгоритм. Раньше я уже пытался сделать это, что оказалось достаточно трудно. Кое-что можно упростить сразу: изменение строки можно считать удалением старой строки и вставкой новой. Мы не будем углубляться в проблемы семантики, пытаясь выяснить, насколько сильно изменилась строка. Мы всего лишь будем рассматривать все изменения в текстовом файле как набор удаленных строк и набор вставленных новых строк.

Требуемый нам алгоритм известен под названием алгоритма определения наиболее длинной общей подпоследовательности (longest common subsequence - LCS). Вначале мы рассмотрим, как он работает применительно к строкам, а затем расширим приобретенные представления на текстовые файлы.

Уверен, что все мы играли с детскими головоломками, в которых нужно было преобразовать одно слово в другое, изменяя по одной букве. Все промежуточные варианты должны были быть также осмысленными словами. Так, преобразуя слово CAT в слово DOG, можно было бы выполнить следующие преобразования: CAT, COT, COG, DOG.

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

Предположим, что наша цель заключается в отыскании наименьшего количества изменений, требуемых для преобразования одного слова в другое. Для примера преобразуем слово BEGIN в слово FINISH. Мы видим, что нужно удалить буквы В, Е и G, а затем вставить букву F перед оставшимися буквами и буквы I, S и H после них. Как же реализовать эти действия в виде алгоритма?