Алгоритмы — это базовые наборы инструкций для компьютера. Они говорят системе, как разбираться в информации, чтобы он, в свою очередь, мог извлечь из нее что-то полезное.
Чем эффективнее алгоритм, тем меньше работы приходится выполнять компьютеру. Несмотря на весь технологический прогресс в оборудовании, и столь обсуждаемую справедливость закона Мура, чистая производительность компьютеров — это только одна сторона медали.
Чуть в стороне можно заметить другую тенденцию: улучшаются алгоритмы, поэтому требуется меньше вычислительной мощности. Хотя эффективность алгоритмов может быть менее заметна, вы обязательно заметите, если ваша привычная поисковая система внезапно станет на одну десятую медленнее, или если перемещение по большим наборам данных будет ощущаться как дорого по пояс в снегу.
Это заставило ученых из Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (CSAIL) задаться вопросом: как быстро улучшаются алгоритмы?
Существующие данные по этому вопросу были, в основном, не точными и состояли из тематических исследований конкретных алгоритмов, которые, как предполагалось, были репрезентативными для более широкого диапазона. Столкнувшись с нехваткой доказательств, команда приступила к обработке данных из 57 учебников и более чем 1110 исследовательских работ, чтобы проследить историю того, когда алгоритмы стали лучше. В некоторых исследовательских статьях прямо сообщалось о том, насколько хороши новые алгоритмы, а другие должны были быть реконструированы авторами с использованием "псевдокода", сокращенных версий алгоритма, описывающих основные детали.
В общей сложности команда рассмотрела 113 "семейств алгоритмов", наборов алгоритмов, решающих одну и ту же проблему, которая была выделена как наиболее важная в учебниках по информатике. Для каждого из 113 команда реконструировала его историю, отслеживая каждый раз, когда предлагался новый алгоритм для решения проблемы, и особо выделяя те, которые были более эффективными. Начиная с 1940-х годов и по настоящее время, группа обнаружила в среднем восемь алгоритмов для каждой семьи, из которых пара улучшила ее эффективность. Чтобы поделиться этой собранной базой знаний, команда также создала ресурс Algorithm-Wiki.org.
Ученые отметили, насколько быстро эти семейства улучшились, сосредоточив внимание на наиболее анализируемой особенности алгоритмов — насколько быстро они могут гарантировать решение проблемы (на компьютерном языке: временная сложность наихудшего случая). То, что было выявлено, было огромным разнообразием, но также и важным пониманием того, как преобразующее совершенствование алгоритмов было для информатики.
Что касается крупных вычислительных задач, то у 43 процентов семейств алгоритмов из года в год были улучшения, которые были равны или превышали широко разрекламированные выгоды от закона Мура. В 14 процентах проблем улучшение производительности алгоритмов значительно опережало улучшение производительности, связанное с оборудованием. Выгоды от улучшения алгоритмов были особенно велики для задач с большими данными, поэтому важность этих достижений в последние десятилетия возросла.
Самое большое изменение, которое наблюдали авторы, произошло, когда семейство алгоритмов перешло от экспоненциальной к полиномиальной сложности. Количество усилий, необходимых для решения экспоненциальной задачи, похоже на попытку человека угадать комбинацию на замке. Если у вас всего один 10-значный циферблат, задача проста. С четырьмя дисками, такими как велосипедный замок, достаточно сложно, но все же возможно, чтобы вы могли попробовать каждую комбинацию. С 50 это практически невозможно — потребуется слишком много шагов. Проблемы, которые имеют экспоненциальную сложность, похожи на задачи компьютеров: по мере того, как они становятся больше, они быстро опережают способность компьютера справляться с ними. Поиск полиномиального алгоритма часто решает эту проблему, позволяя решать проблемы так, как никакое улучшение оборудования не может.
По мере того, как слухи о законе Мура быстро проникают в глобальные дискуссии, исследователи говорят, что пользователям компьютеров все чаще придется обращаться к таким областям, как алгоритмы, для повышения производительности. Команда говорит, что результаты подтверждают, что исторически выгоды от алгоритмов были огромными, поэтому потенциал есть. Но если выигрыш будет исходить от алгоритмов, а не от оборудования, они будут выглядеть иначе. Улучшение оборудования на основе закона Мура происходит плавно с течением времени, а для алгоритмов выигрыш достигается за счет шагов, которые обычно являются большими, но нечастыми.
Благодаря проведенному анализу можно сказать, сколько еще задач можно было бы выполнить с использованием того же количества вычислительной мощности после улучшения алгоритма. По мере того как проблемы увеличиваются до миллиардов или триллионов точек данных, улучшение алгоритмов становится значительно более важным, чем улучшение оборудования. В эпоху, когда воздействие компьютеров на окружающую среду вызывает все большее беспокойство, это способ улучшить работу предприятий и других организаций без каких-либо негативных последствий.
