Расчет квантилей без хранения
Я написал код на С ++ для вычисления 119 квантилей (от 10 ^ -7 до 1 — 10 ^ -7) из 100 миллионов чисел с двойной точностью.
Моя текущая реализация хранит числа в векторе, а затем сортирует вектор.
Есть ли способ рассчитать квантили без сохранения чисел?
Спасибо
ADDENDUM (извините за мой английский):
Вот что я делаю:
1) сгенерировать 20 равномерно распределенных случайных чисел в [0, 1)
2) Я подаю эти числа в алгоритм, который выводит случайное число с неизвестным средним и неизвестной дисперсией
3) сохранить номер на шаге 2
повторите 1, 2 и 3 100 миллионов раз (сейчас я собрал 10 ^ 8 случайных чисел с неизвестным средним и неизвестной дисперсией).
Теперь я сортирую эти числа, чтобы вычислить 119 квантилей от 10 ^ -7 до 1 — 10 ^ -7, используя формулу «R-2, SAS-5»:
https://en.wikipedia.org/wiki/Quantile#Estimating_quantiles_from_a_sample
Поскольку программа многопоточная, распределение памяти слишком велико, и я могу использовать только 5 потоков вместо 8.
Решение
Это проблема из области алгоритмы потоковой передачи (где вам нужно работать с потоком данных без сохранения каждого элемента).
Существуют хорошо известные алгоритмы для алгоритмов квантильных потоков (например, Вот), но если вы хотите использовать квантильные аппроксимации, это довольно простая проблема. Просто использовать отбор проб из пласта равномерно пробовать м снаружи N элементы, и рассчитать квантили на выборке (по методу, который вы сделали: сохранение м сэмплы в векторе и сортировка его). Размер м влияет на точность приближения (см., например, Вот).
Другие решения
Вам нужно знать набор чисел, прежде чем вы сможете рассчитать квантили.
Это может быть сделано путем сохранения чисел, но вы также можете создать / использовать многопроходный алгоритм, который изучает небольшую часть при каждом запуске.
Существуют также приближенные однопроходные алгоритмы для этой задачи, если допустима некоторая неточность в квантилях. Вот пример: http://www.cs.umd.edu/~samir/498/manku.pdf
РЕДАКТИРОВАТЬ ** Забыли, если на ваших номерах много дубликатов, вам просто нужно сохранить номер и сколько раз он появляется, а не каждый дубликат. В зависимости от входных данных это может быть существенной разницей.