Все новости от 1 февраля 2001 г.

Теория, подкрепленная практикой

Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы. Пер. с англ. А. А. Минько. Изд-во "Вильямс", 2000. - 384 с.

Книг, посвященных различным типовым алгоритмам программирования, выходит довольно много. Большинство из них, правда, обладает существенным недостатком - в них поверхностно и без привязки к особенностям компьютерной реализации рассматриваются достаточно простые алгоритмы и структуры данных (например, списки и деревья), которые прикладным программистам сегодня интересны только в общепознавательном смысле.

В состав современных систем быстрой разработки (например, Visual C++, Delphi, Java-среды) уже давно входит богатый набор готовых библиотек, шаблонов, классов, предоставляющих средства работы практически со всеми более-менее востребованными структурами данных. А книги по алгоритмам различаются подчас только стилем изложения и используемым в примерах языком программирования.

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

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

Читатель быстро осознает, насколько важно грамотно проектировать будущую структуру программы и как сильно может повлиять неверно сформулированный или плохо реализованный алгоритм на производительность будущего приложения.

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

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

Рассказано о сложных множествах, которые используются, например, в СУБД для представления отношений "многие-ко-многим". В отдельной главе описываются способы организации эффективной работы с большими множествами.

Пятьдесят страниц посвящено вопросам, связанным с ориентированными и неориентированными графами, алгоритмами их реализации, анализа и обхода. Есть глава, рассмотривающая различные методы сортировки и способы выбора лучшего алгоритма. Не обойдены вниманием методы разработки и анализа алгоритмов. Разбираются математические и эвристические подходы, способы поиска оптимальных решений и конкретные примеры.

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

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

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

Каждая глава дополнена заданиями разной сложности. Наиболее трудные задачи несут прикладную полезность и сопровождаются рекомендациями и подсказками.

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

Мелкие неточности перевода (например, "kill character", традиционно переводимый как стоп-символ, калькируется как "символ-убийца") общей ценности книги не снижают.