4

假设在某个时间点，您有一组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) 方法；我只是建议它作为一个起点。

4

2 回答 2

7

您可以将数组拆分为两个大小相等的堆树，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)，则交换它们的顶部。

于 2013-06-13T11:53:16.230 回答
6

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

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

于 2013-06-13T13:02:44.907 回答