在内存密集型应用程序中计算百分位数

• 下载演示项目 - 6.41 KB
• 下载源代码 - 2.6 KB

引言

假设您有一长串数字，想要找到第 5^个和第 95^个百分位数。如果列表足够小，您可以将列表读入内存，对其进行排序，然后查看哪些数字分别从两端算起占 5%。很简单。但是，如果列表是按顺序生成的，并且整个列表太大而无法一次性放入内存，该怎么办？本文介绍了一个简单的 C++ 类来解决这个问题。该类接受模板参数，因此可以与任何数据类型一起使用。

动机应用

此处提出的解决方案可以用于各种内存密集型问题，但我将简要描述最初促使该代码产生的那个问题。作为其处理的一部分，统计软件包 WFMM 一次生成一个大矩阵的行，然后报告每一列的几个百分位数。如果能够一次生成一列数据，那就太好了，但事实并非如此。问题的性质是行可以独立计算，但列不能。此矩阵的大小根据输入而变化，可用内存决定了软件可以处理的最大问题大小。此处提供的代码在 WFMM 项目中用于节省内存。

背景

为了使问题具体化，假设我们有 1000 个数字，并且想知道如果我们将列表按升序排序，第 50^个数字会是什么。想象一下我们想用尽可能少的内存来完成这个任务。我们可以读取前 50 个数字并对它们进行排序。然后，当我们读取第 51^个数字时，我们将其与我们保存的 50 个数字中的最大值进行比较。如果新数字更大，我们会将其丢弃，因为我们知道它不可能是完整列表中第 50^个最小的数字。如果新数字更小，我们会丢弃我们正在保留的最大数字，并将新数字插入我们的缓存。这样，我们就可以使用 50 个内存位置来计算第 50^个最小的数字。显然，我们也可以使用类似的方法来查找第 50^个最大的数字。

我们能做得更好吗？不能。在我们看到最后 50 个数字之前，我们无法排除我们正在保存的任何一个数字是我们所寻找的那个数字的可能性。当我们看到第 951^个数字时，我们可以从缓存中排除一个数字。当我们看到第 952^个数字时，我们可以从缓存中再排除一个数字，等等。但对于算法的大部分运行时间，我们需要保留 50 个数字。

一般来说，如果你想在一个包含 M 个数字的列表中找到第 n^个最小的数字，你需要沿着过程中保存 n 个数字。（除非 n 大于 M 的一半。然后你可以颠倒问题，找到列表中第 (M-n)^个最大的数字。）所以，如果你想计算 M 个数字列表的第 5^个或第 95^个百分位数，你需要存储 0.05 M 个数字。如果你想找到第 5^个和第 95^个百分位数，你需要在过程中存储 0.10 M 个数字。通过只存储你需要的数字，你可以解决比先将所有内容加载到内存然后进行排序所能解决的问题大 10 倍的问题。

Using the Code

TailKeeper 类通过跟踪数字序列的“尾部”（最大值和最小值）来计算上述的上限和下限百分位数。在值到达时，它们被插入到哈希数据结构中。这使我们能够对存储的数字进行排序，并进行快速插入，而无需额外的内存。

该类使用模板来处理支持比较的任何数据类型，而不仅仅是数值类型。此外，输入类型和存储类型可能不同。在我们的应用中，输入数据类型为 `double`，但存储为 `float` 类型。这使我们在相同的内存中可以存储两倍的数据。数据中的噪声足够多，因此将 `double` 转换为 `float` 所损失的精度并不重要。

要在你的应用程序中使用 TailKeeper，请 `#include` 文件 _TailKeeper.h_ 和 _FixedSizeHeap.h_。该类需要两个常量来指定你正在寻找哪些值。如果你想找到第 **m**^个最小和第 **n**^个最大值，你可以在构造函数或 `Initialize` 函数的参数中指定 **m** 和 **n**。

例如，假设你想在一个 `double` 列表（你愿意将输入转换为 `float` 以节省空间）中查找第 40^个最小和第 10^个最大元素。你可以这样声明一个 `TailKeeper` 类：

 

TailKeeper<double, float> tk(40, 10);

输入类型默认为 `double`，存储类型默认为 `float`，因此在这种情况下可以省略 `<double, float>`。

当列表中的每个值可用时，通过调用 `AddSample` 方法将其插入 TailKeeper：

tk.AddSample( x );

要沿途查找第 40^个最小元素，请调用 `GetMaxLeftTail()`。类似地，要查找第 10^个最大元素，请调用 `GetMinRightTail()`。（在任何时候看到的最小的 40 个元素构成左尾部，因此这些元素中的最大值就是第 40^个最小的。最大的 10 个元素是右尾部，因此这些元素中的最小值就是第 10^个最大的。）

测试代码

演示项目首先通过检查和插入几个值，并将堆的内部状态与手动计算结果进行比较，来测试 TailKeeper 所依赖的 FixedSizeHeap 类。

然后，项目创建一个包含 1000 个随机整数的列表，并直接使用 TailKeeper 通过对列表进行排序来查找第 5^个和第 96^个百分位数。

///////////////////////////////////////////////////////////////////////
// Generate a list of random integers.
int length = 1000;
std::vector data(length);
data[0] = 137; // arbitrary seed
for (int i = 1; i != length; ++i)
{
    // This is George Marsaglia's "CONG" random number generator.
    data[i] = 69069*data[i-1] + 1234567;
}

///////////////////////////////////////////////////////////////////////
// Find the 50th smallest and 40th largest elements using TailKeeper.
int lower = 50, upper = 40;
TailKeeper<int, int> tk(lower, upper);
for (int i = 0; i != length; ++i)
    tk.AddSample( data[i] );
int leftTailTK = tk.GetMaxLeftTail();
int rightTailTK = tk.GetMinRightTail();

///////////////////////////////////////////////////////////////////////
// Find the same values directly by sorting the entire list.
std::sort(data.begin(), data.end());
int leftTailSort = data[lower-1];
int rightTailSort = data[length - upper];

///////////////////////////////////////////////////////////////////////
// Compare the results.
assert(leftTailTK == leftTailSort);
assert(rightTailTK == rightTailSort);

为了进一步测试，你可以更改随机数生成器的种子值 `data[0]` 或 `length`、`upper` 和 `lower` 参数的值。

历史

• 2008 年 4 月 28 日：首次发布