Algorytm P2 to miłe znalezisko. Działa poprzez dokonanie kilku oszacowań kwantyla, okresową aktualizację i zastosowanie interpolacji kwadratowej (nieliniowej, nie sześciennej) do oszacowania kwantyla. Autorzy twierdzą, że interpolacja kwadratowa działa lepiej na ogonach niż interpolacja liniowa, a sześcienny stałby się zbyt wybredny i trudny.
Nie podajesz dokładnie, w jaki sposób to podejście zawodzi w przypadku twoich „grubościennych” danych, ale łatwo zgadnąć: szacunki ekstremalnych kwantyli dla gruboziarnistych dystrybucji będą niestabilne, dopóki nie zgromadzi się dużej ilości danych. Ale będzie to stanowić problem (w mniejszym stopniu), nawet jeśli miałbyś przechowywać wszystkie dane, więc nie oczekuj cudów!
W każdym razie, dlaczego nie ustawić pomocniczych znaczników - nazwijmy je i x 6 - w przypadku których masz pewność, że kwantyl będzie leżał, i zapisz wszystkie dane, które leżą między x 0 a x 6 ? Gdy bufor się zapełni, będziesz musiał zaktualizować te znaczniki, zawsze zachowując x 0 ≤ x 6 . Prosty algorytm do tego celu można opracować na podstawie kombinacji (a) aktualnego oszacowania P2 kwantyla i (b) przechowywanych zliczeń liczby danych mniejszej niż x 0 i liczby danych większej niż x 6x0x6x0x6x0≤x6x0x6. W ten sposób możesz z dużą pewnością oszacować kwantyl tak samo dobrze, jak gdyby cały zestaw danych był zawsze dostępny, ale potrzebujesz tylko stosunkowo małego bufora.
W szczególności proponuję strukturę danych celu utrzymania częściowej informacji o sekwencji n wartości danych x 1 , x 2 , … , x n . Tutaj y jest połączoną listą(k,y,n)nx1,x2,…,xny
y=(x(n)[k+1]≤x(n)[k+2]≤⋯≤x(n)[k+m]).
W tej notacji oznacza i- tą najmniejszą z dotychczas odczytanych wartości n x . m jest stałą wielkością bufora y .x(n)[i]ithn xmy
Algorytm zaczyna się od wypełnienia napotkanymi pierwszymi m wartościami danych i umieszczenia ich w posortowanej kolejności, od najmniejszej do największej. Niech q będzie kwantylem do oszacowania; np. q = 0,99. Po odczytaniu x n + 1 możliwe są trzy działania:ymqqxn+1
Jeżeli , przyrost k .xn+1<x(n)[k+1]k
Jeśli , nic nie rób.xn+1>x(n)[k+m]
W przeciwnym razie wstaw do y .xn+1y
W każdym razie przyrost .n
Procedura wstawiania umieszcza w y w posortowanej kolejności, a następnie eliminuje jedną z ekstremalnych wartości w y :xn+1yy
Jeśli , a następnie usunąć x ( n ) [ k + 1 ] z y a przyrost K ;k+m/2<nqx(n)[k+1]yk
W przeciwnym razie usuń z y .x(n)[k+m]y
Pod warunkiem, że jest wystarczająco duży, procedura ta będzie zawierała prawdziwe kwantyle rozkładu z dużym prawdopodobieństwem. Na dowolnym etapie n można to oszacować w zwykły sposób w kategoriach x ( n ) [ ⌊ q n ⌋ ] i x ( n ) [ ⌈ q n ⌉ ] , które prawdopodobnie będą znajdować się w y . (Uważam, że m musi być skalowane tylko jako pierwiastek kwadratowy maksymalnej ilości danych ( Nmnx(n)[⌊qn⌋]x(n)[⌈qn⌉]ymN), ale nie przeprowadziłem rygorystycznej analizy, aby to udowodnić.) W każdym razie algorytm wykryje, czy się udało (porównując i ( k + m ) / n do q ).k/n(k+m)/nq
Testowanie do 100 000 wartości przy użyciu iq=.5(najtrudniejszy przypadek) wskazuje, że ten algorytm ma 99,5% skuteczności w uzyskaniu prawidłowej wartości x ( n ) [ ⌊ q n ⌋ ] . Dla strumieniaN=10 12 wartości wymagałoby to bufora tylko dwóch milionów (ale trzy lub cztery miliony byłoby lepszym wyborem). Użycie posortowanej podwójnie połączonej listy dla bufora wymagaO(log( √m=2N−−√q=.5x(n)[⌊qn⌋]N=1012=wysiłekO(log(N))podczas identyfikowania i usuwania maks. Lub min tooperacjeO(1). Stosunkowo drogie wstawienie zwykle wymaga wykonania tylkoO( √O(log(N−−√))O(log(N))O(1)razy. Zatem koszty obliczeniowe tego algorytmu wynosząO(N+ √O(N−−√)w czasie iO( √O(N+N−−√log(N))=O(N)w magazynie.O(N−−√)