У меня есть программа, которая должна многократно вычислять приблизительный процентиль (статистику заказа) набора данных, чтобы удалить выбросы перед дальнейшей обработкой.В настоящее время я делаю это, сортируя массив значений и выбирая соответствующий элемент;это выполнимо, но это заметный всплеск в профилях, несмотря на то, что это довольно незначительная часть программы.
Дополнительная информация:
- Набор данных содержит порядка до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;
}
Спасибо, Гроним, за то, что указал мне правильное направление!