Роллинг-медиана в реализации C-Turlach

Ответ 1

Я внедрил скользящий средний калькулятор в C здесь (Gist ). Он использует структуру кучи max-median-min: медиана находится в куче [0] (которая находится в центре массива K-элементов). В куче [1] есть minheap и maxheap (с отрицательной индексацией) в куче [-1].
Это не то же самое, что реализация Turlach из источника R: эта поддерживает значения, которые вставляются "на лету", в то время как действует R-версия на весь буфер сразу. Но я считаю, что временная сложность такая же. И его можно было бы легко использовать для реализации всей версии буфера (возможно, с добавлением некоторого кода для обработки R "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); }
   }
}

Ответ 2

OpenCV имеет функцию medianBlur, которая, кажется, делает то, что вы хотите. Я знаю, что это скользящая медиана. Я не могу сказать, действительно ли это "Turlach roll median". Это довольно быстро, хотя и поддерживает многопоточность, когда доступно.

Ответ 3

Вы можете посмотреть исходный код на std:: nth_element в С++ и переписать его как C. nth_element может найти медианный (или любой другой отдельный элемент отсортированного массива) в O (N) времени в среднем.

float values[N];
...
std::nth_element( values, values+N/2, values+N );
return values[N/2];