P
Query точный или приближенный?
Точный
Size: a a a
2020 March 20
P
Step может как угодно меняться?
точно не знаю, но начали с того, когда он постоянный.
CD
Ну то есть надо в мапе найти количество элементов больше определенного, добро пожаловать в декартовы деревья декартовых деревьев)
MB
Пусть сначало это константа. Если в такой формулировке
Тогда можно в явном виде поддерживать для каждого юзера, сколько событий произошло за последний time. И для cnt хранить, у скольких юзеров такое cnt.
Это что-то типа двух хэшмап
Это что-то типа двух хэшмап
MB
Но да, если левые границы (т.е. cur_time-step) немонотонные, то у меня нет идей кроме двумерных деревьев.
CD
Короче, я бы уже расчехлял корневую
P
Тогда можно в явном виде поддерживать для каждого юзера, сколько событий произошло за последний time. И для cnt хранить, у скольких юзеров такое cnt.
Это что-то типа двух хэшмап
Это что-то типа двух хэшмап
А можешь детальнее сказать? Что будет хранится для каждого юзера?
CD
Как её тут правильно писать-то
CD
А можешь детальнее сказать? Что будет хранится для каждого юзера?
Для юзера нет альтернативы хранению сортированного набора событий
P
Для юзера нет альтернативы хранению сортированного набора событий
То есть хранения моментов времени, когда эти события произошли?
CD
CD
Это же все могут спросить
MB
А можешь детальнее сказать? Что будет хранится для каждого юзера?
Для юзера храним вектор с моментами событий, которые пока что актуально.
MB
А точнее очередь
P
Понял, и отдельно отображение count на количество юзеров с количеством событий равным count?
MB
Соответственно новое событие пушится в конец очереди. Протухшее удаляется из начала.
MB
Понял, и отдельно отображение count на количество юзеров с количеством событий равным count?
Да. После каждого изменения каждой очереди при необходимости перекладываем юзера.
MB
Это решение работает, если step растет не быстрее, чем time. В частности, если step фиксирован
P
А какая тогда сложность RegisterEvent? Мы должны будем пробегатся по всех юзерах, чтобы обновить их очередь зарегестрированных событий?
P
Или когда мы будет обновлять эти очереди