Фундаментальные алгоритмы и структуры данных в Delphi [Джулиан М. Бакнелл] (fb2) читать постранично, страница - 205

нуля, данная ячейка является первой ячейкой матрицы LCS, поэтому подпрограмма просто выполняет выход}

if (aFromInx = -1) and (aToInx = -1) then

Exit;

{если индекс строки From меньше нуля, ячейка расположена в левом столбце матрицы, поэтому необходимо переместиться вверх; этому будет соответствовать удаление}

if (aFromInx = -1) then begin

slWriteChange(F, aFromInx, aToInx-1);

writeln(F, '->', FToFile[aToInx]);

end

{если индекс строки To меньше нуля, ячейка расположена в верхней строке матрицы, поэтому необходимо переместиться влево; этому будет соответствовать вставка}

else

if (aToInx = -1) then begin

slWriteChange(F, aFromInx-1, aToInx);

writeln(F, '<-', FFromFile[aFromInx]);

end

{в противном случае необходимо выполнить действия, указанные ячейкой}

else begin

Cell := FMatrix[aFromInx, aToInx];

case Cell^.ldPrev of

ldNorth :

begin

slWriteChange(F, aFromInx-1, aToInx);

writeln(F, '<-', FFromFile [aFromInx]);

end;

ldNorthWest : begin

slWriteChange(F, aFromInx-1, aToInx-1);

writeln(F, 1 ', FFromFile[aFromInx]);

end;

ldWest : begin

slWriteChange(F, aFromInx, aToInx-1);

writeln(Ff FToFile[aToInx]);

end;

end;

end;

end;

procedure TtdFileLCS.WriteChanges(const aFileName : string);

var

F : System.Text;

begin

System.Assign(F, aFileName);

System.Rewrite(F);

try

slWriteChange (F, pred(FFromFile.Count), pred(FToFile.Count)) finally

System.Close(F);

end;

end;

Резюме

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

Применительно к многопоточным приложениям, мы рассмотрели решение проблемы синхронизации потоков считывания-записи - алгоритма, который играет большую роль во множестве программ подобного рода. Применительно к проблеме использования потоков производителей-потребителей, мы рассмотрели алгоритм, который может применяться во многих ситуациях, когда большие объемы данных должны одновременно обрабатываться, причем различным образом.

Алгоритм определения наиболее длинной общей подпоследовательности (LCS) является более специализированным, но находит применение в системах управления исходным кодом, а также в качестве программ наподобие diff.

Эпилог

Если быть кратким, написание этой книги явилось интересным опытом (а также работой, попортившей немало кровушки).

В течение долгих лет я считал, что Delphi, Visual Basic, а теперь и Kylix, порождали, порождают и будут порождать программистов, которые не имеют ни малейшего представления об этом занятии. Да, они могут создавать приложения простым перетаскиванием, с использованием небольшого объема связующего кода и нескольких обработчиков событий. Тем не менее, любое приложение, достойное того, чтобы его создавать, требует определенного мастерства, опыта и теоретической подготовки, которые могут быть предоставлены традиционными компьютерными науками и программированием. Конечно, при создании программы можно немало напутать, и, тем не менее, программа таки будет работать. Однако различие будет столь же разительным, как и различие между яйцом, сваренным вкрутую, и яйцом Фаберже.

Должен признать, что вся моя теоретическая подготовка в компьютерной области была получена в результате самообразования. Я получил ученую степень по математике в Королевском колледже при Лондонском университете. Во время учебы мне довелось прослушать единственный курс по программированию - программированию на языке FORTRAN, программы которого, хранящиеся в виде колод перфокарт, были предвестниками сегодняшнего расцвета компьютерных технологий - но насколько я помню, не предпринималось никаких реальных попыток обучения студентов строгим компьютерным наукам. (В те времена не приходилось говорить и о немедленном получении результатов, столь привычном для современного программирования на ПК). Мне пришлось полюбить просматривать длинные листинги программ на языке, который не поддерживал ни локальных переменных, ни указателей. Тем не менее, это меня не остановило. Я начал исследовать и изучать все эти премудрости. Долгими часами я мучился, пытаясь усвоить язык MIX, разработанный Кнутом (Knuth), С и иже с ними. Я пытался извлечь практическую пользу из учебников, которые оставляли реализацию операции Delete в качестве упражнения 4.25. Смею заверить, что все это - совершенно чудесный способ изучения языка.

Готов поспорить, что если вам стали известны доступные возможности языка, с которым вы более всего знакомы, то вы будете знать, следует ли при решении следующей задачи использовать хеш-таблицу или отложить клавиатуру и вычертить блок-схему конечного автомата, или, быть может, создать еще один экземпляр объекта списка TList. Именно в этом и состоит главная цель данной книги -показать читателям, чего можно добиться, если известны доступные возможности. Основное назначение кода, приведенного в книге - его непосредственное использование. (Вам требуется вычислитель регулярных выражений? Тогда воспользуйтесь кодом, разработанным нами в главе 10. Добавьте модуль в список uses и -"лэтс гоу", то бишь, за дело.)

Предупреждаю, что эта книга далеко не исчерпывающая. Когда я планировал ее