C 中的滚动中位数 - Turlach 实现 [英] Rolling median in C - Turlach implementation

问题描述

有谁知道 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，这是一个滚动顺序统计算法的c 实现.我相信算法比 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.

推荐答案

我在这里实现了一个 滚动中值计算器 (要点).它使用最大-中值-最小堆结构:中值位于 heap[0](位于 K 项数组的中心).在 heap[1] 处有一个 minheap，在 heap[-1] 处有一个 maxheap(使用负索引).
它与 Turlach 实现并不完全相同R 源:这个支持即时插入值，而 R 版本一次作用于整个缓冲区.但我相信时间复杂度是一样的.它可以很容易地用于实现整个缓冲区版本(可能添加一些代码来处理 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); }
   }
}

这篇关于C 中的滚动中位数 - Turlach 实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！