C ++快速百分位数计算

Question

我正在尝试编写一个百分位函数，它将2个向量作为输入，1个向量作为输出。输入向量之一（Distr）将是随机数的分布。另一个输入向量（测试）将是我想要从Distr计算百分位数的值向量。输出将是一个向量（与测试大小相同），它返回测试中每个值的百分位数。

以下是我想要的一个例子：

Input Distr = {3, 5, 8, 12}
Input Tests = {4, 9}
Output Percentile = {0.375, 0.8125}

以下是我在C ++中的实现：

vector<double> Percentile(vector<double> Distr, vector<double> Tests)
{
    double prevValue, nextValue;
    vector<double> result;
    unsigned distrSize = Distr.size();

    std::sort(Distr.begin(), Distr.end());

    for (vector<double>::iterator test = Tests.begin(); test != Tests.end(); test++)
    {

        if (*test <= Distr.front())
        {
            result.push_back((double) 1 / distrSize); // min percentile returned (not important)
        }
        else if (Distr.back() <= *test)
        {
            result.push_back(1); // max percentile returned (not important)
        }
        else
        {
            prevValue = Distr[0];
            for (unsigned sortedDistrIdx = 1; sortedDistrIdx < distrSize; sortedDistrIdx++)
            {
                nextValue = Distr[sortedDistrIdx];

                if (nextValue <= *test)
                {
                    prevValue = nextValue;
                }
                else
                {
                    // linear interpolation
                    result.push_back(((*test - prevValue) / (nextValue - prevValue) + sortedDistrIdx) / distrSize);
                    break;
                }
            }
        }
    }
    return result;
}

Distr和Tests的大小可以从2,000到30,000。

是否有任何现有的库可以计算百分位数如上所示（或类似）？如果不能，我怎样才能更快地完成上述代码？

Answer 1

您的问题有一个线性算法（两种尺寸的线性时间对数）。你需要对两个向量进行排序，然后有两个迭代器通过每个向量（itDistr，itTest）。有三种可能性：

1. itDistr * <*测试

在这里，除了增加itDistr之外你什么都没有。

2. itDistr *> = *测试

当您找到* itTest是区间[ *(itDistr-1), *itDistr )的元素的测试用例时就是这种情况。所以你必须进行你使用的插值（线性），然后增加itTest。

第三种可能性是其中任何一个到达其容器向量的末尾。您还必须定义在开头和结尾处发生的事情，这取决于您从数字序列中定义分布的方式。

是否有任何现有的库可以计算百分位数如上所示（或类似）？

可能，但它很容易实现，你可以很好地控制插值技术。

Answer 2

我会做点什么的

vector<double> Percentile(vector<double> Distr, vector<double> Tests)
{
    double prevValue, nextValue;
    vector<double> result;
    unsigned distrSize = Distr.size();

    std::sort(Distr.begin(), Distr.end());

    for (vector<double>::iterator test = Tests.begin(); test != Tests.end(); test++)
    {
        if (*test <= Distr.front())
        {
            result.push_back((double) 1 / distrSize); // min percentile returned (not important)
        }
        else if (Distr.back() <= *test)
        {
            result.push_back(1); // max percentile returned (not important)
        }
        else
        {
            auto it = lower_bound(Distr.begin(), Distr.end(), *test);
            prevValue = *(it - 1);
            nextValue = *(it + 1);
            // linear interpolation
            result.push_back(((*test - prevValue) / (nextValue - prevValue) + (it - Distr.begin())) / distrSize);
        }
    }
    return result;
}

请注意，我不是在每个测试的Distr上进行线性搜索，而是利用Distr进行排序并进行二进制搜索的事实（使用lower_bound）。

Answer 3

如果两个测试都很大，那么测试的每个元素的Distr的线性搜索将是主要的时间量。

当Distr大得多时，进行二分搜索而不是线性搜索要快得多。 std中有一个二进制搜索算法。你不需要写一个。

当测试几乎与Distr或更大的测试一样大时，进行索引排序测试然后按顺序排列两个排序列表一起存储结果，然后在下一次传递中输出存储的结果。

编辑：我看到Csaba Balint的回答更详细地介绍了“通过两个排序列表一起排序”的含义。

编辑：正在讨论的基本方法是： 1）对两个列表进行排序，然后线性处理，时间为NlogN + MlogM 2）只对一个列表和二进制搜索进行排序，时间（N + M）logM 3）只排序其他列表和分区，时间我还没想到，但是在N和M类似的情况下，它必须比方法1或2大，并且在N足够小的情况下必须小于方法1或2。

Answer 4

这个答案与input最初是随机的（未排序）和test.size()小于input.size()的情况有关，这是最常见的情况。

假设只有一个测试值。然后你只需要根据这个值对input进行分区，并获得下（上）分区的上（下）界限来计算各自的百分位数。这比输入的完全排序要快得多（quicksort实现为分区的递归）。

如果test.size()>1，那么你首先排序test（理想情况下，test已经排序，您可以跳过此步骤），然后按递增顺序继续测试元素，每次只分区上一部分的上部分。由于我们还跟踪上部分区的下限（以及下部分区的上限），我们可以检测连续测试元素之间是否没有输入数据，并避免分区。

该算法应该接近最优，因为没有生成不必要的信息（就像使用完整的input一样）。

如果后续分区将输入大致分成两半，则算法将是最佳的。这可以通过不按test的递增顺序进行近似，而是通过随后将test减半，即从中位数测试元素开始，然后是第一和第三四分位数等。