97 этюдов для программистов. Опыт ведущих экспертов - Пит Гудлиф

Lego: вы создаете собственные команды, просто комбинируя маленькие, но универсальные утилиты UNIX. К примеру, следующая последовательность представляет собой текстовую реализацию анализа сигнатуры по Каннингему — последовательность использования точки с запятой, фигурных скобок и кавычек в любом файле может многое сказать о его содержимом:

for i in *.java; do

   echo — n "$i: "

   sed ’s/[~"{};]//g' $i | tr — d 'n'

   echo

done

Далее, каждая изученная вами операция IDE специфична для данной задачи, например добавление нового шага в конфигурацию отладочной сборки проекта. Напротив, более глубокое изучение утилит UNIX повышает вашу эффективность при решении любых задач. Например, я применил утилиту sed, использованную в приведенной выше последовательности команд, чтобы преобразовать процедуру сборки проекта для кросскомпиляции на многопроцессорных архитектурах.

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

grep ‘ <revision>’ | wc — l

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

Принцип «прекрасное в малом» и открытость реализаций утилит UNIX делают их доступными повсеместно, даже на платформах с ограниченными ресурсами, таких как медиа-проигрыватель, подключаемый к телевизору, или маршрутизатор DSL. Такие устройства едва ли располагают мощным графическим интерфейсом пользователя, но часто содержат приложение BusyBox, предлагающее наиболее часто используемые утилиты. Если вы занимаетесь разработкой под Windows, среда Cygwin предложит вам все мыслимые утилиты UNIX как в виде исполняемых файлов, так и в виде исходного кода.

Наконец, если вас не удовлетворяют существующие утилиты UNIX, вы можете легко расширить их набор. Напишите программу, которая решает нужную вам задачу, на любом понравившемся вам языке, соблюдая следующие простые правила: программа должна выполнять одну единственную задачу, читать данные со стандартного ввода в виде строк текста и печатать результат на стандартный вывод без всяких заголовков и прочих украшательств. Параметры, влияющие на функционирование утилиты, задаются в командной строке. Следуйте этим правилам, и тогда «Земля — твое, мой мальчик, достоянье».

Правильно выбирайте алгоритмы и структуры данных

Ян Кристиаан ван Винкель

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

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

for (i=0; i<strlen(s); ++i) {

  if (… s[i]…)…

}

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

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

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

n=strlen(s);

for (i=0; i<n; ++i) {

   if (… s[i]…)…

}

Всем известен принцип «сделай так, чтобы код работал, потом сделай так, чтобы он работал быстро», который направлен против оптимизаций на микроуровне. Но по приведенному примеру можно решить, что программист исполнил макиавеллевское адажио «сначала сделай так, чтобы код работал медленно».

Подобная бездумность встречается, и нередко. И дело не только в том, что не нужно «заново изобретать колесо». Иногда молодые программисты бросаются, не особо раздумывая, писать код и вдруг «изобретают» пузырьковую сортировку. При этом они, случается, еще и хвастают этим.

Обратной стороной выбора правильного алгоритма является выбор структуры данных. Этот выбор может серьезно повлиять на скорость работы: если для хранения коллекции в миллион объектов, по которой нужно выполнять поиск, вы используете связный список — а не структуру с хешированием данных либо двоичное дерево, — пользователю найдется что сказать насчет вашего умения программировать.

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

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

Поэтому прочтите несколько хороших книг — и хорошенько в них разберитесь. А если вы глубоко изучите «Искусство программирования» Дональда Кнута, вам может даже повезти: найдите у автора ошибку, и вы получите от него чек на один шестнадцатеричный доллар ($2.56).

Многословный журнал лишит вас сна

Йоханнес Бродуолл

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