快速中值更新算法

Question

假设在某个时间点,您有一组N数字并知道中间元素:M.现在,您将获得一个新值,X因此您可能需要更新M.(或者更确切地说,您需要,假设您正在处理的数字都是唯一的.此外,所有样本都是连续接收的,因此并发性没有问题.)

计算新均值很简单:采用旧均值,加X,乘N,除N + 1.(通过检查N元素的平均值是如何定义的,这一点很清楚.目前我并不太担心数字.)

我的问题是:任何人都可以提出更新中位数的创意/小说(或者可能是可证明最优的)方法吗？我将在下面提供一个示例(我自己设计的简单概念),并进行一些分析:

在这个例子中,我将使用a std::forward_list,因为C++ 11是我最近遇到过的.在不失一般性的情况下,我将假设你以正确的方式进行此操作:维护到目前为止遇到的元素(类型T)的有序列表,std::forward_list<T> sorted;当 T x;出现时,只需使用以下方法将其折叠到位:

sorted.merge(std::forward_list<T> {{ x }});

顺便说一句,我很好奇是否有人有更好的(更有效/更优雅)的方法.欢迎Gripes.

所以,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

您可以将数组拆分为两个堆大小,相同大小,I最少部分或数组,并且S最大部分,并且它们的顶部包含最大和最小元素.Say数组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),如果是奇数,则其中一个堆应该是比其他元素大的一个元素,并且中值在更大的元素之上.

完成此操作后,更新中位数很简单,如果top(S)小于top(I),则应将元素添加到其中一个堆中并交换顶部.

Answer 2

您可以使用a 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;
  }
};

我会把擦除元素作为练习留给你;-)