Как выбирать данные для оценки медианы: последовательный проход или случайная подвыборка

Что проверяют

Понимаете ли вы, что «первые N строк» это не выборка, и умеете ли оценить погрешность приближённой медианы. В задаче из категории coding следом часто просят написать reservoir sampling или медиану потока на двух кучах.

Как отвечать

Сначала уточните условия: помещаются ли данные в память, упорядочены ли они (по времени, по ключу), сколько проходов допустимо, какая нужна точность.

• данные в памяти: считайте точную медиану через np.median или quickselect за O(n) в среднем. Подвыборка тут ничего не даёт;
• последовательный проход по первым N: это не случайная выборка. Если файл отсортирован по дате или id, а значение с ними связано, оценка смещена сколь угодно сильно;
• случайная подвыборка за один проход: reservoir sampling держит k элементов и с вероятностью k/i заменяет случайный из них i-м элементом потока. Выборка получается равномерной без знания длины потока. Проще бернуллиевская выборка: каждая строка берётся с вероятностью p;
• скетчи: KLL, t-digest, алгоритм GK дают квантили с контролируемой ошибкой за один проход и в малой памяти. В Spark это approxQuantile с параметром relativeError, KLL есть в Apache DataSketches.

Погрешность выборки считают по рангу, а не по значению. По неравенству DKW (Дворецкий, Кифер, Вольфовиц) около 18 тысяч элементов дают ошибку ранга не больше 1% с вероятностью 95%, и от размера исходных данных это не зависит. Ошибка в единицах измерения зависит от плотности данных около медианы.

Медиана потока на двух кучах (max-heap для нижней половины, min-heap для верхней, в Python через heapq с отрицанием) точна, но хранит все элементы.

Где спотыкаются

Берут df.head(n) или одну партицию как выборку. На упорядоченных данных это систематическая ошибка, которую не видно, пока не сравнишь с полным расчётом.

Усредняют медианы частей. Среднее медиан по партициям не равно общей медиане, если партиции разного размера или с разным распределением.

Пишут, что случайная подвыборка «снижает влияние выбросов». Медиана устойчива к выбросам сама, выборка только добавляет случайную ошибку, и её нужно уметь оценить.