День восемьсот семьдесят девятый. #Оффтоп #97Вещей
97 Вещей, Которые Должен Знать Каждый Программист
89. Используйте Правильные Алгоритмы и Структуры Данных
Большой банк с множеством филиалов жаловался, что новые компьютеры, которые он закупил для кассиров, слишком медленные. Это было ещё до того, как все начали использовать онлайн банки, а банкоматы не были так широко распространены, как сейчас. Люди ходили в банк гораздо чаще, а из-за медленных компьютеров выстраивались очереди. Тогда банк пригрозил разорвать контракт с поставщиком.

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

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] …) …
}

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

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

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

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

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

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

Так что читайте умные книги и разбирайтесь в том, что там написано. А если вы действительно прочитали Дональда Кнута «Искусство программирования» и смогли найти ошибку у автора, то можете получить один из его шестнадцатеричных долларов.

Источник: https://www.oreilly.com/library/view/97-things-every/9780596809515/
Автор оригинала – Jan Christiaan “JC” Van Winkel