являются задачами гигантского размера. Поэтому, для того чтобы использовать в своей книге интересные примеры, мне приходится писать программы, решающие задачу таким образом, чтобы заставить читателя подумать: “О да, я бы не смог решить эту задачу с помощью обычных методов, поэтому мне нужно кое-что узнать об искусстве программирования, иначе у меня уйдет сотня лет на решение этой задачи с помощью метода грубой силы”.

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

Около года назад я прочитал обзор в журнале “Computing Reviews” - рецензент писал о книге под названием “Programming Tricks” (Уловки в программировании) или что-то вроде того. Суть рецензии сводилась к следующему: “Если бы я узнал, что кто-то из программистов, работающих на меня, применяет эти штучки, я бы их уволил”. Естественно, я начал искать эту книгу, подумав: “Именно такая книга мне и нужна - в ней я могу узнать для себя много нового”. К сожалению, уловки не были такими уж хорошими.

Сейбел: Они что, действительно причиняли вред?

Кнут: Вообще-то, это были очень слабые и неэффективные уловки. Они не были систематизированы и все такое, но самое главное - они были достаточно очевидны. Это была совершенно иная культура. Что же касается рецензента, который собирался увольнять своих сотрудников, - он хочет, чтобы в программировании все делалось неэффективно, но вписывалось бы в его идею аккуратности. Его абсолютно не интересует, хороша программа или нет - если брать в расчет скорость исполнения и производительность; он думает лишь о том, чтобы она соответствовала другим критериям, - например, чтобы ее поддержку мог осуществлять абсолютно любой человек. Что ж, у многих вообще очень странные взгляды на действительность.

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

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

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

Люди же, наоборот, все засовывают в упаковку, которую не открыть, и преподносят эту закрытую упаковку программистам, и всем программистам во всем мире не разрешается вскрывать эту упаковку. Они только и могут что соединять одно с другим. И поэтому приходится помнить, что, вызывая вот эту подпрограмму, нужно ввести х0, у0, х1, у1, а при вызове другой подпрограммы нужно ввести х0, х1, у0, у1. Все выполняется строго по инструкции - и это ваша работа.

Сейбел: Многие с вами согласятся, что, да, интереснее писать код самому. Но помимо увлекательности есть еще и...

Кнут: Дело не только в том, что это интересно. Работа математика заключается в том, чтобы писать доказательства, но практически никогда не бывает так, что в процессе решения математической задачи вы можете найти теорему, чьи гипотезы абсолютно идеально подходят для вашего случая. Практически всегда вы работаете с тем, что более или менее похоже на классическую теорему из учебника. Поэтому, что вы делаете? Читаете доказательство этой теоремы и думаете: “Ага, вот как мне нужно изменить это доказательство, чтобы доказать гипотезу, которой я занимаюсь”. То есть в математических книгах полно теорем, но вы никогда не берете всю теорему от начала до конца - вам нужно увидеть ее доказательство, потому что лишь в одном случае из ста вы сможете найти теорему, которая идеально подходит для вашей задачи. Думаю, примерно так же дело обстоит и с ПО.

Сейбел: И тем не менее, не является ли ПО - по-моему, вы сами же об этом и говорили - самой сложной вещью, когда-либо созданной человеком?

Кнут: По-моему, Дейкстра сказал это первым, но, вообще, да, все верно. Все дело в том, что сложность соединения разных вещей далеко не однородна. В чистой математике стремятся к тому, чтобы выработать небольшое количество правил, которые можно было бы применять ко всем явлениям - 3 -4 аксиомы для описания целой системы. В компьютерной же программе множество частей: шаг 1 не похож на шаг 2, а тот, в свою очередь, не похож на шаг 3. Вам нужно соединить все эти вещи и организовать весьма нетривиальным способом.

Сейбел: Таким образом, учитывая сложность, получается, что в какой-то момент нужно взять ряд черных ящиков и сказать: “Ага, мы знаем, как эта штука работает, и можем ею пользоваться”. Если бы нам пришлось заглядывать внутрь каждого черного ящика, мы бы никогда не смогли ничего довести до конца.

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

Сейбел: Медленнее - вы имеете в виду работу программы или ее разработку?

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

Сейбел: Какое-то время назад программист, писавший стандартные библиотеки Java, написал статью о том, как в их реализации двоичного поиска на протяжении девяти лет была ошибка. То есть они взяли минимум и максимум, сложили их и разделили на два. Но, естественно, если операция сложения переполняется, то это ошибка. В общем, конечно, плохо то, что в стандартной библиотеке была ошибка, но в итоге они нашли ее и устранили. Если бы все сами писали двоичный поиск, то ошибочных двоичных поисков, наверное, было бы больше.

Кнут: Это так. И это лишь один пример из огромного множества. Двоичный поиск - это конкретный пример того, с чего мы начинали наши занятия по программированию в 1970-х. В первый день учебы все писали программы двоичного поиска и сдавали нам, после чего ассистенты их изучали. В результате работали меньше 10% программ. И находилось около 4-6 различных ошибок. Но ни одна из них не имела никакого отношения к переполнению, которое вы упомянули; это новая ошибка - на моих занятиях мы не считали сложение этих двух чисел проблемой.

Вернемся к идее черного ящика. Вы можете спросить, почему же она мне так ненавистна? Мы говорим об арифметических операциях, поэтому предположим, что у нас есть программа для перемножения матриц. У нас есть черный ящик для перемножения матриц, затем мы меняем тип данных - с действительного на комплексный; и теперь у нас есть черный ящик для перемножения комплексных матриц, работа которого занимает 4я³ шагов, а не п³ шагов. Если работа программы с действительным типом данных занимает определенное время t, то работа программы с комплексным типом данных занимает время 4?. Но если вы можете заглянуть внутрь ящика, то вам понадобится лишь 3 операции перемножения матриц с действительным типом данных, а не 4,