Сортировка, или структурирование данных, была основным принципом вычислительных операций с тех пор, как были разработаны первые компьютеры.
Упорядочивание и обработка чисел были продемонстрированы вавилонянами около 2500 года до нашей эры. Египтяне последовали их примеру примерно в 1550 году до нашей эры, а греческий математик Евклид около 300 года до нашей эры разработал формулу для быстрого нахождения наибольшего общего делителя двух целых чисел.
В середине 1800-х годов упорядочивание было главной целью математика Августы Ады Кинг, дочери поэта лорда Байрона. Она создала первый алгоритм, предназначенный для использования на тогдашней теоретической машине, придуманной ее наставником, математиком Чарльзом Бэббиджем (известным как отец компьютеров). За это достижение она получила титул «первый компьютерный программист».
В 1951 году другая женщина, Фрэнсис Элизабет Холбертон, разработала первую систему генеративного программирования — элементарную процедуру сортировки/слияния для армии США. Она также помогала программировать баллистические траектории во время Второй мировой войны.
На самом деле, по словам эксперта по компьютерному дизайну и криптологии Фрэнка Рубина, сортировку можно проследить до форм жизни еще до появления человека — примерно за 65 миллионов лет до этого. Динозавры, по его словам, выполняли простую сортировку. Они классифицировали все живые существа на две категории: «пища» и «не пища».
Темпы разработки вычислительных алгоритмов ускорились с середины 20-го века по настоящее время. Теперь у нас есть компьютеры, способные производить квинтиллион вычислений в секунду.
Вавилоняне — возможно, даже динозавры — были бы весьма впечатлены.
Также впечатляет прорыв, объявленный 7 июня командой Google DeepMind в онлайн-блоге.
Команда разработала подход к обработке чисел, который на 70% быстрее, чем существующие методы. Алгоритмы используются уже год, так как они были добавлены в библиотеку C++. По данным DeepMind, алгоритмы с открытым исходным кодом в настоящее время используются миллионами разработчиков и компаний по всему миру.
Проект искусственного интеллекта под названием AlphaDev — это «система искусственного интеллекта, которая использует обучение с подкреплением для обнаружения усовершенствованных алгоритмов информатики, превосходящих те, которые оттачивались учеными и инженерами десятилетиями», — сообщает DeepMind в своем блоге. Статья также опубликована в журнале Nature.
AlphaDev развивает успех своего предшественника, AlphaZero, который освоил стратегии, лежащие в основе Go и шахмат.
Обучение AlphaDev сортировке проводилось с использованием того, что исследователи назвали «однопользовательской игрой на ассемблере».
Алгоритмы сортировки создавались по одной инструкции за раз, поскольку AlphaDev постоянно изучала варианты, чтобы найти тот, который работал лучше предыдущего. Этот процесс включает в себя подключение к нейронным сетям для сравнения и перемещения значений, и все это для получения наиболее точных результатов в кратчайшие сроки.
«Закон Мура подходит к концу, когда чипы приближаются к своим фундаментальным физическим пределам», — сказал ученый DeepMind Дэниел Манковиц. «Нам нужно найти новые и новаторские способы оптимизации вычислений».
Исследование было сосредоточено на коротких списках, содержащих до пяти символов. Исследователи заявили, что алгоритмы для трех-пяти символов наиболее часто используются программистами. Такие алгоритмы используются «триллионы раз в день», говорится в блоге DeepMind.
Для более длинных последовательностей сортировки, до 250 000 элементов, наблюдалось незначительное повышение скорости по сравнению с существующими методами.
Следующим шагом для AlphaDev является изучение оптимизации на языках более высокого уровня, таких как C++, что должно привести к значительному повышению скорости и быть более полезным для разработчиков.
