从整数流[复制]查找运行中位数从整数流[复制]查找运行中位数(Find running median

可能重复：
滚动使用C的中值算法

鉴于整数从数据流中读取。 找到有效的方式至今读元素的中位数。

解决方案我已阅读：我们可以使用左侧的最大堆来表示小于有效位数的元素，并在右侧最小堆来表示比有效位数更大的元素。

处理传入元件后，在堆元件的数目由1个元件至多不同。 当两个堆包含相同数量的元素，我们发现堆的根数据的平均有效位数。 当堆不均衡，我们选择从含有多种元素堆的根的有效位数。

但是，我们怎么构建最大堆和最小堆也就是说，我们怎么会知道这里的有效位数？ 我认为我们会插入最大堆1元，然后在最小堆接下来的1元，等所有的元素。 纠正我，如果我错了这里。

Answer 1:

有寻找从流式数据流动中位数，我将简要地谈谈他们在回答的最后一个号码不同的解决方案。

该问题是关于一个特定的溶液（最大堆/分钟堆溶液）的细节，并且基于如何堆溶液的工作原理是说明如下：

对于前两个元素加在右边较小的maxHeap左边，和一个更大的minHeap。 然后由一个进程流数据中的一个，

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

然后，在任何给定的时间就可以计算出中位数是这样的：

   If the heaps contain equal amount of elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

现在，我将谈论一般问题，在回答的开头承诺。 从数据流中找到运行中位数是一个棘手的问题，并寻找具有内存限制一个确切的解决方案可有效恐怕是不可能对于一般情况。 在另一方面，如果数据有一定的特点，我们可以利用，我们可以开发高效的专业化解决方案。 举例来说，如果我们知道数据是整型，那么我们可以使用计数排序 ，它可以给你一个固定存储器常数时间算法。 基于堆的解决方案是一种更通用的解决方案，因为它可以用于其它类型的数据（重复）为好。 最后，如果不需要准确的中位数和近似是不够的，你可以尝试估计的概率密度函数使用的数据和估计值。

Answer 2:

如果你不能在内存中保存所有项目一次，这个问题变得更加困难。 堆解决方案要求您同时保留在内存中的所有元素。 这是不可能在大多数现实世界中这一问题的应用程序。

相反，正如你看到的数字，追踪你看到每个整数次数的计数 。 假设4个字节的整数，这是2 ^ 32桶，或至多2 ^ 33的整数（键和计数每个INT），它是2 ^ 35字节或32GB。 它可能会比这少得多，因为你不需要存储密钥或计数那些0（即像Python中的defaultdict）项。 这需要一定的时间来将每个新的整数。

然后，在任何时候，要找到中间，只需使用数来确定哪些整数中间元素。 这需要一定的时间（尽管是大稳定，但仍然不变）。

Answer 3:

如果输入的方差统计分布（例如正常的，对数正态...等），然后贮存采样是从数字的任意长的流估计百分/中位数的一种合理的方式。

int n = 0;  // Running count of elements observed so far  
#define SIZE 10000
int reservoir[SIZE];  

while(streamHasData())
{
  int x = readNumberFromStream();

  if (n < SIZE)
  {
       reservoir[n++] = x;
  }         
  else 
  {
      int p = random(++n); // Choose a random number 0 >= p < n
      if (p < SIZE)
      {
           reservoir[p] = x;
      }
  }
}

“蓄水池”然后执行中，均匀的（中等），所有输入的样本 - 无论大小。 寻找中位数（或任何百分位），然后是整理水库和查询有趣点的直线前进的问题。

由于贮存器是固定的大小，排序可以被认为有效地是O（1） - 这方法与两个恒定的时间和内存消耗运行。

Answer 4:

这个问题有一个只需要n个最近看到的元素被保存在内存中一个确切的解决方案。 它是快速和很好地扩展。

的可转位skiplist支持O（LN n）的插入，删除，和索引的搜索任意的元件，同时保持排序的顺序。 当与连接的FIFO队列跟踪第n最旧的条目，解决方案是简单的：

class RunningMedian:
    'Fast running median with O(lg n) updates where n is the window size'

    def __init__(self, n, iterable):
        self.it = iter(iterable)
        self.queue = deque(islice(self.it, n))
        self.skiplist = IndexableSkiplist(n)
        for elem in self.queue:
            self.skiplist.insert(elem)

    def __iter__(self):
        queue = self.queue
        skiplist = self.skiplist
        midpoint = len(queue) // 2
        yield skiplist[midpoint]
        for newelem in self.it:
            oldelem = queue.popleft()
            skiplist.remove(oldelem)
            queue.append(newelem)
            skiplist.insert(newelem)
            yield skiplist[midpoint]

通过以下链接来完成工作的代码（易于理解的类版本，并与可转位skiplist代码内联优化的发电机版）：

• http://code.activestate.com/recipes/576930-efficient-running-median-using-an-indexable-skipli/

• http://code.activestate.com/recipes/577073 。

Answer 5:

来计算，我发现了一个流的百分位的最有效的方法是P 2算法： 拉吉耆那教，里奇·克兰塔克：在P 2算法不存储观测Quantiiles和直方图的动态计算。 COMMUN。 ACM 28（10）：1076年至1085年（1985）

该算法实现直线前进和运作非常良好。 这是一个估计值，然而，记住这一点。 从抽象：

启发式算法动态计算QF中位数和其他位数。 估计值是动态产生的观察结果生成的。 这些意见不存储; 因此，该算法不考虑观测值的数量的具有非常小的和固定的存储要求。 这使得它非常适合在可在工业控制器和记录器中使用的分位数芯片实现。 该算法进一步扩展到直方图绘制。 该算法的精度进行了分析。

Answer 6:

想想这一个直观的方法是，如果你有一个完整的平衡的二叉搜索树，那么根将是中间元素，因为将有相同数量的小和更大的元素。 现在，如果树不充分，这将不会那么以后还会有从最后一级元素缺失的情况。

所以，我们能做些什么，而不是为有位，以及两个平衡二叉树，一个不到位数的元素，以及一个用于元素比中值大。 两棵树必须保持在相同的尺寸。

当我们从数据流中一个新的整数，我们把它比作位数。 如果它比中位数大，我们把它添加到右侧树。 如果这两个树的大小相差超过1，我们拆下右树的分元素，使之成为新的中位数，并把旧的中位数在左边的树形。 同样，对于小。

Answer 7:

有效的是依赖于上下文的字。 这个问题的解决方案取决于相对于插入物的量来进行的查询的数量。 假设你向你有兴趣的中位数到底插入N个数和K倍。 堆基于算法的复杂度是O（N日志N + K）。

考虑以下方案。 普拉克数字在阵列，并且对于每个查询，运行线性选择算法（使用快速排序枢轴，说）。 现在你有一个运行时间为O（KN）的算法。

现在，如果K为足够小（不频繁的查询），后者实际上算法更高效的，并且反之亦然是。

Answer 8:

你不能只用一个堆做到这一点？ 更新：无。 见注释。

不变：读取后2*n输入，最小堆保持n最大他们。

循环：阅读2个输入。 他们都添加到堆，并删除堆的分钟。 这重新建立不变。

所以，当2n输入被读取，堆的min是第n个最大的。 有需要一点额外的复杂性，以平均约中间位置的两个元素和奇数号码的输入后处理查询。

文章来源: Find running median from a stream of integers [duplicate]