Возрастающее среднее вычисление с макс. эффективностью памяти
У меня есть процесс, который генерирует значения и что я наблюдаю. Когда процесс завершается, я хочу вычислить медиану тех значений.
Если бы я должен был вычислить среднее, то я мог бы просто сохранить сумму и количество сгенерированных значений и таким образом иметь O (1) требование к памяти. Как насчет медианы? Существует ли способ экономить на очевидном O (n) прибывающий из хранения всех значений?
Править: Заинтересованный 2 случаями: 1) потоковая длина известна, 2) это не.
3 ответа
Вам нужно будет сохранить как минимум ceil (n / 2) точек, потому что любой из Первые n / 2 балла могут быть медианой. Вероятно, проще всего просто сохранить точки и найти медиану. Если сохранение ceil (n / 2) точек имеет значение, тогда считайте первые n / 2 точек в отсортированный список (двоичное дерево, вероятно, лучше всего), затем, когда добавляются новые точки, отбросьте низкие или высокие точки и сохраните отслеживать количество выброшенных очков на обоих концах.
Редактировать:
Если длина потока неизвестна, то, очевидно, как Стивен заметил в комментариях, у нас нет другого выбора, кроме как все запомнить. Если вероятны повторяющиеся элементы, мы могли бы сэкономить немного памяти, используя идею Dolphins о хранении значений и счетчиков.
Вы можете
- Использовать статистику, если это приемлемо - например, вы можете использовать выборку.
- Использовать знания о потоке чисел
- используя подход, похожий на подсчет:
kотдельных значений означает хранениеO(k)памяти) - или отбросить известные выбросы и вести счетчик (high,low).
- Если вы знаете, что у вас нет дубликатов, вы можете использовать битовую карту... но это просто меньшая константа для
O(n).
- используя подход, похожий на подсчет:
Если у вас есть дискретные значения и много повторений, вы можете сохранить значения и счетчики, что сэкономит немного места.
Возможно на этапах вычислений вы могли бы отбросить верхнее «n» и нижнее «n» значения, если вы уверены, что медиана не находится в этом верхнем или нижнем диапазоне.
например Допустим, вы ожидаете 100 000 значений. Каждый раз, когда ваше сохраненное число достигает (скажем) 12000, вы можете отбросить самые высокие 1000 и самые низкие 1000, уменьшив объем памяти до 10 000.
Если бы распределение значений было достаточно последовательным, это сработало бы. Однако, если есть вероятность того, что вы получите большое количество очень высоких или очень низких значений ближе к концу, это может исказить ваши вычисления. В основном, если вы отбрасываете «высокое» значение, которое меньше (возможной) медианы, или «низкое» значение, которое равно или больше (конечной) медианы, то ваш расчет будет отключен.
Обновление
Бит примера
Допустим, набор данных - это числа 1,2,3,4,5,6,7,8,9.
При осмотре медиана равна 5.
Предположим, что первые 5 чисел, которые вы получите, - 1,3,5,7,9.
Для экономии места отбрасываем самые высокие и самые низкие, оставляя 3,5,7
Теперь возьмите еще два, 2,6, так что наше хранилище будет 2,3,5,6,7
Отбросить самый высокий и самый низкий, оставив 3,5,6
Получим последние два 4,8, и у нас будет 3,4,5,6,8
Медиана по-прежнему равна 5, и мир - хорошее место.
Однако, допустим, что первые пять чисел, которые мы получаем, - 1,2,3,4,5
Отбросить верх и низ, оставив 2,3,4
Возьмите еще два 6,7, и у нас будет 2,3,4,6,7
Отбросить верх и низ, оставив 3,4,6
Получим последние два 8,9, и у нас будет 3,4,6,8,9
Со средним значением 6, что неверно.
Если наши числа хорошо распределены, мы можем продолжать обрезать конечности. Если они могут быть сгруппированы в много больших или много маленьких, то выбрасывать их опасно.