Алгоритм быстрого среднего обновления

Question

Предположим, что в определенный момент времени у вас есть коллекция номеров 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), если вы считаете, что это мусор/твой намного лучше; Я просто предлагаю это как отправную точку.

Answer 1

Вы можете использовать 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; 
    } 
}; 

Я оставлю стирание элементов в качестве упражнения вы ;-)

Answer 2

Вы можете разделить ваш массив Int два кучи деревьев, одинакового размера, 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 

Примечание, если число элементов четно, то медиана = верхняя (S) + верхняя (I), и если нечетно, то один из куч thould быть одним из элементов больше другое, а медиана - сверху более крупного.

Если это сделано, то обновление медианы прост, вы должны добавить свой элемент в одну из куч и обменивать свои вершины, если верхний (S) стал меньше верхнего (I).