В июне 2023 года компания DeepMind из Google опубликовала в журнале Nature плодотворную статью, в которой объявила, что их программист искусственного интеллекта AlphaDev обнаружил несколько новых алгоритмов сортировки, которые могут улучшить сортировку коротких последовательностей до 70%.
Это удивительно. Сортировка остается основополагающим принципом в области информатики: множество алгоритмов сортировки прошли десятилетия тщательного изучения. Что именно предложил AlphaDev?
К сожалению, сообщение в блоге DeepMind об их открытии скорее вводит в заблуждение, чем помогает. sort3 (алгоритм сортировки трех чисел) в их сообщении просто сортируется неправильно. В их сообщении упущен тот важный факт, что их sort3 является лишь фрагментом реального sort3.
Учитывая это упущение, я начну с нуля и выведу этот новый алгоритм sort3 в пошаговом повествовании, управляемом человеком. Это не только прольет свет на ошибки нашего алгоритма в прошлом, но и проложит путь для будущих улучшений. В статье DeepMind содержится больше алгоритмов, чем sort3. Но для простоты в ходе нашего обсуждения мы сосредоточимся только на этом.
1. Обязательное условие
Новый алгоритм сортировки AlphaDev обнаруживается на уровне ассемблерного кода. Но не волнуйтесь, если вы не знакомы с этим компьютерным языком низкого уровня. Все, что вам нужно знать, это следующие три простых инструкции:
mov A B : move a value from source A to destination B cmp A B : compare the values in A and B, and set a register flag accordingly cmovX A C: Conditionally move the value from A to C given the register flag where "X" could be l (less than), g (greater than), le (less than or equal to), or ge (greater than or equal to).
Обладая вышеуказанными знаниями, мы готовы понять прорыв в области сортировки AlphaDev.
2. Возвращаясь к исходной реализации sort3
Давайте сначала попробуем решить эту проблему самостоятельно. Можно сформулировать алгоритм сортировки трех чисел, подобный следующему:
// sort3(P, Q, R) if (Q > R) swap(Q, R); // sort2(Q, R) if (P > R) swap(P, R); // sort2(P, R) if (P > Q) swap(P, Q); //…