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 после них. Как же реализовать эти действия в виде алгоритма?
Один из возможных способов предполагает просмотр подпоследовательностей букв каждого слова и выяснение наличия в них общих последовательностей. Подпоследовательность (subsequence) строки образуется за счет удаления из нее одного или более символов. Оставшиеся символы не должны переставляться. Например, четырехбуквенными подпоследовательностями для строки BEGIN являются EGIN, BGIN, BEGIN, BEIN и BEGI. Как видите, они образуются путем поочередного отбрасывания одного из символов. Трехбуквенными подпоследовательностями являются BEG, BEI, BEN, BGI, BGN, BIN, EGI, EGN, EIN и GIN. Для данного слова существует 10 двухбуквенных подпоследовательностей и пять одно-буквенных. Таким образом, для пятибуквенного слова существует всего 30 возможных подпоследовательностей, а в общем случае можно было бы показать, что для n-буквенной последовательности существует около 2(^n^) подпоследовательностей. Пока что примите это утверждение на веру.
Алгоритм с применением "грубой силы", если его можно так назвать, заключается в просмотре двух слов BEGIN и FINISH и просмотре их пятибуквенных подпоследовательностей на предмет наличия каких-либо совпадений. Такие совпадения отсутствуют, поэтому для каждого слова то же самое нужно сделать, используя четырехбуквенные подпоследовательности. Как и в предыдущем случае, ни одна из подпоследовательностей не совпадает, поэтому мы переходим к рассмотрению трехбуквенных последовательностей. Результат снова отрицателен, поэтому мы переходим к сравнению двухбуквенных подпоследовательностей. Самой длинной общей подпоследовательностью этих двух слов является IN. Исходя из этого, можно определить, какие буквы необходимо удалить, а какие вставить.
Для коротких слов, подобных приведенному примеру, описанный подход не так уж плох. Но представим, что требуется просмотреть все подпоследовательности 100-символьной строки. Как уже упоминалось, их количество составляет 2(^100^). Алгоритм с применением "грубой силы" является экспоненциальным. Количество выполняемых операций пропорционально O(2(^n^)). Даже для строк средней длины поле поиска увеличивается чрезвычайно быстро. А это влечет за собой радикальное увеличение времени, требуемого для отыскания решения. Чтобы сказанное было нагляднее, представим следующую ситуацию: предположим, что можно генерировать около биллиона подпоследовательностей в секунду.(т.е. 2(^40^)= 1 099 511 627 776, или тысячу подпоследовательностей за один такт работы процессора ПК, тактовая частота которого равна 1 ГГц). Год содержит около 2(^25^) секунд. Следовательно, для генерации всего набора подпоследовательностей для 100-символьного слова потребовалось бы 2(^35^) (34 359 738 368) лет - 11-значное число. А теперь вспомните, что 100-символьная строка - всего лишь простенький пример того, что необходимо сделать: например, найти различие между двумя вариантами 600-строчного исходного файла.
Однако идея применения подпоследовательностей обладает своими достоинствами. Просто нужно подойти к ней с другой стороны. Вместо перечисления и сравнения всех подпоследовательностей в двух словах посмотрим, нельзя ли применить пошаговый подход.
Для начала предположим, что нам удалось найти наиболее длинную общую подпоследовательность двух слов (далее для ее обозначения мы будем использовать аббревиатуру "LCS"). В этом случае можно было бы соединить линиями буквы в LCS первого слова с буквами LCS второго слова. Эти линии не будут пересекаться. (Это обусловлено тем, что подпоследовательности определены так, что перестановки букв не допускаются. Поэтому буквы в LCS в обоих словах будут располагаться в одинаковом порядке.) LCS для слов "banana" и "abracadabra" (т.е. b, а, а, а) и линии, соединяющие совпадающие в них буквы, показаны на рис. 12.1. Обратите внимание, что для этой пары слов существует несколько возможных LCS. На рисунке, показана лишь первая из них (занимающая самую левую позицию).
Рисунок 12.1. LCS для слов "banana" и "abracadabra"
Итак, тем или иным способом мы определили LCS двух слов. Предположим, что длина этой подпоследовательности равна х. Взгляните на последние буквы обоих слов. Если ни одна из них не является частью соединительной линии, и при этом они являются одной и той же буквой, то эта буква должна быть последней буквой LCS и между ними должна была бы существовать соединительная линия. (Если эта буква не является последней буквой подпоследовательности, ее можно было бы добавить, удлинив LCS на одну букву, что противоречило бы сделанному предположению о том, что первая подпоследовательность является самой длинной.) Удалим эту последнюю букву из обоих слов и из подпоследовательности.
Полученная сокращенная подпоследовательность длиной x - 1 представляет собой LCS двух сокращенных слов. (Если бы это было не так, для двух сокращенных слов должна была бы существовать общая подпоследовательность длиной X или больше. Добавление заключительных букв привело бы к увеличению длины новой общей подпоследовательности на единицу, а, значит, для двух полных слов должна была бы существовать общая подпоследовательность, содержащая x+1 или более букв. Это противоречит предположению о том, что мы определили LCS.)
Теперь предположим, что последняя буква в LCS не совпадает с последней буквой первого слова. Это означало бы, что LCS двух полных слов была бы также LCS первого слова без последней буквы и второго слова (если бы это было не так, можно было бы снова добавить последнюю букву к первому слову и найти более длинную LCS двух слов). Эти же рассуждения применимы и к случаю, когда последняя буква второго слова не совпадает с последней буквой LCS.
Все это замечательно, но о чем же оно свидетельствует? LCS содержит в себе LCS усеченных частей обоих слов. Для отыскания LCS строк X и Y мы разбиваем задачу на более мелкие задачи. Если бы последние символы слов X и Y совпадали, нам пришлось бы найти LCS для строк X и Y без их последних букв, а затем добавить эту общую букву. Если нет, нужно было бы найти LCS для строки X без последней буквы и строки Y, а также LCS строки X и строки Y без ее последней буквы, а затем выбрать более длинную из них. Мы получаем простой рекурсивный алгоритм.
Однако во избежание проблемы, которая может быть порождена простым решением, вначале необходимо описать алгоритм несколько подробней.
Мы пытаемся вычислить LCS двух строк X и Y. Вначале мы определяем, что строка X содержит n символов, а строка Y - m. Обозначим строку, образованную первыми i символами строки X, как Х(_i_). i может принимать также нулевое значение, что означает пустую стоку (это соглашение упростит понимание алгоритма). В таком случае Х(_n_) соответствует всей строке. С применением этой формы записи алгоритм сводится к следующему; если последние два символа строк Х(_n_) и Y(_m_) совпадают, самая длинная общая последовательность равна LCS Х(_n-1_) и Y(_m-1_) с добавлением этого последнего символа. Если они не совпадают, LCS равна более длинной из LCS строк Х(_n-2_) и Y(_m_) и LCS строк Х(_n_) и Y(_m-1_). Для вычисления этих "меньших" LCS мы рекурсивно вызываем одну и ту же подпрограмму.
Тем не менее, обратите внимание, что для вычисления LCS строк Х(_n-1_) и Y(_m_) может потребоваться вычислить LCS строк Х(_n-2_) и Y(_m-1_), LCS строк Х(_n-1_) и Y(_m-1_) и LCS строк Х(_n-2_) и Y(_m_). Вторую из этих подпоследовательностей можно уже вычислить. При недостаточной внимательности можно было бы вычислять одни и те же LCS снова и снова. В идеале во избежание этих повторных вычислений нужно было бы кешировать ранее вычисленные результаты. Поскольку мы располагаем двумя индексами для строк X и Y, имеет смысл воспользоваться матрицей.
Что необходимо хранить в каждом из элементов этого матричного кеша? Очевидный ответ - саму строку LCS. Однако, это не слишком целесообразно - да, это упростит вычисление LCS, но не поможет определить, какие символы нужно удалить из строки X, а какие новые символы вставить с целью получения строки Y. Лучше в каждом элементе хранить достаточный объем информации, чтобы можно было генерировать LCS за счет применения алгоритма типа O(1), а также достаточный объем информации для определения команд редактирования, обеспечивающих переход от строки X к строке Y.
Один из информационных элементов, в котором мы действительно нуждаемся, -это длина LCS на каждом этапе. Используя упомянутое значение, с помощью рекурсивного алгоритма можно легко выяснить длину LCS для двух полных строк. Чтобы можно было сгенерировать саму строку LCS, необходимо знать путь, пройденный по матричному кешу. Для этого в каждом элементе потребуется сохранять указатель на предыдущий элемент, который был использован для построения LCS для данного элемента.
Однако прежде чем приступить к рассмотрению просмотра матрицы LCS, необходимо ее построить. Пока же будем считать, что в каждом элементе матрицы будут храниться два информационных фрагмента: длина LCS на данном этапе и позиция предыдущего элемента матрицы, образующего предшественницу этой LCS. Для последнего значения существует только три возможных ячейки: непосредственно над ним (к северу), слева (к западу) и выше и левее (к северо-западу). Поэтому для их обозначения вполне можно было бы использовать перечислимый тип.