Быстрый алгоритм для повторного расчета процентиля?

Question

В алгоритме я должен вычислять 75-й процентиль набора данных при каждом добавлении значения. Прямо сейчас я делаю это:

1. Получить значение x
2. Вставить x в уже отсортированный массив в конце
3. своп x вниз до сортировки массива
4. Считать элемент в позиции array[array.size * 3/4]

Точка 3 - это O (n), а остальное - O (1), но это все еще довольно медленно, особенно если массив увеличивается. Есть ли способ оптимизировать это?

UPDATE

Спасибо, Никита! Поскольку я использую 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;
};

Answer 1

Вы можете сделать это с двумя кучами . Не уверен, что есть менее «надуманное» решение, но оно обеспечивает O(logn) сложность времени, и кучи также включены в стандартные библиотеки большинства языков программирования.

Первая куча (куча A) содержит наименьшие 75% элементов, другая куча (куча B) - остальные (самые большие 25%). Первый имеет самый большой элемент сверху, второй - самый маленький.

1. Добавление элемента.

Проверьте, является ли новый элемент x <= <code>max(A). Если это так, добавьте его в кучу A, в противном случае - в кучу B.
Теперь, если мы добавили x в кучу A и она стала слишком большой (содержит более 75% элементов), нам нужно удалить самый большой элемент из A (O (logn)) и добавить его в кучу B (также O (LOGN)).
Похоже, если куча B стала слишком большой.

2. Нахождение "0,75 медианы"

Просто возьмите самый большой элемент из A (или самый маленький из B). Требуется время O (logn) или O (1), в зависимости от реализации кучи.

редактировать
Как отмечалось Dolphin , нам нужно точно указать, насколько большой должна быть каждая куча для каждого n (если мы хотим получить точный ответ). Например, если size(A) = floor(n * 0.75) и size(B) - это остаток, то для каждого n > 0, array[array.size * 3/4] = min(B).

Answer 2

Для этого достаточно простого дерева статистики заказов .

Сбалансированная версия этого дерева поддерживает вставку / удаление времени O (logn) и доступ по рангу.Таким образом, вы получаете не только 75% -ный процентиль, но также 66% или 50% или все, что вам нужно, без необходимости менять код.

Если вы часто получаете 75% -ный процентиль, но вставляете его режевы всегда можете кэшировать 75% процентиль элемента во время операции вставки / удаления.

Большинство стандартных реализаций (например, TreeMap в Java) представляют собой деревья статистики заказов.

Answer 3

Вот решение 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);

Answer 4

Если у вас есть известный набор значений, следующее будет очень быстрым:

Создайте большой массив целых чисел (будут работать даже байты) с количеством элементов, равным максимальному значению ваших данных.Например, если максимальное значение 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;

Можно также рассмотреть возможность использования TreeMap вместо массива, если значения не подтверждают эти ограничения.

Answer 5

Вы можете использовать бинарный поиск, чтобы найти правильную позицию в O (log n).Тем не менее, сдвиг массива вверх все равно O (n).