Постепенное вычисление медианы с максимальной эффективностью памяти

Question

У меня есть процесс, который генерирует ценности и который я наблюдаю. Когда процесс завершится, я хочу вычислить медиану этих значений.

Если бы мне нужно было вычислить среднее значение, я мог бы просто сохранить сумму и количество сгенерированных значений и, таким образом, потребовать O (1) памяти. Как насчет медианы? Есть ли способ сэкономить на очевидном O (n), полученном при хранении всех значений?

Редактировать: Интересуют 2 случая: 1) длина потока известна, 2) нет.

Answer 1

Вам нужно будет хранить как минимум баллы ceil (n / 2), потому что любой из первых n / 2 баллов может быть медианой.Вероятно, проще всего просто сохранить точки и найти медиану.Если сохранение значений ceil (n / 2) имеет значение, то считайте первые n / 2 точки в отсортированный список (двоичное дерево, вероятно, лучше), а затем при добавлении новых точек отбрасывайте низкие или высокие точки и сохраняйтеотслеживание количества точек на обоих концах.

Редактировать:

Если длина потока неизвестна, то, очевидно, как заметил Стивен в комментариях, тогдаУ нас нет выбора, кроме как помнить все.Если вероятны повторяющиеся элементы, мы могли бы сэкономить немного памяти, используя идею Dolphins для хранения значений и счетчиков.

Answer 2

Вы можете

• Использовать статистику, если это приемлемо - например, вы можете использовать выборку.
• Использовать знания о вашем потоке номеров
  • , используя подсчетПодход, подобный сортировке: k различные значения означают хранение O(k) памяти)
  • или сбросить известные выбросы и сохранить (высокий, низкий) счетчик.
  • Если вы знаете, что у вас нет дубликатов, вы можете использовать растровое изображение ... но это просто меньшая константа для O(n).

Answer 3

Если у вас есть дискретные значения и много повторений, вы можете сохранить значения и счетчики, что сэкономит немного места.

Возможно на этапах вычислений вы можете отбросить верхние и нижние значения n, если вы уверены, что медиана не находится в этом верхнем или нижнем диапазоне.
Например, допустим, вы ожидаете 100 000 значений.Каждый раз, когда ваш сохраненный номер достигает (скажем) 12 000, вы можете сбросить самые высокие 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, что неверно.

Если наши числа хорошо распределены, мы можем продолжать обрезать конечности.Если они могут быть сгруппированы в большое или большое количество маленьких чисел, то отбрасывание рискованно.