Я правильно понял что идея в том, чтобы натренировать branch predictor на то что range check всегда валидный и как следствие можно сразу смотреть на сравнение элементов?

Если это так, то на сколько я помню Александреску в итоге линейную вставку запускал со второго (или даже третьего?) элемента в хипе и получил на этом заметный прирост. То есть, кажется, это не связано с обучением предиктора игнорировать конец массива.

это связано с тем, что первый элемент хипы минимум, так что второй не надо трогать

На счет первого элемента это более-менее очевидно. Про второй с ходу не скажу, мне нужно вспоминать как именно работает хип.

Но я до сих пор не уверен, что правильно понял почему пузырек мог дать тот же эффект.

Наверное со вторым и третьим элементами там было просто сравнение и своп, а сортировка запускалась с четвертого.

@isenbaev что я там переизобретаю, признавайся

тут получается, что перед insertion sort 32 надо выполнить проходики со сравнениями на расстояниях 7 4 1

эти проходы чудесно векторизуются (если есть векторизованная команда minmax разумеется)

я видел этот подход в какой-то сортировке, но не помню названия

shell sort? 🤔

да, очень похоже

там должны быть слова типа h-sorted как раз

правда 1 4 7 там нет, но она явно специфическая в классе)

То есть вероятно можно было воспользоваться shell sort вместо make heap + linear insertion?

Ребят, привет всем. Хотел бы услышать идеи на решение такой задачи.

Есть множество с положительными целыми числами по модулю до 10^9, количество до 10^6.

Над множеством нужно делать следующие действия, пока оно будет изменяться: берём все возможные пары из различных чисел и вставляем в это множество модуль их разницы.

После этого нужно найти k-th largest.

Как это можно сделать эффективно?

Ну то есть понятно, что можно добавлять эллементы в конец, если они новые и потом на следующей итерации брать пары между новыми и предыдущими, и т.д.

Но по-идее нужно как-то свойства чисел заюзать.

Во многих кейсах после преобразований множество будет вида 2, 3, 4, ... max_element, но есть и корнер кейсы.

Вот один из них будет таким
x, 2*x, ..., k*x, но мне кажется, что должны быть и другие

k * gcd всех?

😳😳😳😳😳

Хм...
Я подумаю контрпример, но это было бы слишком просто 😃

там модуль может быть взаимно простым с чем-нибудь