Нейросеть помогла разработать улучшенный алгоритм сортировки
![de70f972da0258aef8f140d174b12273.png](https://habrastorage.org/getpro/habr/upload_files/de7/0f9/72d/de70f972da0258aef8f140d174b12273.png)
Google DeepMind сообщила, что благодаря использующей обучение с подкреплением системе ИИ AlphaDev, удалось разработать усовершенствованные алгоритмы сортировки. В компании отмечают, что в отличие от общепринятых подходов, разработка велась с нуля при помощи игры, основанной на ассемблерных кодах.
Делая ход, AlhpaDev оценивала сгенерированный ей алгоритм и информацию в процессоре, а затем выбирала очередную инструкцию, которую добавляла при новом ходе. В DeepMind отмечают, что игра получилась невероятно сложной за счет огромного количества возможных комбинаций, число которых аналогично количеству частиц во вселенной или количеству возможных комбинаций ходов шахматах (10^120). При этом всего один неверный ход мог привести к порче всего алгоритма.
В конечном итоге AlphaDev обнаружила новые алгоритмы сортировки, которые были интегрированы в библиотеку сортировки LLVM libc ++ и позволили на 70% ускорить сортировку коротких последовательностей и примерно на 1,7% — последовательностей, превышающих 250 000 элементов.
Материал, посвященный этой работе, опубликован в журнале Nature.