CD
И если у вас есть какие-то особенности в изменении num - их нет в описанной вами задаче
Size: a a a
2020 July 22
KO
Сорри, но правда не ясно зачем это обсуждение Я описал, что nth_element - это один из вариантов. Вы меня убеждаете в чём-то что не приближает ни к одной из более эффективных альтернатив.
CD
Сорри, но правда не ясно зачем это обсуждение Я описал, что nth_element - это один из вариантов. Вы меня убеждаете в чём-то что не приближает ни к одной из более эффективных альтернатив.
Почему? Я убеждаю вас, что вам надо использовать std::set, в асимптотике оптимально, в константе не оптимальны оба решения. И да, я надеюсь, вы не берёте оценки операций из эзотерики типа fib-heap, потому что на практике это будет binary heap
CD
Если вас волнует константа при логарифме при 3 операциях в секунду это правда странно
KO
я немного утрировал историю про 3 операции в секунду. я сейчас прикидываю в голове сколько у меня в среднем элементов, изменений в секунду, и запросов срединного элемента чтобы как-то внятно объяснить
CD
если вам позарез нужна константа обновления, боюсь вам нужно структуры в духе B-tree согласованных с длиной кэш-линии
CD
все константы этих решений в кэш-промахах
KO
думаю в моём случае всё же честно сказать что N не будет большим, и nth_element просто выиграет за счёт того что он будет ближе к константе.
CD
запрос nth_element у вас всегда О(1)
KO
сейчас снова не понял.
CD
например, вы храните три раздельные сущности - левее середины, середину и правее середины
CD
при изменении элемента двигается не более О(1) элементов
VO
не, я наверное задачу не понял, но если элементов константа, а изменение порядка +/-1 и сами элементы искать не надо -- то отсорированный масив дает тупо константу.
CD
я думал, что эта часть у вас есть, по-другому из хипы середина не достается :)
KO
Повторю задачу. Есть N узлов кластера. Это в пределах 10-15 в худшем случае. У каждого узла есть переменная, которая постоянно меняется - его позиция. Она монтонно растёт, это integer. Нужно быстро определять где находится большинство.
VO
большинство находится выше 0
2020 July 23
CD
Повторю задачу. Есть N узлов кластера. Это в пределах 10-15 в худшем случае. У каждого узла есть переменная, которая постоянно меняется - его позиция. Она монтонно растёт, это integer. Нужно быстро определять где находится большинство.
Задача сильно изменилась и потерялась любая необходимость что-либо оптимизировать, просто храните сортированный массив
KO
сортировать его по чему? В какой момент?
VO
в начале, по порядку
CD
сортировать его по чему? В какой момент?
по тому, для которого середина определяется