Получить среднее число в структуре данных отсчета-мин-эскиза

Question

Я влюблен в вероятностные структуры данных.Для моей текущей проблемы кажется, что структура count-min-sketch - почти правильный кандидат.Я хочу использовать count-min-sketch для хранения событий для каждого идентификатора.

Предположим, у меня есть следующее

Map<String, Int> {
   [ID1, 10],
   [ID2, 12],
   [ID2, 15]
}

Если я использую count-min-sketch, я могу запроситьструктура данных по идентификаторам и получить количество ~.

Вопрос

На самом деле меня интересует средняя встречаемость по всем идентификаторам, которая в приведенном выше примере будет: 12,33.Если я использую счетчик минут, то кажется, что мне нужно сохранить набор идентификаторов, а затем перебрать набор и запросить счетчик минут для каждого идентификатора и вычислить среднее значение.Есть ли улучшенный способ без сохранения всех идентификаторов?В идеале я просто хочу получить среднее значение сразу, не запоминая все идентификаторы.

Надеюсь, что имеет смысл!?

Answer 1

Вы должны быть в состоянии рассчитать среднее количество, если вы знаете количество записей и количество различных записей:

averageCount = totalNumberOfEntries / numberOfDistinctEntries

Верно?И для расчета количества отдельных записей вы можете использовать, например, HyperLogLog .Вы уже добавили тег hyperloglog в свой вопрос, так что, может быть, вы уже знаете это?