Rolling median algorithm in C

by

I have looked at R’s src/library/stats/src/Trunmed.c a few times as I wanted something similar too in a standalone C++ class / C subroutine. Note that this are actually two implementations in one, see src/library/stats/man/runmed.Rd (the source of the help file) which says

\details{
  Apart from the end values, the result \code{y = runmed(x, k)} simply has
  \code{y[j] = median(x[(j-k2):(j+k2)])} (k = 2*k2+1), computed very
  efficiently.

  The two algorithms are internally entirely different:
  \describe{
    \item{"Turlach"}{is the Härdle-Steiger
      algorithm (see Ref.) as implemented by Berwin Turlach.
      A tree algorithm is used, ensuring performance \eqn{O(n \log
        k)}{O(n * log(k))} where \code{n <- length(x)} which is
      asymptotically optimal.}
    \item{"Stuetzle"}{is the (older) Stuetzle-Friedman implementation
      which makes use of median \emph{updating} when one observation
      enters and one leaves the smoothing window.  While this performs as
      \eqn{O(n \times k)}{O(n * k)} which is slower asymptotically, it is
      considerably faster for small \eqn{k} or \eqn{n}.}
  }
}

It would be nice to see this re-used in a more standalone fashion. Are you volunteering? I can help with some of the R bits.

Edit 1: Besides the link to the older version of Trunmed.c above, here are current SVN copies of

Edit 2: Ryan Tibshirani has some C and Fortran code on fast median binning which may be a suitable starting point for a windowed approach.

More Related Contents:

  1. Generating a uniform distribution of INTEGERS in C
  2. Algorithm to find the smallest number in an array in C [closed]
  3. Recursive C function
  4. Finding target sum of two numbers in array
  5. How to remove blank spaces from buffer [closed]
  6. What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?
  7. hash function for string
  8. Algorithm: efficient way to remove duplicate integers from an array
  9. What is the fastest substring search algorithm?
  10. how to rasterize rotated rectangle (in 2d by setpixel)
  11. Point in Polygon Algorithm
  12. What common algorithms are used for C’s rand()?
  13. Matrix multiplication: Small difference in matrix size, large difference in timings
  14. Enumerate factors of a number directly in ascending order without sorting?
  15. Project Euler Question 14 (Collatz Problem)
  16. “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
  17. How do you print the EXACT value of a floating point number?
  18. Time complexity of a recursive algorithm
  19. How to find largest triangle in convex hull aside from brute force search
  20. Print all the permutations of a string in C
  21. Why prefer start + (end – start) / 2 over (start + end) / 2 when calculating the middle of an array?
  22. Given an audio stream, find when a door slams (sound pressure level calculation?)
  23. find if 4 points on a plane form a rectangle?
  24. Linked list recursive reverse
  25. Reductions in parallel in logarithmic time
  26. Finding out the duplicate element in an array
  27. Does C have any tools for doing string addition?
  28. A possible algorithm for determining whether two strings are anagrams of one another? [closed]
  29. QuickSort and Hoare Partition
  30. Calculate mean and standard deviation from a vector of samples in C++ using Boost

Leave a Comment