StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I've implemented a <a href="http://ideone.com/8VVEa" rel="noreferrer">rolling median calculator in C here</a> <a href="https://gist.github.com/ashelly/5665911" rel="noreferrer">(Gist)</a>. 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].<br> It's not exactly the same as the <a href="http://svn.r-project.org/R/trunk/src/library/stats/src/Trunmed.c" rel="noreferrer">Turlach implementation from the R source</a>: 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 <em>(possibly with with the addition of some code to handle R's "endrules")</em>.</p> <p>Interface:</p> <pre><code>//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); } } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload