Скользящий медианный алгоритм в C

Question

В настоящее время я работаю над алгоритмом реализации скользящего медианного фильтра (аналога скользящего среднего фильтра) в C. Из моего поиска литературы, похоже, есть два достаточно эффективных способа сделать это. Первый - отсортировать начальное окно значений, затем выполнить двоичный поиск, чтобы вставить новое значение и удалить существующее на каждой итерации.

Второй (от Hardle and Steiger, 1995, JRSS-C, Algorithm 296) строит структуру кучи с двумя концами, с maxheap на одном конце, minheap на другом и медианой в середине. Это дает алгоритм с линейным временем вместо алгоритма O (n log n).

Вот моя проблема: реализация первого выполнима, но мне нужно выполнить это на миллионах временных рядов, поэтому эффективность очень важна. Последнее оказывается очень сложным для реализации. Я нашел код в файле Trunmed.c кода для пакета статистики R, но он довольно не поддается расшифровке.

Кто-нибудь знает хорошо написанную реализацию C для алгоритма линейного скользящего медианного времени?

Редактировать: ссылка на код Trunmed.c http://google.com/codesearch/p?hl=en&sa=N&cd=1&ct=rc#mYw3h_Lb_e0/R-2.2.0/src/library/stats/src/Trunmed.c

Answer 1

Вот тот, который может использоваться, когда точный вывод не важен (для целей отображения и т. Д.) Вам нужен totalcount и lastmedian, а также новое значение.

{
totalcount++;
newmedian=lastmedian+(newvalue>lastmedian?1:-1)*(lastmedian==0?newvalue: lastmedian/totalcount*2);
}

Создает довольно точные результаты для таких вещей, как page_display_time.

Правила: входной поток должен быть сглаженным по порядку времени отображения страницы, большим числом (> 30 и т. Д.) И иметь ненулевое медиану.

Пример: время загрузки страницы, 800 элементов, 10 мс ... 3000 мс, среднее 90 мс, реальная медиана: 11 мс

После 30 входов средняя ошибка обычно составляет <= 20% (9 мс. 12 мс) и становится все меньше и меньше. После 800 входов ошибка составляет + -2%. </p>

Другой мыслитель с подобным решением находится здесь: Медианный фильтр Супер эффективная реализация

Answer 2

Если вам просто требуется сглаженное среднее, быстрый / простой способ - умножить последнее значение на x и среднее значение на (1-x), а затем добавить их. Это становится новым средним значением.

edit: Не то, о чем просил пользователь, и не настолько статистически достоверно, но достаточно хорошо для многих применений.
Я оставлю это здесь (несмотря на отрицательные голоса) для поиска!