Алгоритм быстрого обновления медианы
Предположим, что в определенный момент времени у вас есть коллекция N числа и знать средний элемент: M, Теперь вы получили новое значение, Xи поэтому вам может потребоваться обновить M, (Или, скорее, вам понадобится, если предположить, что числа, с которыми вы имеете дело, уникальны. Кроме того, все выборки принимаются последовательно, поэтому проблем с параллелизмом не возникает.)
Вычислить новое среднее значение просто: возьмите старое среднее, добавьте X, умножить на Nи разделить на N + 1, (Это ясно из проверки того, как определяется среднее из N элементов. На данный момент я не слишком беспокоюсь о числах.)
Мой вопрос: может ли кто-нибудь предложить творческий / новый (или, возможно, доказуемо-оптимальный) подход к проблеме обновления медианы? Ниже я приведу пример (простая идея моего собственного дизайна) с небольшим анализом:
В этом примере я буду использовать std::forward_list, поскольку в C ++ 11 я столкнулся с этим совсем недавно. Без потери общности, я собираюсь предположить, что вы идете по этому пути правильно: ведение упорядоченного списка элементов (типа T), с которыми встречались до сих пор, std::forward_list<T> sorted; когда T x; просто сложите его на место, используя:
sorted.merge(std::forward_list<T> {{ x }});
Кстати, мне любопытно, есть ли у кого-нибудь лучший (более эффективный / элегантный) метод для этого. Нарушения приветствуются.
Так, X сейчас является частью sortedи вот моя идея, в двух словах:
auto it = sorted.begin(), itend = sorted.end();
typename std::forward_list<T>::size_type count = std::distance(it, itend);
for (const auto &e : sorted) {
if (it == itend || ++it == itend) {
M = (count % 2) ? e : (e + M) / 2;
break;
} else { ++it; }
}
Хорошая (если не довольно трудная для понимания) вещь, которая здесь происходит, заключается в следующем: поскольку вы перемещаете итератор вперед дважды (и безопасно, я мог бы добавить, хотя и ценой двух сравнений) для каждого элемента, когда end() достигается, мы будем на правильное (медианное) значение. Если есть нечетное количество элементов, M это просто образец, если нет, то это просто среднее значение этого элемента и старая (вытесненная) медиана. Потому что чередуются нечетные и четные числа, старые или новые M на самом деле будет в коллекции. Это рассуждение обоснованно, да?
Вам не нужно комментировать мой метод O (3n), если вы думаете, что он лучше, чем ваш; Я просто предлагаю это как отправную точку.
Решение
Вы могли бы использовать std::setи тот факт, что вставка в наборы не сделает недействительными итераторы.
Вы можете держать итератор mIt к срединному элементу множества, если N нечетно, и слева от двух срединных элементов, если N даже.
Давайте рассмотрим различные случаи, когда вы можете вставлять элементы:
Вставка когда N нечетно: если вставленный элемент меньше чем *mItСтарая медиана становится правой от двух новых медианных элементов, поэтому уменьшите итератор. Если оно больше (или равно, для multiset), все хорошо.
Вставка когда N четный: если вставленный элемент больше (или равен) чем *mIt, старая правая медиана становится медианной, поэтому увеличиваем итератор. Если он меньше, старая левая медиана становится медианной, и все хорошо.
template <class T>
class MedianHolder {
std::set<T> elements;
std::set<T>::const_iterator mIt;
public:
T const& getMedian() const { return *mIt; }
void insert(T const& t) {
if (elements.empty()) {
mIt = elements.insert(t).first;
return;
}
bool smaller = std::less<T>(t,getMedian());
bool odd = (elements.size() % 2) == 1;
if (!elements.insert(t).second)
return; //not inserted
if (odd && smaller) --mIt;
else if (!odd && !smaller) ++mIt;
}
};
Я оставлю стирание элементов в качестве упражнения для вас 😉
Другие решения
Вы можете разделить ваш массив на два куча деревья одинакового размера, I наименьшей части или массива, и S имеет большую часть, и их вершины содержат максимальный и минимальный элемент. Скажи массив 1, 2, 4, 4, 5, 5, 7, 8, 8, 8 организован так:
1 4
\ /
4 2
\ /
5 <--- I's top
5 <--- S's top
/ \
7 8
/ \
8 8
Обратите внимание, что если число элементов четное, то медиана = top (S) + top (I), а если нечетное, то одна из куч может быть на один элемент больше другого, а медиана — сверху большего.
Когда это будет сделано, обновление медианы будет простым, вы должны добавить свой элемент в одну из куч и поменять их вершины, если top (S) стал меньше top (I).