Rolling medyan C algoritması

SORU

20 AĞUSTOS 2009, PERŞEMBE

Rolling medyan C algoritması

Ben şu anda çalışan bir algoritma uygulamak için bir yuvarlanma medyan filtre (benzer bir rolling yani filtre) C. benim arama edebiyata, orada görünmesi için iki oldukça etkili yöntemler. İlk başlangıç değerleri penceresi sıralamak, eklemek için bir ikili arama yeni değeri gerçekleştirmek ve çıkarken kaldırmak her yineleme bir.

İkinci (Hardle ve Steiger, 1995, JRSS-C, Algoritma 296) oluşturur bir çift uçlu öbek yapısı ile bir maxheap bir ucunda bir minheap diğer, ortanca ortada. Bu lineer zamanı algoritması yerine O tek bir(n günlük n) verir.

Burada benim sorunum: eski yapılabilir, ama zaman serileri, verimlilik konularda milyonlarca bu çalıştırmak için ihtiyacım var çok. uygulama İkincisi uygulamak çok zor olduğunu gösteriyor. Bu Trunmed kod buldum.c R istatistik paketi için kod dosyası, ama oldukça anlaşılmaz.

Herkes iyi yazılmış C uygulama doğrusal bir ortalama algoritması rolling biliyor mu?

Edit: Trunmed Link.c kodu 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

CEVAP

21 AĞUSTOS 2009, Cuma

R baktım birkaç kez bir şeyler de bağımsız sınıf C / C yordam benzer istediğim gibi src/library/stats/src/Trunmed.c. Bu aslında bir iki uygulamaları, diyor ** 2 (yardım kaynak dosyası) olduğunu unutmayın

\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}.}
  }
}