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

Бакнелл Джулиан М.

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 и -"лэтс гоу", то бишь, за дело.)

Предупреждаю, что эта книга далеко не исчерпывающая. Когда я планировал ее написание, мне пришлось опустить больше материала, чем я смог осветить ("А чего ж ты не рассмотрел B-деревья, Юлиан?"). Угу... Так уж получилось... Прочтите книгу, а затем двигайтесь дальше, и постарайтесь выяснить, что еще написано по той или иной теме.

Список литературы

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

1. Abramowitz, Milton, and Irene A. Stegun. Handbook of Mathematical Functions. Dover Publications, Inc., 1964.

2. Aho, Alfred V., Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and

Tools. Addison-Wesley, 1986.

3. Beck, Kent. Extreme Programming Explained. Addison-Wesley, 2000.

4. Binstock, Andrew, and John Rex. Practical Algorithms for Programmers. Addison-Wesley, 1995.

5. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. MIT Press, 1990.

6. Folk, Michael J., and Bill Zoellick. File Structures. 2nd Ed. Addison-Wesley, 1992.

7. Guibas L.J., and R. Sedgewick. "A dichromatic framework for balanced trees." Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978.

8. Jones, Douglas W. "Application of Splay Trees to Data Compression." Communications of the ACM, Vol. 31 (1988), pp. 996-1007.

9. Kane, Thomas S. The New Oxford Guide to Writing. Oxford University Press, 1988.

10. King, Stephen. On Writing. Scribner, 2000.

11. Knuth, Donald E. The Art of Computer Programming: Fundamental Algorithms. 3rd Ed. Addison-Wesley, 1997.

12. Knuth, Donald E. The Art of Computer Programming: Seminumerical Algorithms. 3rd Ed. Addison-Wesley, 1998.

13. Knuth, Donald E. The Art of Computer Programming: Sorting and Searching. 2nd Ed. Addison-Wesley, 1998.

14. L"Ecuyer, Pierre. "Efficient and Portable Combined Random Number Generators." Communications of the ACM, Vol. 31 (1988), pp. 742-749, 774.

15. Nelson, Mark. The Data Compression Book. M& T Publishing, 1991.

16. Park, S.K., and K.W. Miller. "Random Number Generators: Good Ones are Hard to Find." Communications of the ACM, vol. 31 (1988), pp. 1192-1201.

17. Pham, Thuan Q. and Pankaj K. Garg. Multithreaded Programming with Win32. Prentice Hall, 1999.

18. Pugh, William. "Skip Lists: A Probabilistic AItemative to Balanced Trees." Communications of the ACM, Vol. 33 (1990), pp. 668-676.

19. Robbins, John. Debugging Applications. Microsoft Press, 2000.

20. Sedgewick, Robert. Algorithms. 2nd Ed. Addison-Wesley, 1988.