Быстрый алгоритм для повторного расчета процентиля?
-
03-10-2019 - |
Вопрос
В алгоритме я должен рассчитать 75-й процентиль данных набора данных, когда я добавляю значение. Прямо сейчас я делаю это:
- Получить значение
x
- Вставлять
x
в уже отсортированном массиве сзади - обмен
x
вниз, пока массив не будет отсортирован - Прочитайте элемент в положении
array[array.size * 3/4]
Точка 3 - O (n), а остальное o (1), но это все еще довольно медленно, особенно если массив становится больше. Есть ли способ оптимизировать это?
ОБНОВИТЬ
Спасибо Никиту! Поскольку я использую C ++, это решение простое для реализации. Вот код:
template<class T>
class IterativePercentile {
public:
/// Percentile has to be in range [0, 1(
IterativePercentile(double percentile)
: _percentile(percentile)
{ }
// Adds a number in O(log(n))
void add(const T& x) {
if (_lower.empty() || x <= _lower.front()) {
_lower.push_back(x);
std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
} else {
_upper.push_back(x);
std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
}
unsigned size_lower = (unsigned)((_lower.size() + _upper.size()) * _percentile) + 1;
if (_lower.size() > size_lower) {
// lower to upper
std::pop_heap(_lower.begin(), _lower.end(), std::less<T>());
_upper.push_back(_lower.back());
std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
_lower.pop_back();
} else if (_lower.size() < size_lower) {
// upper to lower
std::pop_heap(_upper.begin(), _upper.end(), std::greater<T>());
_lower.push_back(_upper.back());
std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
_upper.pop_back();
}
}
/// Access the percentile in O(1)
const T& get() const {
return _lower.front();
}
void clear() {
_lower.clear();
_upper.clear();
}
private:
double _percentile;
std::vector<T> _lower;
std::vector<T> _upper;
};
Решение
Вы можете сделать это с двумя куча. Отказ Не уверен, есть ли менее «надуманный» решение, но это обеспечивает O(logn)
Сложность и куча также включены в стандартные библиотеки большинства языков программирования.
Первая куча (куча а) содержит самые маленькие 75% элементов, другая куча (куча b) - остальные (крупные 25%). Первый имеет самый большой элемент на вершине, второй - самый маленький.
- Добавление элемента.
Посмотрите, если новый элемент x
это <= max(A)
. Отказ Если это так, добавьте его в кучу A
, в противном случае - до куча B
.
Теперь, если мы добавили x
Куча а и стало слишком большим (удерживает более 75% элементов), нам нужно удалить самый большой элемент из A
(O (logn)) и добавьте его в куча b (также o (logn)).
Похоже, если куча b стала слишком большой.
- Найти "0,75 медиана"
Просто возьмите самый большой элемент из (или наименьшего из б). Требуется O (logn) или o (1) время, в зависимости от реализации кучи.
редактировать
Так как Дельфин Отмечено, нам нужно точно указать, насколько большая каждая куча должна быть для каждого N (если мы хотим точный ответ). Например, если size(A) = floor(n * 0.75)
а также size(B)
это остальное, то для каждого n > 0
, array[array.size * 3/4] = min(B)
.
Другие советы
Простой Заказать статистику дерева Достаточно для этого.
Сбалансированная версия этого дерева поддерживает o (logn) Время вставки / удаления и доступа по рангу. Таким образом, вы не только получаете 75% процентилей, но и на 66% или 50% или что вам нужно без необходимости менять свой код.
Если вы часто обратитесь к 75% процентиляю, но только вставляете реже, вы всегда можете кэшировать 75% процентильного элемента во время операции вставки / удаления.
Большинство стандартных реализаций (например, Java's Treemap) являются статистическими деревьями заказа.
Вы можете использовать двоичный поиск, чтобы найти правильную позицию в O (log n). Тем не менее, смещение массива вверх по-прежнему O (n).
Вот решение JavaScript. Скопируйте его в консоль браузера, и она работает. $scores
содержит список оценок и, $percentile
дает n-th percentile
списка. Таким образом, 75-й процентиль составляет 76,8 и 99 процентилей 87,9.
function get_percentile($percentile, $array) {
$array = $array.sort();
$index = ($percentile/100) * $array.length;
if (Math.floor($index) === $index) {
$result = ($array[$index-1] + $array[$index])/2;
}
else {
$result = $array[Math.floor($index)];
}
return $result;
}
$scores = [22.3, 32.4, 12.1, 54.6, 76.8, 87.3, 54.6, 45.5, 87.9];
get_percentile(75, $scores);
get_percentile(90, $scores);
Если у вас есть известный набор значений, следующее будет очень быстро:
Создание большого массива целых чисел (даже байты будут работать) с количеством элементов, равных максимальному значению ваших данных. Например, если максимальное значение t составляет 100 000, создайте массив
int[] index = new int[100000]; // 400kb
Теперь итерации по всему набору ценностей, как
for each (int t : set_of_values) {
index[t]++;
}
// You can do a try catch on ArrayOutOfBounds just in case :)
Теперь рассчитайте процентиль как
int sum = 0, i = 0;
while (sum < 0.9*set_of_values.length) {
sum += index[i++];
}
return i;
Вы также можете рассмотреть возможность использования TREEWAP вместо массива, если значения не подтверждают эти ограничения.