由网友(狼の嚣张)分享简介：有谁知道是否有一个干净的实施Turlach滚动中位数算法的C呢？我无法移植第r版到一个干净的C版本。请参见此处对算法的详细信息。Does anyone know if there is a clean implementation of the Turlach rolling median algorithm in...

有谁知道是否有一个干净的实施Turlach滚动中位数算法的C呢？我无法移植第r版到一个干净的C版本。请参见此处对算法的详细信息。

Does anyone know if there is a clean implementation of the Turlach rolling median algorithm in C? I'm having trouble porting the R version to a clean C version. See here for more details on the algorithm.

编辑： 正如darkcminor指出，MATLAB有一个函数 medfilt2 这就要求 ordf 这是AC实现滚动次序统计算法。我相信算法比为O（n ^ 2）速度更快，但它不是开源的，我不希望购买图像处理工具箱。

As darkcminor pointed out, matlab has a function medfilt2 which calls ordf which is a c implementation of a rolling order statistic algorithm. I believe the algorithm is faster than O(n^2), but it is not open source and I do not want to purchase the image processing toolbox.

推荐答案

我已经实现了一个滚动平均计算器C语言这里 （GIST）。它采用的是最大中值 - 最小堆结构：中值是在堆[0]（这是在一个K项阵列的中心）。有在堆一个minheap起始于堆[1]，和一个maxheap（使用负索引）[-1]。 这是不完全一样的 Turlach实现从R源：这一个支持插入上的即时值，而第r版本上的整个缓冲作用在一次。但我相信时间复杂度是一样的。它可以很容易地用来实现整个缓冲区版本的（可能与增加了一些code来处理R原则endrules）的。

I've implemented a rolling median calculator in C here (Gist). It uses a max-median-min heap structure: The median is at heap[0] (which is at the center of a K-item array). There is a minheap starting at heap[ 1], and a maxheap (using negative indexing) at heap[-1]. It's not exactly the same as the Turlach implementation from the R source: This one supports values being inserted on-the-fly, while the R version acts on a whole buffer at once. But I believe the time complexity is the same. And it could easily be used to implement a whole buffer version (possibly with with the addition of some code to handle R's "endrules").

接口：

//Customize for your data Item type
typedef int Item;
#define ItemLess(a,b)  ((a)<(b))
#define ItemMean(a,b)  (((a)+(b))/2)

typedef struct Mediator_t Mediator;

//creates new Mediator: to calculate `nItems` running median. 
//mallocs single block of memory, caller must free.
Mediator* MediatorNew(int nItems);

//returns median item (or average of 2 when item count is even)
Item MediatorMedian(Mediator* m);

//Inserts item, maintains median in O(lg nItems)
void MediatorInsert(Mediator* m, Item v)
{
   int isNew = (m->ct < m->N);
   int p = m->pos[m->idx];
   Item old = m->data[m->idx];
   m->data[m->idx] = v;
   m->idx = (m->idx+1) % m->N;
   m->ct += isNew;
   if (p > 0)         //new item is in minHeap
   {  if (!isNew && ItemLess(old, v)) { minSortDown(m, p*2);  }
      else if (minSortUp(m, p)) { maxSortDown(m,-1); }
   }
   else if (p < 0)   //new item is in maxheap
   {  if (!isNew && ItemLess(v, old)) { maxSortDown(m, p*2); }
      else if (maxSortUp(m, p)) { minSortDown(m, 1); }
   }
   else            //new item is at median
   {  if (maxCt(m)) { maxSortDown(m,-1); }
      if (minCt(m)) { minSortDown(m, 1); }
   }
}