CD
из 4 если не впаковать все в одну
Size: a a a
2020 July 23
KO
Константин, правда, всё чем хип отличается от bubble sort это количество сравнений.. в хип их будет меньше, тк.. структура частично отсортирована
KO
по кэш линиям всё можно сделать точно так же
CD
Константин, правда, всё чем хип отличается от bubble sort это количество сравнений.. в хип их будет меньше, тк.. структура частично отсортирована
Только ЦПУ будет заниматься не сравнениями, а ожиданием кэша
KO
но вот с учётом отсутствия в С++ стандартного интрузивного хипа, это не вариант.
VO
не-не. массив-то у нас полностью отсортирован
CD
И не дай бог он не поймет, какие кэш-линии ему запросить
VO
и пузырек завершиться за одно-два сравнения если все pos разные.
CD
Именно поэтому в стандартной сортировке if на 64 элемента
KO
Там точно также будет основная стоимость - это дереференс struct node по указателю
KO
сам хип, как и массив, будут маленькими.
VO
это после пузырька.
KO
это точно так же будет работать в случае кучи.
KO
оптимизация одинаково применима.
CD
будет, или не будет, будет кэш-мисс из-за непонятного запроса индекса и конечная остановка
CD
std::sort все-таки не дураки писали, и они массив в 64 элемента сортируют insertion-ом
VO
куча на ссылках/указателях? если да -- то нифига, размеры больше за счет укзателей + миссы
CD
куча на ссылках/указателях? если да -- то нифига, размеры больше за счет укзателей + миссы
куча не требует ссылок
KO
это я вообще оставлю в стороне, дураки ли писали std::sort.