Несколько недель назад товарищ скинул в общий чатик ссылку на новость что опубликована
статья на Nature про то как AlphaDev открывает самые быстрые алгоритмы сортировки. AlphaDev это расширение для AlphaZero, которая хорошо играет в шахматы и го. Новость подаётся в стиле машины научились думать, наконец-то и уже создают алгоритмы, а не просто бесконечно большие
switch case. Я честно подождал, потом поискал, что-то где было доступным языком расписано что же в итоге сделали в DeepMind, но ничего вменяемого не увидел. Пришлось читать статью самому.
Я честно пропустил всё что касалось собственно ИИ и сосредоточился только на найденных алгоритмах, они кстати искали не алгоритмы, а сразу программы на ассемблере
x86 правда в нотации AT&T (там операнды в другом порядке относительно нотации Intel). Надо сказать что я сразу понял, что зря тему алгоритмов с точки зрения математики, а конкретно алгоритмов сортировки никогда не затрагивал, поэтому и ждал пока кто-то разжуёт что же там сделали, для таких как я. В связи с этим я советую почитать статью тем кто хочет больше понять про алгоритмы сортировок небольших наборов значений из 3, 4, 5 элементов, именно их оптимизируют в статье. Там даже про сети есть, правда сортировочные. Есть
гитхаб со всеми алгоритмами, а в самой статье разбирается несколько из них с конкретными изменениями было-стало. Нет смысла разбирать именно ассемблерный код, он не сложен, всё дело в том что он реализовывает. Что я там увидел (напомню что алгоритмизации как части математики я никогда не касался):
Было найдено несколько решений, которые можно явно сравнить с тем как было реализовано до этого. В частности про сортировке 3-х элементного массива была убрана лишняя проверка, с точки зрения кода это лишняя пересылка
mov, а с точки зрения математики условие в этом месте выполняется всегда. Дальше это повлияло и на сортировку массивов из большего количества элементов, в частности приводится пример фрагмента кода взятого из сортировки 8-ми элементов. На мой дилетантский взгляд, кто-то из людей в этом месте перестраховался, а потом к этому месту никто не возвращался.
Второй момент отмечаемый в статье это оптимизация алгоритма сортировки с переменным количеством элементов, но опять же небольшим. Приводится блок схема как это реализовывалось человеком для сортировки массивов от 2 до 4 элементов: если 2 - вызов сортировки для двух элементов, если 3 - вызов сортировки для трёх элементов, если 4 - вызов сортировки для 4-х элементов. AlphaDev найден другой алгоритм: если 2 - вызов сортировки двух, если больше то всегда сортируем первые 3 и если надо сортировать 4, то сортируем получившийся массив с учётом что первые три элемента уже отсортированы и в этом месте получаем выигрыш по длине и задержке.
Новые сортировки 3, 4 и 5 элементных массивов пропатчили в
LLVM libc++, там есть тесты производительности, но больше именно про тесты можно читать в
дополнении (pdf).Я могу очень сильно ошибаться и всё ещё жду популярную статью где доступным языком расскажут что же такого произошло с этими алгоритмами, чего такого нашли нового в DeepMind. Может не очень доступным, но хотя бы переведут с языка математики, на язык программистов. Но как минимум не просто хвалебные отзывы о том что машины стали делать сами себя. Я не увидел тут прорыва именно ИИ, точнее вижу что это мог сделать и человек. На мой взгляд на эту часть алгоритмов, их реализаций, все забили и копипастили явных авторитетов, а потом вспомнили и решили, а давайте-ка посмотрим что с этим нейронки могут сделать. Ну они и сделали. А мы будем пользоваться и получать удовольствие от этого :)
