Этого наброска оказалось достаточно, чтобы программист решил свою задачу. Некоторые из особенностей реализации, с которыми он столкнулся, описаны в задачах 1, 2 и 6 в конце данной главы.
1.5. ОСНОВНЫЕ ПРИНЦИПЫ
Мой собеседник рассказал мне о своей задаче по телефону. Нам потребовалось около 15 мин, чтобы разобраться в особенностях задачи и найти решение с побитовым представлением. Написание программы из нескольких десятков строк на Фортране заняло у него пару часов. Это было неплохо по сравнению с сотнями строк и неделей программирования, чего мы боялись в начале телефонного разговора. Программа работала молниеносно: в то время как программа сортировки слиянием на диске могла бы работать несколько минут, эта программа затрачивала ненамного больше времени, чем требуется для чтения входных данных и записи выходных, - менее 10 с.
В этих фактах содержится первый урок, извлекаемый из рассмотрения данного случая: тщательный анализ небольшой задачи может иногда лринести потрясающую практическую пользу. В данном примере тщательное изучение в течение нескольких минут привело к сокращению на порядок числа операторов в программе, времени программирования и времени прогона. Генерал Ч. Йегер (первый человек, полетевший со сверхзвуковой скоростью) похвалил двигательную установку самолета следующими словами: "Проста, мало деталей, легко обслуживать, очень прочная". Эти эпитеты относятся и к нашей программе. Однако может оказаться, что специфические структуры данной программы будет тяжело модифицировать при изменении объемов некоторых данных. Являясь рекламой искусного программирования, этот пример иллюстрирует следующие общие принципы.
Правильная постановка задачи. Наш спор почти целиком был посвящен формулировке задачи. Я рад, что программист не успокоился на первой программе, которую я ему описал. Задачи 9 и 10 имеют элегантные решения, если вы правильно их сформулируете. Хорошенько подумайте над ними, прежде чем смотреть подсказки и решения.
Побитовая структура данных. Эта структура данных представляет собой компактное отображение конечного набора данных для случая, когда каждый элемент встречается не более одного раза и с ним не связано никаких других данных. Даже если эти условия не удовлетворяются (имеются повторяющиеся элементы или дополнительные данные), ключ, полученный с помощью этого отображения, может быть использован в качестве ссылки на адрес в таблице, содержащей более сложные входные данные.
