AlphaDev от Google увеличил скорость сортировки данных на 70%

Сортировка, или структурирование данных, была основным принципом вычислительных операций с тех пор, как были разработаны первые компьютеры.

Порядок и обработка чисел были продемонстрированы вавилонянами еще около 2500 г. до н.э. Египтяне последовали их примеру около 1550 г. до н.э., а греческий математик Евклид около 300 г. до н.э. разработал формулу для быстрого нахождения наибольшего общего делителя двух целых чисел.

В середине 1800-х годов упорядочение было главной целью математика Августы Кинг, дочери поэта лорда Байрона. Она создала первый алгоритм, предназначенный для использования на том, что тогда было теоретической машиной, придуманной ее наставником, математиком Чарльзом Бэббиджем (известным как отец компьютеров). За это достижение она получила титул «первый программист».

В 1951 году другая женщина, Фрэнсис Элизабет Холбертон, разработала первую систему генеративного программирования, элементарную процедуру сортировки/слияния.

На самом деле, по словам экспертов, сортировку можно проследить еще до того, как люди эволюционировали, примерно за 65 миллионов лет до этого. Динозавры, по их словам, выполняли простую сортировку. Они классифицировали все живое на две категории: «еда» и «не еда».

Темпы развития вычислительных алгоритмов ускорились с середины 20-го века до настоящего времени. И теперь есть компьютеры, способные выполнять квинтиллион вычислений в секунду. Вавилоняне — а возможно, даже динозавры — были бы весьма впечатлены.

Также впечатляет прорыв, о котором 7 июня сообщила команда Google DeepMind в онлайн- блоге.

Исследователи разработали подход к обработке чисел, который на 70% быстрее, чем существующие методы.

Проект искусственного интеллекта под названием AlphaDev представляет собой «систему искусственного интеллекта, которая использует обучение с подкреплением для обнаружения усовершенствованных алгоритмов компьютерных наук, превосходящих те, которые оттачивались учеными и инженерами на протяжении десятилетий», — сообщает DeepMind в своем блоге.

AlphaDev основывается на успехе своего предшественника AlphaZero, который овладел стратегиями, лежащими в основе игры в го и шахматы.

Обучение AlphaDev сортировке проводилось с использованием того, что исследователи назвали «игрой для одного игрока на ассемблере [язык]».

Алгоритмы сортировки строились по одной инструкции за раз, поскольку AlphaDev постоянно изучал варианты, чтобы найти тот, который работал лучше, чем предыдущий. Процесс включает в себя подключение к нейронным сетям для сравнения и перемещения значений, чтобы получить наиболее точные результаты в кратчайшие сроки.

«Закон Мура подходит к концу, когда чипы приближаются к своим фундаментальным физическим пределам», — сказал ученый из DeepMind Дэниел Манковиц. «Нам нужно найти новые и инновационные способы оптимизации вычислений».

Исследование было сосредоточено на коротких списках до пяти символов. Исследователи говорят, что программисты чаще всего используют алгоритмы для трех-пяти символов. Такие алгоритмы используются «триллионы раз в день», говорится в блоге DeepMind.

Для более длинных последовательностей сортировки, до 250 000 элементов, было незначительное улучшение скорости по сравнению с текущими методами.

Следующим шагом для AlphaDev является изучение оптимизации на языках более высокого уровня, таких как C++, что должно выявить большее улучшение скорости и быть более полезным для разработчиков.