У меня есть процесс, который генерирует значения и что я наблюдаю. Когда процесс завершается, я хочу вычислить медиану этих значений.
Если мне приходилось вычислять среднее значение, я мог бы просто сохранить сумму и количество сгенерированных значений и, следовательно, иметь потребность в O (1) памяти. Как насчет медианы? Есть ли способ сэкономить на очевидном O (n), исходящем из хранения всех значений?
Изменить: Заинтересованы в 2 случаях: 1) известна длина потока, 2) это не так.
Вам нужно будет хранить как минимум точки ceil (n/2), так как любая из первых n/2 точек может быть медианной. Вероятно, проще всего просто сохранить точки и найти медианную. Если точки сохранения ceil (n/2) имеют значение, то прочитайте в первых n/2 точках в отсортированный список (возможно, лучшее бинарное дерево), затем, когда новые точки добавляются, выкидывают низкие или высокие точки и сохраняют отслеживать количество точек на обоих концах.
Edit:
Если длина потока неизвестна, то, очевидно, как заметил Стивен в комментариях, у нас нет выбора, кроме как запомнить все. Если бы повторяющиеся элементы были вероятными, мы могли бы сэкономить немного памяти, используя идею Dolphins о хранении значений и значений.
Вы можете
k различные значения означают сохранение O(k) памяти)O(n).Если у вас есть дискретные значения и много повторений, вы можете сохранить значения и подсчеты, что бы сэкономить немного места.
Возможно, на этапах вычисления вы можете отбросить верхние "n" и "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, которая неверна.
Если наши числа хорошо распределены, мы можем продолжать обрезать конечности. Если они могут быть сгруппированы во множестве больших или больших количеств, то отбрасывание является рискованным.
У меня была такая же проблема, и я получил способ, который не был опубликован здесь. Надеюсь, мой ответ поможет кому-то в будущем.
Если вы знаете свой диапазон значений и не очень заботитесь о точности медианных значений, вы можете постепенно создавать гистограмму квантованных значений, используя постоянную память. Тогда легко найти медиану или любую позицию значений с вашей ошибкой квантования.
Например, предположим, что ваш поток данных представляет собой значения пикселей изображения, и вы знаете, что эти значения являются целыми числами, все находятся в пределах 0 ~ 255. Чтобы постепенно создавать гистограмму изображения, просто создайте 256 счетчиков (бинов), начиная с нулей, и считайте один на бине, соответствующий значению пикселя, при сканировании через вход. После создания гистограммы найдите первое кумулятивное число, которое больше половины размера данных, чтобы получить медиану.
Для данных, которые являются действительными числами, вы все равно можете вычислить гистограмму, чтобы каждый столбец имел квантованные значения (например, наборы из 10, 1 или 0,1 и т.д.), В зависимости от ожидаемого диапазона значений данных и требуемой точности.
Если вы не знаете диапазон значений всей выборки данных, вы все равно можете оценить возможный диапазон значений медианы и вычислить гистограмму в этом диапазоне. По своей природе это отклонение от нормы, но это именно то, что мы хотим при вычислении медианы.