Читать онлайн «Искусство программирования для Unix». Страница 178

http://www.cs.yorku.ca/~oz/wily

http://plan9.bell-labs.com/sys/doc/acme/acme.html

⁸³ формуле: An + с, где А — некоторый неизвестный постоянный коэффициент пропорциональности, а С — неизвестная константа, представляющая время установки. Линейный поиск определенного значения в списке представляет собой алгоритм типа О (и). Алгоритм О(п') выполняется за время An' плюс величина более низкого порядка (которая может быть линейной либо логарифмической или любой другой функцией ниже квадратичной). Поиск повторяющихся значений в списке (примитивным методом, без сортировки списка) является алгоритмом О(п'). Аналогично, алгоритмы порядка О(п') имеют среднее время выполнения, вычисляемое по кубической формуле. Такие алгоритмы часто слишком медленны для практического применения. Порядок О (log п) типичен для поиска по дереву. Взвешенный выбор алгоритма часто может сократить время выполнения с 0(п') до О (log п). Иногда, когда требуется рассчитать использование алгоритмом памяти, можно заметить, что оно изменяется как O(l) или О (я), или О(п). Как правило, алгоритмы с использованием памяти О(п') или более высокого порядка являются непрактичными.

2 Удвоение мощности в течение каждых 18 месяцев, обычно цитируемое в контексте закона Мура, подразумевает, что можно достичь 26% прироста производительности просто путем приобретения нового аппаратного обеспечения через 6 месяцев.

Молодые читатели могут не знать, что раньше терминалы печатали (на бумаге и очень медленно).

⁸⁴  Термины, введенные здесь для обозначения проблем проектирования, происходят из устоявшегося жаргона хакеров, описанного в книге £66].

⁸⁵  Разделение случайной и необязательной сложности означает, что рассматриваемые здесь категории не являются тем же, что сущность и случайность в очерке Фреда Брукса "No Silver Bullet" [8], однако в философском смысле они имеют одинаковое происхождение.

⁸⁶  http://plan9.bell-labs.com/sys/doc/sam/sam.html

⁸⁷  Разработчиками Emacs были Ричард М. Столлмен (Richard М. Stallman) и Берии Гринберг (Bcrnie Greenberg). Первоначальный редактор Emacs был изобретением Столлмена, первая версия со встроенным языком Lisp была создана Гринбергом, а окончательная на сегодняшний день версия создана Стол-лменом на основе версии Гринберга. К 2003 году нет полного изложения истории разработки редактора, но эту тему освещает статья Гринберга "Multics Emacs: The History, Design, and Implementation", которую можно найти в Web но ключевым словам.

⁸⁸  За пределами мира Unix этот прирост аппаратной производительности на три порядка в значительной мере затмевается соответствующим понижением производительности программ.

⁸⁹  ерьезность данной проблемы подтверждается богатым сленгом, выработанным Unix-програм-мистами для описания различных ее разновидностей: "псевдонимная ошибка" (aliasing bug), "нарушение выделенной области памяти" (arena corruption), "утечка памяти" (memory leak), "переполнение буфера" (buffer overflow), "разрушение стека" (stack smash), "отклонение указателя" (fandango on core), "недействительный указатель" (stale pointer), "подкачка памяти" (heap trashing), а также вызывающее справедливые опасения "вторичное повреждение" (secondary damage). Пояснения приведены в Словаре хакера chttp: / /www.catb.org/-esr/jargon>.

⁹⁰  Последний стандарт С++, датированный 1998 годом, был широко распространенным, но слабым, особенно в области библиотек.

⁹¹  См. очерк Тома Кристианссна (Tom Christiansen) "Csh Programming Considered Harmfulкоторый можно легко найти в Web.

⁹²  Существует Web-сайт проекта Freenet chttp://£reenetproject. org>.

⁹³  URL-запроса для получения статистических данных: <http: //sourcef orge. net/sof twaremap/ trove_list.php?form_cat=160>.

⁹⁴  Распространенное более новое описание языка Perl как "швейцарской бензопилы" является производным.

⁹⁵  PLY можно загрузить со страницы <http: //systems. cs. uchicago. edu/ply/ >.

⁹⁶  Пакет CUP доступен на странице <http: //www. cs .princeton. edu/-appel/modern/java/CUP>.

⁹⁷  Пакет Jack доступен на странице <http://www.javaworld.com/javaworld/jw-12-1996/ j w-12-jack, html >.

⁹⁸  Пакет Yacc/M доступен на странице <http://david.tribble.com/yaccm.html>.

⁹⁹  http://cm.bell-labs.com/cm/cs/upe/

¹⁰⁰  Блочный тест представляет собой тестовый код, прикрепленный к модулю для проверки корректности представления. Использование термина "блочный тест" подразумевает, что тест написан разработчиком одновременно с основным кодом и означает порядок, при котором версии модуля не считаются завершенными до тех нор, пока к ним не прикреплен тестовый код. Данный термин и идея возникли в методологии "Экстремального программирования", популяризированной Кентом Беком (Kent Beck), но получили широкое распространение среди Unix-программистов примерно с 2001 года.

¹⁰¹  Более подробная информация по данным и родственным командам управления компиляцией приведена в справочном мешо Emacs: p+processes- >compile.

¹⁰²  Подробнее эти и родственные команды описываются в подразделе справочной системы Emacs, озаглавленном Version Control (Управление версиями).

¹⁰³  Агентство NASA, в котором целенаправленно создавалось программное обеспечение, предназначенное для использования в течение десятилетий, научилось настаивать на доступности исходного кода для всех создателей программного обеспечения для аэрокосмической техники.

¹⁰⁴  Обе системы PDP-7 Unix и Linux стали примерами "неожиданной живучести". Unix в качестве "игрушки для опытов" была создана несколькими исследователями в перерывах между основными проектами. Наполовину она была предназначена для экспериментов с файловой системой и наполовину для поддержки компьютерной игры. Linux была охарактеризована своим создателем как "мой эмулятор терминала с выросшими ногами" 85]

¹⁰⁵  Таким образом, литера "С" в названии языка С означает Common (общий) или, возможно, "Christopher". Аббревиатура BCPL первоначально расшифровывалась как "Bootstrap CPL" — сильно упрощенная версия языка CPL, весьма интересного, но слишком претенциозного языка общего программирования (Common Programming Language) Оксфордского и Кембриджского университетов, также называемого "языком программирования Кристофера" (Christopher Programming Language) по имени его главного пропагандиста, первопроходца компьютерной науки Кристофера Стрэчи (Christopher Strachey).

¹⁰⁶  Документ доступен в Web: <http: //anubis. dkuug. dk/JTC1/SC22/WG14/www/charters

¹⁰⁷  Первоначальный пробный стандарт в 1985 году назывался IEEE-IX. Название "POSIX" было предложено Ричардом Столлменом. Введение в POSIX.1 гласит "Ожидается произношение "поз-икс" как "позитив", а не "по-сикс" или в других вариантах. Произношение опубликовано в целях обнародования стандартного способа ссылки на стандартный интерфейс операционной системы".

¹⁰⁸  Один Linux-дистрибьютор, а именно Лазермун (Lasermoon) из Великобритании, добился сертификации POSIX. 1 FIPS 151-2, но вышел из бизнеса, поскольку потенциальных клиентов сертификация не интересовала.

¹⁰⁹  Эта тема обсуждается в книге "Just for Fun " 85]

¹¹⁰  Web-поиск, вероятно, предоставит популярную страницу, на которой сатирически описывается семиуровневая модель OSI сравнивается.