У меня есть проблема, когда мне нужно хранить изменяющиеся значения данных v_i (целые числа) для постоянных ключей i (также целые числа, в некотором диапазоне, скажем, [1; M]).Мне нужно уметь быстро рисовать случайный элемент, взвешенный по значениям v_i, то есть вероятность нарисовать ключ k должна быть v_k / (сумма (i = 1 ... M) v_i)
Лучшая идеяЯ мог бы придумать, использует двоичное дерево и сохраняет частичную сумму по значениям в поддереве с корнем в k как значение для ключа k (все еще в диапазоне [1; M]).Затем, когда значение изменяется, мне нужно обновить его узел и все родительские узлы в дереве (занимает O (log M) времени, так как ключи фиксированы и, следовательно, двоичное дерево идеально сбалансировано).Рисование случайного элемента, как описано выше, также занимает время O (log M) (для каждого уровня дерева сравнивается случайное число, скажем, в диапазоне (0,1), с относительными весами левого поддерева, правого поддерева исам узел) и намного быстрее, чем простой алгоритм (взять случайное число r, перебрать элементы, чтобы найти наименьшее k, чтобы сумма (i = 1 ... k) r; занимает O (M) времени).
Теперь у меня есть вопрос, как оптимизировать размещение узлов дерева в памяти, чтобы минимизировать потери в кеше.Поскольку все ключи известны и остаются постоянными, это по сути порядок, в котором я должен выделять память для узлов дерева.
Спасибо !!