从整数流中查找运行中位数

Question

可能重复:
C中的滚动中值算法

鉴于从数据流中读取整数.到目前为止,以有效的方式查找元素的中位数.

解决方案我已经读过:我们可以使用左侧的最大堆来表示小于有效中位数的元素,在右侧使用最小堆来表示大于有效中位数的元素.

在处理传入元素之后,堆中元素的数量最多相差1个元素.当两个堆包含相同数量的元素时,我们发现堆的根数据的平均值为有效中值.当堆不平衡时,我们从包含更多元素的堆的根中选择有效中值.

但是我们如何构建最大堆和最小堆,即我们如何知道这里的有效中位数呢？我认为我们会在max-heap中插入1个元素,然后在min-heap中插入下一个元素,依此类推所有元素.纠正我如果我错在这里.

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

计算流量百分位数的最有效方法是P²算法:Raj Jain,Imrich Chlamtac:用于动态计算量化和直方图的P²算法,无需存储观测值.COMMUN.ACM 28(10):1076-1085(1985)

该算法很容易实现并且工作得非常好.然而,这是一个估计,所以请记住这一点.从摘要:

提出了一种启发式算法,用于中值和其他分位数的动态计算.估计是在生成观测值时动态生成的.没有存储观察结果; 因此,无论观测数量多少,该算法都具有非常小且固定的存储要求.这使其成为可用于工业控制器和记录器的分位数芯片的理想选择.该算法进一步扩展到直方图绘图.分析了算法的准确性.

Answer 5

这个问题有一个确切的解决方案,只需要将最近看到的n个元素保存在内存中.速度快,尺度好.

的可转位skiplist支持O(LN n)的插入,删除,和索引的搜索任意的元件,同时保持排序的顺序.当与跟踪第n个最旧条目的FIFO队列结合使用时,解决方案很简单:

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 6

一个直观的思考方法是,如果你有一个完全平衡的二元搜索树,那么根就是中间元素,因为那里会有相同数量的更小和更大的元素.现在,如果树没有满,那么情况就不是这样了,因为最后一级会缺少元素.

所以我们可以做的是使用中位数和两个平衡二叉树,一个用于小于中位数的元素,一个用于大于中位数的元素.这两棵树必须保持相同的大小.

当我们从数据流中获得一个新的整数时,我们将它与中位数进行比较.如果它大于中位数,我们将它添加到正确的树中.如果两个树的大小差异大于1,我们删除右树的min元素,使其成为新的中位数,并将旧的中位数放在左侧树中.同样适合较小的.

Answer 7

效率是一个取决于背景的词.此问题的解决方案取决于相对于插入量执行的查询量.假设您在中位数感兴趣的末尾插入N个数字和K次.基于堆的算法的复杂度将是O(N log N + K).

考虑以下替代方案.将数字插入数组中,对于每个查询,运行线性选择算法(比如使用快速排序轴).现在你有一个运行时间为O(KN)的算法.

现在,如果K足够小(不常见的查询),后一种算法实际上更有效,反之亦然.