我有一个程序需要重复计算数据集的近似百分位数（顺序统计量），以便在进一步处理之前去除异常值。目前的做法是通过对值数组进行排序并选择适当的元素来实现；虽然这是可行的，但它占用了程序中相当小的一部分，但在性能分析中是明显的短板。
更多信息：
- 数据集包含大约高达100000个浮点数，并且假定为“合理”分布 - 不太可能存在重复项或密度在特定值附近的巨大峰值；如果由于某种奇怪的原因分布很奇怪，则不精确的近似值也可以接受，因为数据可能已经混乱，进一步处理也是可疑的。但是，数据不一定是均匀或正态分布的；它只是非常不可能退化。 - 近似解决方案是可以的，但我需要了解近似如何引入误差，以确保它有效。 - 由于旨在去除异常值，因此始终在同一数据上计算两个百分位数：例如95％和5％。 - 应用程序使用C＃编写，其中部分重要工作使用C ++完成；伪代码或现有库都可以。 - 只要合理，完全不同的去除异常值的方法也可以接受。
更新：看起来我正在寻找一种近似的选择算法。
更多信息：
- 数据集包含大约高达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;
}
QuickSelect(values, (int)(values.Length*0.05+0.5))。如果你想要第95个百分位数，使用QuickSelect(values, (int)(values.Length*0.95+0.5))- 注意，你必须将0.05和0.95的小数索引四舍五入为整数索引，除非你的列表长度是20的倍数。如果你的列表很短，你可能考虑插值而不是只选择一个索引，但对于大多数用途来说，我认为这并不重要 - 如果你不关心选择5%，那么你可能不在乎它实际上是4.8%或其他什么 - 总的来说，没有确切的第5个百分位数。 - Eamon Nerbonne