Бинарный алгоритм поиска так же красив, как скульптура Праксителя, как мост Золотые Ворота, как Декларация о независимости, как Smalltalk, как Собор Св. Петра
Красота в программировании важнее, чем в какой-либо другой технологии, поскольку программное обеспечение отличается чрезвычайной сложностью, от которой лучшая "защита" - все та же красота.

Красота. Красота как мера всех вещей. Слово, вызывающее пренебрежение у простаков и уважение у мудрых. Летает только красивый самолет. Красивая программа лучше работает. Она эффективнее, дружелюбнее, удобнее.

Красота - это еще и то, о чем в первую очередь забывают разработчики программного обеспечения. Таково, по крайней мере, мнение профессора вычислительной техники из Йельского университета Дэвида Гелернтера, высказанное в книге Machine Beauty - Elegance and the Heart of Technology (несколько вольный перевод этого названия - "Машина как сочетание красоты и технологичности" - Прим. пер.). Он пишет: "Красота в программировании важнее, чем в какой-либо другой технологии, поскольку программное обеспечение отличается чрезвычайной сложностью, от которой лучшая "защита" - все та же красота". При этом, как ни удивительно, становясь менее сложным, продукт не оказывается менее эффективным.

Мнение Гелернтера полностью разделяют разработчики: продукты, имеющие максимально простую структуру и алгоритмы, на поверку оказываются наиболее мощными.

Красота программы - понятие вполне, если можно так выразиться, прагматическое. Уитфилд Диффи, один из разработчиков простого и эффективного метода кодирования открытым ключом, занимающийся научно-техническими исследованиями в компании Sun Microsystems, утверждает: "Программа должны быть понятной - это ее первейшее достоинство. По всеобщему представлению, программа становится красивой, когда она хорошо организована".

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

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

Один из них, Алан Кей, вице-президент по исследованиям и развитию компании The Walt Disney, который, без сомнения, стоял у самых истоков программирования, считал образцом для подражания Конституцию Соединенный Штатов. Кей утверждал, что она прекрасна, потому что проста и вместе с тем способна выдержать проверку временем. "Я рекомендую вступительную статью к Конституции в качестве руководства по проектированию систем, - говорит Кей. - Здесь предельно четко сформулировано, почему Конституция построена именно таким образом. Это не что иное, как инструкция по созданию машины, рассчитанной на бесперебойную работу в течение нескольких сотен лет".

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

В 1973 году Кей принимал участие в работе группы, спроектировавшей первый в мире персональный компьютер. На этой машине работал Smalltalk - один из элегантнейших объектно-ориентированных языков, изобретенный все тем же Кеем.

В компании American Management Systems трудятся 2300 программистов, и самый талантливый из них, по общему признанию, - Томас Сорджи. Программное обеспечение обработки транзакций на базе Web для сложных банковских приложений - дело его рук. Его программа должна работать на клиентских машинах удаленных пользователей, а не на больших корпоративных серверах, то есть Сорджи вынужден довольствоваться лишь небольшой полосой пропускания, ограниченным дисковым пространством и малой вычислительной мощностью. "Одним словом, разгуляться негде", - говорит Сорджи.

Однако это не стало препятствием для талантливого разработчика. Пользуясь C++ и Java, он создал сложное приложение для обработки аккредитивов, полностью экипированное средствами защиты и генерации отчетов и занимающее всего 450 Кбайт - меньше половины емкости стандартной дискеты. Выполнявшая аналогичные действия система для Windows, созданная в PowerBuilder компании Powersoft, требовала для начала работы ни много ни мало - 30 Мбайт.

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

Сорджи завораживает красота программ во всех ее проявлениях, "ритм чередования строк программы, организация экрана, логика имен".

"Одна и та же программа может иметь сотни обличий, - утверждает астроном, популяризатор и большой поклонник вычислительной техники Клиффорд Столл. - Она может быть создана методом грубой силы, может быть шикарной, изящной, элегантной, может носить следы спешки, легкомыслия разработчика и даже смертельной скуки".

Вот продукты, которые Столл ценит больше всего.

  • Web. Не нужно пересылать мегабайтные файлы от адресата к адресату - достаточно сообщить URL.
  • Электронные таблицы Visicalc. Это по-настоящему элегантное решение, прекрасное и модное. Они просуществовали почти два десятилетия, не претерпев почти никаких изменений.
  • Карманный компьютер PalmPilot корпорации 3Com. В некотором смысле он походит на записную книжку респектабельного делового человека - элегантность и ни одного изъяна.

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

"Microsoft Office 98 - это все равно что швейцарский армейский нож со 145 лезвиями, - сетовал инженер. - Пройдет неделя, пока наткнешься наконец на пилку для ногтей. Мне не нужны 99% возможностей этого продукта, а вычислительных ресурсов он пожирает массу, да еще представляет собой благодатное поле для всяческих ошибок".

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

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

Программист компании Lucent Technologies и автор книги Programming Pearls ("Жемчужины программирования") Йон Бентли считает, что "научиться" элегантности можно, подражая лучшим образцам и неустанно тренируясь. Он рекомендует разработчикам вникать в коды лучших представителей этой профессии и анализировать, как они были созданы.

"Элегантность - вот к чему надо постоянно стремиться, принимая фундаментальные архитектурные решения, которые будут распространяться на многие продукты и приложения, - уверен Уильям Шерлис, профессор вычислительной техники Университета Карнеги - Меллона. - Впрочем, увлекаться не следует. Наводя глянец на какую-нибудь малюсенькую программку можно так увлечься, что пострадает большая система".

В заключение я бы привел слова Пенсака, который советует программистам побольше думать и поменьше программировать: "Какой код разрабатывать быстрее всего? Да тот, который не нужно записывать!"


Гэри Антес - редактор Computerworld. Его адрес gary_anthes@cw.com

Поиск изящного - изящный поиск

"Бинарный поиск неизменно производит ошеломляющее впечатление на новичков, - говорит Уильям Шерлис из Университета Карнеги - Меллона. - Кажется невероятным, как такой маленький алгоритм может быть настолько мощным".

Он позволяет найти элемент или ключ в упорядоченном списке. Допустим, нужно найти цифру 7 в следующей последовательности 1, 3, 4, 6, 7, 9, 10, 11, 13, 14, 16, 18, 22. Можно применить "наивный", по выражению Шерлиса, алгоритм, то есть просмотреть все элементы по порядку. В худшем случае придется перебрать все элементы, как правило, получается около половины. Алгоритм бинарного поиска предлагает начать с середины списка. Если при этом выбирается искомое число - поиск закончен, в противном случае определяется соотношение искомого числа и того, которое оказалось в середине списка. Если, как в данном примере, первое число меньше (7 < 10), поиск ограничивается первой половиной списка, в противном случае - второй. Процесс продолжается до тех пор, пока не будет найден искомый элемент или не обнаружится, что его нет в списке.

В данном примере ключ был найден с третьей попытки. При поиске по списку из 1000 элементов наивный поиск требует перебора в среднем 500, а бинарный - всего 10 элементов. Для списка из 500 тыс. элементов данный показатель составляет 30. "Элегантность этого алгоритма не только в простоте и скорости, но в своего рода универсальности. Можно предложить множество подобных алгоритмов для аналогичных задач", - пояснил Шерлис.

- Гэри Антес

Поделитесь материалом с коллегами и друзьями