Есть ли возможность считать медиану выборки инкрементально?

Question

[Alexeytur]

Добрый день.
Имеется программа, получающая по сети случайные числа и считающая по ним статистику. Программа должна уметь работать продолжительное время. Проблема с вычислением медианы - согласно определению, нужно отсортировать выборку и взять значение посередине массива. То есть нужно хранить все полученные значения. Но при больших объёмах поступающих данных/долгом времени работы закончится память и программа упадёт. Есть ли выход?

Answer 1

[dmshar]

Есть, и называется это Streaming Median:
https://programmingpraxis.com/2012/05/29/streaming...
https://habr.com/post/264987/
https://www.cse.wustl.edu/~jain/papers/ftp/psqr.pdf

Comments

[Alexeytur]

насколько я понял методы из https://habr.com/post/264987/ и https://www.cse.wustl.edu/~jain/papers/ftp/psqr.pdf, неточны, а метод с двумя кучами быстр для расчета, но также требует хранения всех поступивших значений. Получается, для точного вычисления медианы от этого никуда не деться.

[Lynn «Кофеман»]

> В работе Munro, Patterson (1980) заявлена теорема, которая говорит, что ничего лучше придумать нельзя и можно расходиться.

Т.е. либо приблизительное значение, либо хранить всё.

[Alexeytur]

Алексей Тен,
Можно частично уменьшить требования к памяти, способами из моего ответа

Answer 2

[Иван Клименко]

Если числа целые — можно хранить информацию о том, сколько и каких чисел поступило, а потом рассчитывать на основе этих данных медиану. Если числа не целые — можно попытаться свести их к целым.

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

Comments

[Alexeytur]

Спасибо. Так как мне нужно еще считать моду, я использую первый вариант - держу SortedDictionary, в котором хранятся пары число->частота числа.
Но с тем возникают проблемы: 1) Если диапазон поступающих чисел большой, то и этот словарь начинает сильно расти. 2) Для поиска медианы в таком словаре нужно проходить по нему циклом, а цикл по словарю медленный.

[Иван Клименко]

Alexeytur, это можно делать не с помощью словаря, а с помощью массива, если, конечно, у вас разумный разброс чисел. То интерпретировать число как индекс массива и инкрементировать значение в ячейке по этому индексу. Изначально массив должен быть заполнен нулями тогда.

[Alexeytur]

yeswell,
Этот вариант я смотрел, но в моей задаче диапазон чисел не определен.