3 мин. чтения
6/13/2023 1:18:00 PM

DeepMind преуспел в скорости сортировки

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

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

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

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

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

Вавилоняне — может быть, даже динозавры — были бы весьма впечатлены.

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

Featured Image Принципиально разные алгоритмы, обнаруженные AlphaDev. DOI: 10.1038/s41586-023-06004-9

Команда разработала подход к обработке чисел, который на 70% быстрее, чем современные методы. Алгоритмы используются уже год, так как они были добавлены в библиотеку C++. По данным DeepMind, алгоритмы с открытым исходным кодом в настоящее время используются миллионами разработчиков и компаний по всему миру.

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

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

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

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

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

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

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

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

Оригинал статьи: Daniel J. Mankowitz et al, Faster sorting algorithms discovered using deep reinforcement learning, Nature (2023). DOI: 10.1038/s41586-023-06004-9 🔗

Получи бесплатную еженедельную рассылку со ссылками на репозитории и лонгриды самых интересных историй о стартапах 🚀, AI технологиях 👩‍💻 и программировании 💻!
Присоединяйся к тысячам читателей для получения одного еженедельного письма

Подписывайся на нас:

Нашли ошибку в тексте? Напишите нам.

Добавляй ЛРНЧ в свою ленту Google Новостей.
Читайте далее 📖

Нейролянджело - пробуди цифрового Микеланджело с помощью смартфона

7/15/2023 · 3 мин. чтения

Нейролянджело - пробуди цифрового Микеланджело с помощью смартфона

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

6/27/2023 · 3 мин. чтения

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