计算分位数而无需存储

Question

计算分位数而无需存储

4

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

谢谢

补充说明（抱歉我的英语）：这是我正在做的事情： 1）在[0, 1)中生成20个均匀分布的随机数 2）将这些数字输入算法，输出具有未知均值和未知方差的随机数 3）在第2步中存储数字重复1、2和3共1亿次（现在我收集了具有未知均值和未知方差的1亿个随机数）。现在我对这些数字进行排序，使用“R-2，SAS-5”公式计算从10^-7到1-10^-7的119个分位数：https://en.wikipedia.org/wiki/Quantile#Estimating_quantiles_from_a_sample 由于程序是多线程的，内存分配太大，我只能使用5个线程而不是8个。

- Cristiano

3

如果你不存储这些数字，那么你如何在以后检索它们？你究竟想做什么？ - RedX

2

有一种众所周知的方法可以使用堆来找到分布的中位数。看看你的特定问题是否适用于类似的方法？ - Carlos

1

您是指“不存储”还是“不排序”？ - arekolek

是的，你会这么想。很难想象在不存储数字的情况下如何解决这个问题，因为本质上你正在查看一个直方图并决定在哪里切割它。我没有考虑过的一件事是，这是一个在线算法还是一次性算法？ - Carlos

1

@RedX：计算一组数的最小值/最大值可以在不存储数字的情况下完成。这个问题是关于一般化的。 - user1196549

显示剩余6条评论

2个回答

2

在计算分位数之前，您需要知道一组数字。您可以通过存储数字来完成这个任务，但也可以使用多次算法，每次运行学习一小部分。如果对分位数的某些不准确有所容忍，也可以使用近似的一次算法解决此问题。这里是一个示例：http://www.cs.umd.edu/~samir/498/manku.pdf。编辑**如果您的数字具有许多重复项，则只需要存储数字及其出现次数，而不是每个重复项。根据输入数据，这可能会产生明显的差异。

- Koebmand STO

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ami Tavory · Accepted Answer

这是一个涉及流算法的问题（需要在不存储每个元素的情况下对数据流进行操作）。

已有众所周知的分位数流算法（例如，这里），但如果您愿意使用分位数近似，则这是一个相当简单的问题。只需使用蓄水池抽样从n个元素中均匀采样m个，并在样本上计算分位数（通过您所做的方法：将m个样本存储在向量中并对其进行排序）。大小m影响近似精度（请参见，例如，这里）。