получение среднего, p95 и p99 потока данных

Question

У меня есть входящие данные, и я хочу вычислить средний, 95-й и 99-й процентиль этих данных - меня больше всего интересуют последние 1000 значений. В любой момент я хотел бы запросить этот объект, чтобы получить любое из трех значений (это может произойти в любое время, а не только в том случае, когда числа, увиденные по модулю 1000, равны 0). Есть ли способ получить эти три значения без сохранения последних 1000 выборок?

Это не должно быть идеальным, поэтому мы можем использовать некоторые трюки, чтобы получить хорошую оценку. Кроме того, скорость - еще одна проблема. Благодаря

(я буду делать это в C++, но я не думаю, что дело все, что много)

Answer 1

Как минимум, вам необходимо поддерживать очередь самых последних 1000 элементов.

Чтобы сохранить среднее значение, поддерживайте общее количество последних 1000 элементов; когда вы добавляете новый элемент в очередь, вы добавляете его значение в общую сумму, а также вычитаете значение самого старого элемента, который вы только что удалили из очереди. Верните общее количество, разделенное на 1000, и вы идете.

Чтобы сохранить работоспособность Nth процентили, поддерживайте две кучи и сохраняйте количество элементов в кучах; «нижняя» куча имеет более низкий N% значений, а «верхняя» куча имеет верхний (1-N)% (например, нижняя 95-ая процентильная куча будет иметь 950 элементов, а верхняя пятая процентильная куча будет имеют 50 элементов). В любой момент вы можете вернуть самый низкий элемент из верхней кучи, и это ваш процентиль. Когда вы удаляете элемент из очереди последних значений, удалите также значение из кучек. Если это оставляет кучи несбалансированными (например, нижняя куча имеет 951 элемент, а верхняя куча имеет 49 элементов), то сдвигайте элементы, чтобы сбалансировать их (например, удалите верхний элемент из нижней кучи и добавьте его в верхнюю кучу).

Поскольку вы хотите два процентиля, используйте три кучи - нижняя куча имеет нижние 950 элементов, средняя - 40, а верхняя - самая высокая 10. Верните самый нижний элемент средней кучи для 95-го процентиля , и самый нижний элемент верхней кучи для 99-го процентиля.

Добавление и удаление кучевых элементов - это O (lg (n)), так что это затраты на добавление нового элемента в очередь и три кучи: удаление самого старого элемента очереди из кучек (O (lg (n)), добавьте новый элемент очереди в соответствующую кучу (O (lg (n)) и, если нужно, сравните кучи (опять же, O (lg (n)). Добавьте новый элемент в самую низкую кучу, больше, чем элемент кучи, т.е.

if (newElement < lowestHeap.maxElement) { 
    lowestHeap.add(newElement) 
} else if (newElement < middleHeap.maxElement) { 
    middleHeap.add(newElement) 
} else { 
    highestHeap.add(newElement) 
} 

Убедитесь, что ваши отвалы позволяют дублирующие элементы

Answer 2

Сначала давайте предположим, что вы можете позволить себе хранить 1000 числа (скажем, к раз 1000, где к постоянной).

Keep 3 кучки:

1. minheap для хранения 10 (или 50) элементов (heapA)
2. maxheap хранить остальные 990 (или 950 элементов) (heapB)
3. minheap к соблюдайте порядок элементов. Самый старый элемент всегда находится на вершине этой кучи heapC)

Три кучи являются особенными: heapC также сохраняет ссылку на соответствующий элемент в heapA или heapB. heapA и heapB также отслеживают один и тот же элемент в heapC.

Это так, как это работает:

1. Предположим, у вас есть 1000 элементов в системе. heapA имеет 10 элементов, heapB 990 и heapC имеет 1000 элементов
2. Удалить самый старый элемент из системы. Удалите его из heapC и используя ссылку удалить его из heapA или heapB
3. Перебалансируйте три кучи.
4. Добавить новый элемент в heapA или heapB в зависимости от вершины heapA
5. Добавить порядок элементов в heapC.
6. Выполняя это, также добавляйте ссылки друг другу.