Итак, у Вас есть какой-то поток данных. Большой такой поток. Или уже готовый набор. И хочется определить какие-то его характеристики. Алгоритм определения минимального и максимального значения могут придумать даже не программисты. Вычисление среднего уже чуть сложнее, но тоже не представляет никаких трудностей — знай подсчитывай себе сумму да инкрементируй счетчик на каждое новое значение. Среднеквадратичное отклонение — все то же самое, только числа другие. А как насчет медианы?
Для тех, кто забыл, что это такое, напоминаю — медиана (50-й перцентиль) выборки данных — это такое значение, которое делит эту выборку пополам — данные из одной половины имеют значение не меньше медианы, а из второй — не больше. Ценность её заключается в том, что её значение не зависит от величины случайных всплесков, которые могут очень сильно повлиять на среднее.
Строго говоря, из определения следует, что для вычисления точного значения медианы нам нужно хранить всю выборку, иначе нет никаких гарантий, что мы насчитали именно то, что хотели. Но для непрерывных и больших потоков данных точное значение все равно не имеет большого смысла — сейчас оно одно, а через новых 100 отсчетов — уже другое. Поэтому эффективный метод оценки медианы, который не будет требовать много памяти и ресурсов CPU, и будет давать точность порядка одного процента или лучше — как раз то что нужно.
Читать полностью »
