Искусственный интеллект создает более эффективные алгоритмы сортировки
Онлайн-алгоритмы сортировки запускаются миллиарды раз в день для выдачи результатам пользователям. Новые исследования нашли более быстрые альтернативы.
Что нового: Даниэль Дж. Манковиц и его коллеги из Google разработали систему AlphaDev, которая научилась создавать алгоритмы, сортирующие три-пять чисел быстрее, чем предыдущие передовые методы. Ускорение таких алгоритмов может ускорить сортировку списков любого размера - например, для поисковых систем, интернет-магазинов и других - поскольку алгоритмы, сортирующие больше элементов, часто вызывают алгоритмы, сортирующие меньше элементов.
Ключевое открытие: Большинство программистов реализуют алгоритмы сортировки на языке программирования высокого уровня, таком как C++, который компилятор преобразует в инструкции языка ассемблера, управляющие процессором и памятью. Компилятор может преобразовать одну строку C++ в различные последовательности инструкций языка ассемблера, которые функционально эквивалентны, но отличаются скоростью выполнения (количеством инструкций языка ассемблера, необходимых для выполнения). Агент, обучающийся с подкреплением, может научиться выбирать преобразование, максимизирующее скорость.
Как это работает: AlphaDev - это набор нейронных сетей, которые обучаются совместно с помощью обучения с подкреплением. Авторы инициализировали систему, предоставив ей последовательность неотсортированных чисел и пустой список инструкций языка ассемблера. Она строила алгоритмы, добавляя инструкции языка ассемблера по одной. Она получала награды за выбор инструкций, которые правильно и быстро сортировали числа.
С каждой новой выбранной инструкцией трансформатор вычислял вложение инструкций на данный момент, а обычная нейронная сеть вычисляла вложение порядка чисел после применения этих инструкций. Система объединяла два вложения для представления текущего состояния.
Исходя из вложений, две обычные нейронные сети выбирали инструкции. Первая сеть (i) предсказывала общую будущую награду для текущего состояния и (ii) вычисляла вероятность того, что данная инструкция улучшит алгоритм. Вторая сеть (iii) предсказывала награду после добавления каждой возможной инструкции и (iv) предсказывала вложение для представления полученного состояния.
Система искала через возможные последовательности инструкций ту инструкцию, которая чаще всего приводила к наибольшей предсказанной награде. Она добавляла эту инструкцию в алгоритм.
После построения алгоритма авторы загрузили его в основную библиотеку C++, которая не обновлялась более десяти лет. Полученные алгоритмы теперь служат как открытые подпрограммы в алгоритме сортировки по умолчанию C++.
Результаты: Авторы протестировали два подхода к вознаграждению скорости, минимизируя количество инструкций языка ассемблера или среднее время выполнения на нескольких входных данных. Когда AlphaDev минимизировала количество инструкций языка ассемблера, она нашла алгоритм, сортирующий три целых числа с использованием 17 инструкций вместо предыдущего передового алгоритма, созданного человеком, который использовал 18 инструкций. Алгоритм для сортировки четырех целых чисел использовал 28 инструкций, что равно типичному алгоритму. Алгоритм для сортировки пяти целых чисел использовал 42 инструкции по сравнению с альтернативными 46 инструкциями. Когда AlphaDev оптимизировала время выполнения (работая на процессоре Intel 6-го поколения Core "Skylake"), сортировка трех целых чисел занимала 2,18 наносекунды, по сравнению с 4,86 наносекунды у типичного алгоритма. Сортировка четырех беззнаковых целых чисел занимала 1,96 наносекунды вместо 5,43 наносекунды, а сортировка пяти из них занимала 1,98 наносекунды вместо 6,79 наносекунды. AlphaDev достигла меньшего ускорения с более длинными последовательностями чисел: сортировка 16 беззнаковых целых чисел занимала 9,5 наносекунды вместо 10,5 наносекунды, а сортировка 262 144 чисел занимала 60,8 наносекунды вместо 61,4 наносекунды.
Почему это важно: Эта работа переиспользует методику обучения и архитектуру моделей, используемых для игр, таких как AlphaZero, для решения реальных проблем. Суть заключается в том, чтобы переформулировать задачу написания алгоритма сортировки как задачу обучения с подкреплением.
Что мы думаем: какие другие алгоритмы могут быть оптимизированы с помощью этого подхода? Насколько быстрее они будут? Давайте разберемся с этими вопросами!
