Используйте правильные алгоритмы и структуры данных

(В оригинале - Use the Right Algorithm and Data Structure)

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

Поставщик отправил в банк специалиста, чтобы тот нашел причину медленной работы. Он очень быстро обнаружил, что одна из программ расходует практически 100% процессорного времени. При помощи профайлера он нашел «виновную» функцию, в которой было следующее:

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

Практически все слышали фразу «сначала сделай так, чтобы работало, потом делай, чтобы работало быстро», предотвращающую ненужную оптимизацию. Однако приведенный выше пример скорее следует правилу «сначала сделай так, чтобы работало медленно».

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

Другая сторона выбора правильного алгоритма – выбор структуры данных. Использование связанного списка для хранения миллиона записей с необходимостью поиска вместо использования хеш-таблицы или двоичного дерева доставят много неприятных минут пользователю вашего ПО.

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

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

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

Автор оригинала - JC van Winkel