Найти бегущую взвешенную медиану из потока значений и весов

Взвешенная медиана выборки — это 50% взвешенный процентиль (см. этот пост @ перекрестная проверка для получения дополнительной информации)/

Мне было интересно, как можно расширить алгоритм, используемый для поиска медианы бегущего потока чисел, подробно описанных здесь (с двумя кучами, минимальной кучей для левой стороны и максимальной кучей для правой стороны), чтобы эффективно вычислить взвешенную медиану из потока double значений и весов.

У меня была идея использовать тот же метод, что и при вычислении медианы из невзвешенного потока чисел, но просто добавить дополнительные значения, если веса не равны единице (например, значение с весом 2 будет вставлено дважды). Однако это не очень хорошо масштабируется с весами, которые могут быть удвоены, а также кажется довольно неэффективным с точки зрения использования памяти.

Спасибо!


median algorithm heap
person Community    schedule 23.06.2016    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Один из подходов со сложностью O(nlogn) состоит в том, чтобы вставить узлы в расширенное сбалансированное двоичное дерево поиска. Дерево будет отсортировано по значению, и каждый узел в дереве будет дополнен полем, дающим общий вес всех дочерних узлов.

Вставка нового узла, включая обновление всех полей общего веса, стоит O(logn).

Чтобы найти медиану, вы спускаетесь по дереву на основе целевого веса общего веса, деленного на 2. Этот поиск займет O (logn).

person Peter de Rivaz    schedule 23.06.2016

arrow_upward
0
arrow_downward

В итоге я реализовал метод, который использует отсортированный массив (по сути, выполняет функцию минимальной кучи, но с более простым поиском) и постоянно отслеживает, где находится пятидесятая процентиль общего веса. Я написал сообщение в блоге о это с более подробными примерами.

person Community    schedule 19.07.2016