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