KO
нет, так будет работать. это называется интрузивный отсортированный массив.
Size: a a a
2020 July 23
CD
у нас 10-15 элементов длиной в 16 байт
KO
а можно сделать его хипом, будет чуть получше чем bubble sort.
CD
а можно сделать его хипом, будет чуть получше чем bubble sort.
не будет, потому что все равно дернутся все кэш-линии
KO
но вопрос не в этом же. допустим bubble sort. вы согласны что это не лучше std::nth_element?
KO
(принципиально не лучше)
KO
а bubble sort мне вручнуюпридётся писать, а nth_element я один раз вызову, и всё.
VO
в смысле? у нас масив struct { int pos; node *ref; }
по затронутым элементам потом проходим обновляем ref->pos; это будет не очень много кеш-линий затронуто
по затронутым элементам потом проходим обновляем ref->pos; это будет не очень много кеш-линий затронуто
KO
Вячеслав, я согласен с вами, что можно так сделать.
VO
там даже читать не надо, задержки могут минимизироваться.
KO
возвращаясь к вопросу, я искал что-то готовое, как обычно.
VO
в смысле "вручную писать"? там кода три строки.
KO
в целом согласен.
KO
но вот представьте сколько в чатике разбирались, примерно столько же будет вопросов на code review.
VO
серьезно? вот к такой тривиальщине на уровне школьного кружка по програмированию -- вопросы?
VO
или я чего не улавливаю?
KO
именно к тривиальщине всегда возникает больше всего вопросов.
KO
это же bikeshed rule
CD
в общем, любые попытки обновления хипы для i-го нода приведут к немедленному запросу i/2, i*2 и i*2+1, что уже означает запрос в 3 кэш-линии
KO
вообще вы мне помогли определиться с моими собственными value judgements о том что делать, спасибо большое. пузырёк, пожалуй, хорошая идея, т.к. тупо.