c++ - 计算分位数而不存储

Question

我编写了 C++ 代码来计算 1 亿个 double 的 119 个分位数(从 10^-7 到 1 - 10^-7)。 我当前的实现将数字存储在一个 vector 中，然后对 vector 进行排序。 有什么方法可以在不存储数字的情况下计算分位数吗？

谢谢

附录(对不起我的英文): 这是我正在做的:

1) 在[0, 1)中生成20个均匀分布的随机数

2) 我将这些数字输入一个算法，该算法输出一个均值和方差未知的随机数

3) 存储第2步的数字

重复 1、2 和 3 1 亿次(现在我收集了 10^8 个均值和方差未知的随机数)。

现在，我使用公式“R-2，SAS-5”对这些数字进行排序，计算从 10^-7 到 1 - 10^-7 的 119 个分位数: https://en.wikipedia.org/wiki/Quantile#Estimating_quantiles_from_a_sample

由于程序是多线程的，内存分配太大，我只能使用5个线程而不是8个。

Answer 1

这是streaming algorithms领域的问题(您需要在不存储每个元素的情况下对数据流进行操作)。

分位数流算法有众所周知的算法(例如 here )，但如果您愿意使用分位数近似值，这是一个相当简单的问题。只需使用 reservoir sampling从 n 个元素中均匀采样 m，并计算样本的分位数(通过您所做的方法:将 m 样本存储在 vector ，并对其进行排序)。 m 的大小会影响近似值的精度(参见，例如 here)。