用于计算百分位数以移除异常值的快速算法

Question

用于计算百分位数以移除异常值的快速算法

Eam*_*nne 18 c# c++ algorithm percentile

我有一个程序需要重复计算数据集的近似百分位数(顺序统计),以便在进一步处理之前删除异常值.我目前正在通过对值数组进行排序并选择适当的元素来实现这一目标; 这是可行的,但它在配置文件上是一个值得注意的昙花一现,尽管它是该计划的一个相当小的部分.

更多信息:

该数据集包含了100000浮点数字的顺序,并认为是"合理"分配 - 有不太可能在不久的特定值密度的重复,也不巨大的尖峰; 如果一些奇怪的原因分布为奇数,这是确定一个近似是不太准确的,因为数据很可能搞砸总之,进一步处理可疑.但是,数据不一定是统一的或正态分布的; 它不太可能退化.
近似解决方案没问题,但我确实需要了解近似值如何引入错误以确保其有效.
由于目标是去除异常值,我在任何时候都在同一数据上计算两个百分点:例如一个在95%,一个在5%.
该应用程序在C#中,在C++中有点繁重; 任何一个伪代码或预先存在的库都可以.
一个完全不同的去除异常值的方法也可以,只要它是合理的.
更新:似乎我正在寻找一种近似选择算法.

虽然这都是在一个循环中完成的,但每次数据(略微)都不同,因此重用数据结构并不像这个问题那样容易.

实施解决方案

使用Gronim建议的维基百科选择算法将这部分运行时间减少了大约20倍.

由于我找不到C#实现,这就是我想出的.即使对于小型输入,它也比Array.Sort更快; 在1000个元素上它快25倍.

public static double QuickSelect(double[] list, int k) {
    return QuickSelect(list, k, 0, list.Length);
}
public static double QuickSelect(double[] list, int k, int startI, int endI) {
    while (true) {
        // Assume startI <= k < endI
        int pivotI = (startI + endI) / 2; //arbitrary, but good if sorted
        int splitI = partition(list, startI, endI, pivotI);
        if (k < splitI)
            endI = splitI;
        else if (k > splitI)
            startI = splitI + 1;
        else //if (k == splitI)
            return list[k];
    }
    //when this returns, all elements of list[i] <= list[k] iif i <= k
}
static int partition(double[] list, int startI, int endI, int pivotI) {
    double pivotValue = list[pivotI];
    list[pivotI] = list[startI];
    list[startI] = pivotValue;

    int storeI = startI + 1;//no need to store @ pivot item, it's good already.
    //Invariant: startI < storeI <= endI
    while (storeI < endI && list[storeI] <= pivotValue) ++storeI; //fast if sorted
    //now storeI == endI || list[storeI] > pivotValue
    //so elem @storeI is either irrelevant or too large.
    for (int i = storeI + 1; i < endI; ++i)
        if (list[i] <= pivotValue) {
            list.swap_elems(i, storeI);
            ++storeI;
        }
    int newPivotI = storeI - 1;
    list[startI] = list[newPivotI];
    list[newPivotI] = pivotValue;
    //now [startI, newPivotI] are <= to pivotValue && list[newPivotI] == pivotValue.
    return newPivotI;
}
static void swap_elems(this double[] list, int i, int j) {
    double tmp = list[i];
    list[i] = list[j];
    list[j] = tmp;
}

Run Code Online (Sandbox Code Playgroud)

性能图