Примечание редактора. Скорость и производительность становятся все более важной частью успеха любого программного обеспечения и разработчика, который его написал. В этой части из 97 вещей, которые должен знать каждый программист Дж. К. ван Винкель, который преподает UNIX и языки программирования с 1992 года и теперь делится своими знаниями в качестве члена команды инженеров по обеспечению надежности сайтов Google, а также члена-основателя и ведущего преподавателя SRE. Образовательная команда SRE EDU рассказывает, как избежать ошибок новичков в программировании и позволить пользователям лучше оценить вашу скорость программирования за счет выбора правильных алгоритмов и структур данных.
Мы будем рады узнать ваше мнение об этой статье.
Большой банк с множеством филиалов пожаловался, что новые компьютеры, купленные для кассиров, работают слишком медленно. Это было в то время, когда еще не все пользовались электронным банкингом, а банкоматы не были так распространены, как сейчас. Люди будут посещать банк гораздо чаще, а из-за медленных компьютеров люди выстраиваются в очередь. Следовательно, банк пригрозил разорвать контракт с продавцом.
Поставщик направил специалиста по анализу производительности и настройке, чтобы определить причину задержек. Вскоре он нашел одну конкретную программу, запущенную на терминале, которая потребляла почти все ресурсы процессора. Используя инструмент профилирования, он увеличил масштаб программы и смог увидеть функцию, которая была виновником. Исходный код гласил:
for (i=0; i‹strlen(s); ++i) {
if (… s[i] …) …
}
Строка s в среднем состояла из тысяч символов. Код (написанный банком) был быстро изменен, и кассиры банка жили долго и счастливо.…
РАЗВЕ НЕ ДОЛЖЕН ПРОГРАММИСТ поступить лучше, чем использовать код, который без необходимости масштабируется квадратично?
Каждый вызов strlen обходит каждый из многих тысяч символов в строке, чтобы найти завершающий нулевой символ. Строка, однако, никогда не менялась. Заранее определив его длину, программист мог бы сэкономить тысячи вызовов strlen (и миллионы выполнений циклов):
n=strlen(s);
для (i=0; i‹n; ++i) {
if (… s[i] …) …
}
Всем известна поговорка «сначала заставь работать, потом заставь работать быстро», чтобы избежать ловушек микрооптимизации. Но предыдущий пример почти заставил бы вас поверить, что программист следовал макиавеллиевскому адажио «сначала заставьте его работать медленно».
Это легкомыслие — то, с чем вы можете столкнуться не раз. И дело не только в «не изобретать велосипед». Иногда начинающие программисты просто начинают печатать, не задумываясь, и вдруг «изобретают» пузырьковую сортировку. Возможно, они даже хвастаются этим.
Другой стороной выбора правильного алгоритма является выбор структуры данных. Это может иметь большое значение: использование связанного списка для коллекции из миллиона элементов, в которых вы хотите выполнить поиск, — по сравнению с хешированной структурой данных или двоичным деревом — окажет большое влияние на оценку пользователем вашего программирования.
Программисты не должны изобретать велосипед и должны использовать существующие библиотеки, где это возможно. Но чтобы избежать таких проблем, как у банка, они также должны быть осведомлены об алгоритмах и способах их масштабирования. Неужели современные текстовые редакторы просто радуют глаз, что делает их такими же медленными, как программы старой школы, такие как WordStar в 1980-х? Многие говорят, что повторное использование в программировании имеет первостепенное значение. Однако прежде всего программисты должны знать, когда, что и как повторно использовать. Для этого они должны обладать знаниями предметной области, алгоритмов и структур данных.
Хороший программист также должен знать, когда использовать отвратительный алгоритм. Например, если предметная область требует, чтобы количество элементов не превышало пяти (например, количество кубиков в игре Яхтзи), вы знаете, что всегда должны сортировать не более пяти элементов. В этом случае пузырьковая сортировка может оказаться наиболее эффективным способом сортировки элементов. У каждой собаки свой день.
Итак, прочитайте несколько хороших книг — и убедитесь, что вы их понимаете. И если вы действительно читали Искусство компьютерного программирования Дональда Кнута (Addison-Wesley Professional), что ж, вам может даже повезти: найдите ошибку автора, и вы заработаете одну из наград Дона Кнута. шестнадцатеричные долларовые ($2,56) чеки.
Учитесь быстрее. Копать глубже. Смотрите дальше.
Присоединяйтесь к платформе онлайн-обучения O’Reilly. Получите бесплатную пробную версию сегодня и быстро находите ответы или осваивайте что-то новое и полезное.
"Выучить больше"
Дж. К. ван Винкель — ведущий преподаватель и старший инженер по надежности сайтов в Google. Он также является представителем Нидерландов по стандартизации C++. JC был членом правления Нидерландской группы пользователей Unix (NLUUG) в течение 12 лет, в течение 6 из которых он также был председателем.
