滚动平均用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
这是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语言这里 <一HREF =https://gist.github.com/ashelly/5665911>(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); }
}
}
这篇关于滚动平均用C - Turlach实施的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!