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

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

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

for (i=0; i

  if (… s[i]…)…

}

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

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

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

n=strlen(s);

for (i=0; i

   if (… s[i]…)…

}

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

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

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

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

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

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

Многословный журнал лишит вас сна Йоханнес Бродуолл