不存储计算分位数

Question

我编写了c++代码来计算一亿个双精度数字的119个分位数(从10^-7到1- 10^-7)。我当前的实现将数字存储在一个向量中，然后对向量进行排序。有没有办法计算分位数而不存储数字？

谢谢

附录(对不起我的英语)：这是我正在做的事情：

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

这是来自字段的问题(您需要在不存储每个元素的情况下对数据流进行操作)。

有一些众所周知的分位流算法(例如，here)，但如果您愿意使用分位数近似，这是一个相当容易的问题。只需使用对n个元素中的m个元素进行均匀采样，并计算样本上的分位数(使用您所使用的方法:将m个样本存储在一个向量中，并对其进行排序)。尺寸m会影响近似的精度(例如，请参见here)。

Answer 2

在计算分位数之前，您需要知道这组数字。

这可以通过存储数字来完成，但您也可以创建/使用多遍算法，该算法在每次运行时都会学习一小部分。

对于这个问题，如果分位数上的一些不准确是可以接受的，也有近似的一次通过算法。下面是一个示例：http://www.cs.umd.edu/~samir/498/manku.pdf

编辑**忘记了，如果你的数字有很多重复项，你只需要存储数字和它出现的次数，而不是每个重复项。根据输入数据的不同，这可能是一个显着的差异。