C의 롤링 중위수 알고리즘
현재 C에서 롤링 중위 필터(롤링 평균 필터와 유사)를 구현하기 위한 알고리즘을 개발 중입니다.내가 문헌을 찾아본 결과, 그것을 할 수 있는 두 가지 상당히 효율적인 방법이 있는 것 같다.첫 번째 방법은 값의 초기 창을 정렬한 다음 이진 검색을 수행하여 새 값을 삽입하고 각 반복에서 기존 값을 제거하는 것입니다.
두 번째(Hardle and Steiger, 1995, JRSS-C, Algorithm 296)는 한쪽 끝에는 최대 히프가, 다른 한쪽 끝에는 최소 히프가, 중앙에는 중앙이 있는 이중 엔드 힙 구조를 구축합니다.그러면 O(n log n)가 아닌 선형 시간 알고리즘이 생성됩니다.
여기 문제가 있습니다.전자의 실장은 가능하지만, 수백만 번의 시계열로 실행할 필요가 있기 때문에 효율이 매우 중요합니다.후자는 실행하기가 매우 어렵다는 것이 증명되고 있다.R의 stats 패키지용 코드의 Trunmed.c 파일에서 코드를 찾았는데, 읽을 수 없습니다.
선형 시간 굴림 중앙 알고리즘에 대해 잘 작성된 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
순서 통계와 함께 c++ 데이터 구조의 현대적인 구현을 찾을 수 없었기 때문에 MAK가 제안하는 상위 코더스 링크(Match Editory: Scroll down to Floating Median)에서 두 가지 아이디어를 모두 구현하게 되었습니다.
멀티셋×2
첫 번째 아이디어는 데이터를 삽입/삭제당 O(ln N)가 있는 두 개의 데이터 구조(히프, 멀티셋 등)로 분할하는 것으로, 큰 비용 없이 분위수를 동적으로 변경할 수 없다.즉, 롤링 중위수 또는 롤링 75%를 가질 수 있지만 동시에 둘 다 가질 수는 없습니다.
세그먼트 트리
두 번째 아이디어는 삽입/삭제/쿼리에 O(ln N)인 세그먼트 트리를 사용합니다.가장 좋은 점은 데이터 범위의 크기입니다.따라서 롤링 중앙값의 창이 100만 개이지만 데이터가 1,65536개에서 다른 경우 롤링 창 100만 개 이동당 16개의 작업만 필요합니다.
c++ 코드는 위의 Denis가 게시한 것과 유사합니다(여기 정량화된 데이터에 대한 단순한 알고리즘이 있습니다).
GNU 주문 통계 트리
포기 직전에 stdlibc++에 주문 통계 트리가 포함되어 있는 것을 발견했습니다!!!
여기에는 다음 두 가지 중요한 작업이 있습니다.
iter = tree.find_by_order(value)
order = tree.order_of_key(value)
libstdc++ 수동 정책_based_data_structures_test("분할 및 가입")를 참조하십시오.
c++0x/c++11 스타일의 partial typedef를 지원하는 컴파일러의 편리한 헤더에 사용하기 위해 트리를 랩했습니다.
#if !defined(GNU_ORDER_STATISTIC_SET_H)
#define GNU_ORDER_STATISTIC_SET_H
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// A red-black tree table storing ints and their order
// statistics. Note that since the tree uses
// tree_order_statistics_node_update as its update policy, then it
// includes its methods by_order and order_of_key.
template <typename T>
using t_order_statistic_set = __gnu_pbds::tree<
T,
__gnu_pbds::null_type,
std::less<T>,
__gnu_pbds::rb_tree_tag,
// This policy updates nodes' metadata for order statistics.
__gnu_pbds::tree_order_statistics_node_update>;
#endif //GNU_ORDER_STATISTIC_SET_H
다음과 같은 증분 중위수 추정기를 사용합니다.
median += eta * sgn(sample - median)
이 값은 더 일반적인 평균 추정기와 동일한 형태를 가집니다.
mean += eta * (sample - mean)
여기 eta는 작은 학습 속도 파라미터입니다(예:0.001및 , 。sgn()다음 중 하나를 반환하는 시그넘 함수입니다.{-1, 0, 1} (합니다.)eta이고 시간에 그렇지 않은 경우 소스에 는 다음과 같은 을 사용합니다. 그렇지 않으면 고정 소스의 경우 다음과 같은 기능을 사용합니다.eta = 1 / nn의
또한, 저는 중위수 추정기를 수정하여 임의의 분위에 대해 작동하도록 했습니다.일반적으로, 분위수 함수는 데이터를 두 분수로 나누는 값을 알려줍니다.p ★★★★★★★★★★★★★★★★★」1 - p을 하다
quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)
값p에 있어야 [0, 1]에 의해, 으로는 「이행」이 sgn() 출력 「」{-1, 0, 1} 두 개의 빈)으로으로 기울입니다.p ★★★★★★★★★★★★★★★★★」1 - p데이터의 양이 분위수 추정치보다 적거나 적습니다.)「 」의 경우는, 을해 주세요.p = 0.5이 값은 중위수 추정치로 감소합니다.
R을 .src/library/stats/src/Trunmed.c스탠드아론 C++ 클래스 / C 서브루틴에서도 비슷한 것을 원했기 때문에 몇 번인가.입니다.「 2 」를 참조해 주세요.src/library/stats/man/runmed.Rd) 라고 있습니다.
\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}.}
}
}
이것을 좀 더 독립형으로 재사용하는 것을 보면 좋을 것 같아요.자원봉사를 하시는 건가요?R비트를 좀 도와줄 수 있어요.
편집 1: 위의 이전 버전의 Trunmed.c에 대한 링크 외에 현재 SVN 복사본은 다음과 같습니다.
편집 2: Ryan Tibshirani는 빠른 중앙값 비닝에 몇 가지 C 및 Fortran 코드를 가지고 있으며, 이는 윈도우 접근에 적합한 시작점일 수 있습니다.
여기서 C를 구현했습니다.C - Turlach 구현에서의 롤링 중위수 몇 가지 세부 사항은 이 질문에 있습니다.
사용 예:
int main(int argc, char* argv[])
{
int i, v;
Mediator* m = MediatorNew(15);
for (i=0; i<30; i++) {
v = rand() & 127;
printf("Inserting %3d \n", v);
MediatorInsert(m, v);
v = MediatorMedian(m);
printf("Median = %3d.\n\n", v);
ShowTree(m);
}
}
다음은 정량화된 데이터에 대한 간단한 알고리즘입니다(수개월 후).
""" median1.py: moving median 1d for quantized, e.g. 8-bit data
Method: cache the median, so that wider windows are faster.
The code is simple -- no heaps, no trees.
Keywords: median filter, moving median, running median, numpy, scipy
See Perreault + Hebert, Median Filtering in Constant Time, 2007,
http://nomis80.org/ctmf.html: nice 6-page paper and C code,
mainly for 2d images
Example:
y = medians( x, window=window, nlevel=nlevel )
uses:
med = Median1( nlevel, window, counts=np.bincount( x[0:window] ))
med.addsub( +, - ) -- see the picture in Perreault
m = med.median() -- using cached m, summ
How it works:
picture nlevel=8, window=3 -- 3 1s in an array of 8 counters:
counts: . 1 . . 1 . 1 .
sums: 0 1 1 1 2 2 3 3
^ sums[3] < 2 <= sums[4] <=> median 4
addsub( 0, 1 ) m, summ stay the same
addsub( 5, 1 ) slide right
addsub( 5, 6 ) slide left
Updating `counts` in an `addsub` is trivial, updating `sums` is not.
But we can cache the previous median `m` and the sum to m `summ`.
The less often the median changes, the faster;
so fewer levels or *wider* windows are faster.
(Like any cache, run time varies a lot, depending on the input.)
See also:
scipy.signal.medfilt -- runtime roughly ~ window size
http://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c
"""
from __future__ import division
import numpy as np # bincount, pad0
__date__ = "2009-10-27 oct"
__author_email__ = "denis-bz-py at t-online dot de"
#...............................................................................
class Median1:
""" moving median 1d for quantized, e.g. 8-bit data """
def __init__( s, nlevel, window, counts ):
s.nlevel = nlevel # >= len(counts)
s.window = window # == sum(counts)
s.half = (window // 2) + 1 # odd or even
s.setcounts( counts )
def median( s ):
""" step up or down until sum cnt to m-1 < half <= sum to m """
if s.summ - s.cnt[s.m] < s.half <= s.summ:
return s.m
j, sumj = s.m, s.summ
if sumj <= s.half:
while j < s.nlevel - 1:
j += 1
sumj += s.cnt[j]
# print "j sumj:", j, sumj
if sumj - s.cnt[j] < s.half <= sumj: break
else:
while j > 0:
sumj -= s.cnt[j]
j -= 1
# print "j sumj:", j, sumj
if sumj - s.cnt[j] < s.half <= sumj: break
s.m, s.summ = j, sumj
return s.m
def addsub( s, add, sub ):
s.cnt[add] += 1
s.cnt[sub] -= 1
assert s.cnt[sub] >= 0, (add, sub)
if add <= s.m:
s.summ += 1
if sub <= s.m:
s.summ -= 1
def setcounts( s, counts ):
assert len(counts) <= s.nlevel, (len(counts), s.nlevel)
if len(counts) < s.nlevel:
counts = pad0__( counts, s.nlevel ) # numpy array / list
sumcounts = sum(counts)
assert sumcounts == s.window, (sumcounts, s.window)
s.cnt = counts
s.slowmedian()
def slowmedian( s ):
j, sumj = -1, 0
while sumj < s.half:
j += 1
sumj += s.cnt[j]
s.m, s.summ = j, sumj
def __str__( s ):
return ("median %d: " % s.m) + \
"".join([ (" ." if c == 0 else "%2d" % c) for c in s.cnt ])
#...............................................................................
def medianfilter( x, window, nlevel=256 ):
""" moving medians, y[j] = median( x[j:j+window] )
-> a shorter list, len(y) = len(x) - window + 1
"""
assert len(x) >= window, (len(x), window)
# np.clip( x, 0, nlevel-1, out=x )
# cf http://scipy.org/Cookbook/Rebinning
cnt = np.bincount( x[0:window] )
med = Median1( nlevel=nlevel, window=window, counts=cnt )
y = (len(x) - window + 1) * [0]
y[0] = med.median()
for j in xrange( len(x) - window ):
med.addsub( x[j+window], x[j] )
y[j+1] = med.median()
return y # list
# return np.array( y )
def pad0__( x, tolen ):
""" pad x with 0 s, numpy array or list """
n = tolen - len(x)
if n > 0:
try:
x = np.r_[ x, np.zeros( n, dtype=x[0].dtype )]
except NameError:
x += n * [0]
return x
#...............................................................................
if __name__ == "__main__":
Len = 10000
window = 3
nlevel = 256
period = 100
np.set_printoptions( 2, threshold=100, edgeitems=10 )
# print medians( np.arange(3), 3 )
sinwave = (np.sin( 2 * np.pi * np.arange(Len) / period )
+ 1) * (nlevel-1) / 2
x = np.asarray( sinwave, int )
print "x:", x
for window in ( 3, 31, 63, 127, 255 ):
if window > Len: continue
print "medianfilter: Len=%d window=%d nlevel=%d:" % (Len, window, nlevel)
y = medianfilter( x, window=window, nlevel=nlevel )
print np.array( y )
# end median1.py
롤링 중위수는 두 개의 숫자 파티션을 유지하여 찾을 수 있습니다.
파티션을 유지 보수하려면 최소 힙 및 최대 힙을 사용합니다.
최대 힙에는 중위수보다 작은 숫자가 포함됩니다.
최소 힙에는 중위수보다 큰 숫자가 포함됩니다.
Balancing Constraint: 요소의 총 수가 짝수인 경우 두 힙 모두 동일한 요소를 가져야 합니다.
요소의 총 수가 홀수인 경우 Max Heap에는 최소 Heap보다 요소가 하나 더 있습니다.
중위수 요소: 두 파티션의 요소 수가 같을 경우 중위수는 첫 번째 파티션의 최대 요소와 두 번째 파티션의 최소 요소의 합계의 절반이 됩니다.
그렇지 않으면 중위수가 첫 번째 파티션의 최대 요소가 됩니다.
알고리즘-1 - 2개의 히프 (1개의 최소 힙과 1개의 최대 힙)를 취득합니다.최대 힙에는 전반 절반의 요소가 포함됩니다.최소 힙에는 후반의 요소 수가 포함됩니다. 2- 스트림의 새 숫자를 최대 힙의 상단과 비교합니다.이 값이 작거나 같으면 최대 힙에 이 숫자를 추가합니다. 그렇지 않으면 최소 힙에 번호를 추가합니다. 3- 최소 힙에 최대 힙보다 많은 요소가 있는 경우그런 다음 최소 힙의 상위 요소를 제거하고 최대 힙을 추가합니다. max 힙에 최소 힙보다 여러 요소가 있는 경우그런 다음 Max Hipp의 상위 요소를 제거하고 최소 힙을 추가합니다. 4- 두 힙의 요소 수가 같을 경우median은 Max Heap의 max 요소와 Min Heap의 min 요소의 합계의 절반이 됩니다. 그렇지 않으면 중위수가 첫 번째 파티션의 최대 요소가 됩니다.
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
RunningMedianHeaps s = new RunningMedianHeaps();
int n = in.nextInt();
for(int a_i=0; a_i < n; a_i++){
printMedian(s,in.nextInt());
}
in.close();
}
public static void printMedian(RunningMedianHeaps s, int nextNum){
s.addNumberInHeap(nextNum);
System.out.printf("%.1f\n",s.getMedian());
}
}
class RunningMedianHeaps{
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Comparator.reverseOrder());
public double getMedian() {
int size = minHeap.size() + maxHeap.size();
if(size % 2 == 0)
return (maxHeap.peek()+minHeap.peek())/2.0;
return maxHeap.peek()*1.0;
}
private void balanceHeaps() {
if(maxHeap.size() < minHeap.size())
{
maxHeap.add(minHeap.poll());
}
else if(maxHeap.size() > 1+minHeap.size())
{
minHeap.add(maxHeap.poll());
}
}
public void addNumberInHeap(int num) {
if(maxHeap.size()==0 || num <= maxHeap.peek())
{
maxHeap.add(num);
}
else
{
minHeap.add(num);
}
balanceHeaps();
}
}
스트림 내의 모든 값이 (상대적으로) 작은 정의 범위 내의 정수인 경우라는 단순한 정확한 해결책이 있는 특별한 경우가 있다는 점을 지적할 필요가 있습니다.예를 들어, 모두 0과 1023 사이에 있어야 한다고 가정합니다.이 경우 1024개의 요소와 카운트의 배열을 정의하고 이들 값을 모두 클리어합니다.스트림의 각 값에 대해 해당 빈과 카운트가 증가합니다.스트림 종료 후 카운트/2의 가장 높은 값을 포함하는 빈을 찾습니다. 0부터 시작하여 연속 빈을 추가하면 쉽게 얻을 수 있습니다.동일한 방법을 사용하여 임의 순위 값을 찾을 수 있습니다.(실행 중에 빈 포화를 감지하고 저장 빈의 크기를 더 큰 유형으로 "업그레이드"해야 하는 경우 약간의 문제가 있습니다.)
이 특별한 경우는 인위적으로 보일 수 있지만 실제로는 매우 흔하다.또한 실수가 범위 내에 있고 "충분한" 정밀도가 알려진 경우 실수의 근사치로 적용할 수 있습니다.이것은 "실제 세계" 물체의 그룹에 대한 거의 모든 일련의 측정을 유지할 수 있습니다.예를 들어, 한 무리의 키나 몸무게.충분히 크지 않은가?누군가가 데이터를 제공할 수 있다면 지구상의 모든 박테리아(개별)의 길이나 무게에 대해서도 효과가 있을 것이다!
원문을 잘못 읽은 것 같습니다.원문은 매우 긴 스트림의 중앙값 대신 슬라이딩 윈도우 중앙값을 원하는 것 같습니다.이 접근방식은 아직 유효합니다.초기 창에 대해 첫 번째 N개의 스트림 값을 로드한 다음 N+1번째 스트림 값의 경우 해당 빈을 증가시키고 0번째 스트림 값에 해당하는 빈을 감소시킵니다.이 경우 크기 N의 배열을 주기적으로 처리함으로써 효율적으로 수행될 수 있는 마지막 N 값을 유지할 필요가 있다. 중앙값의 위치는 슬라이딩 윈도우의 각 단계에서 -2,-1,0,1,2만큼만 변경될 수 있으므로, 각 단계에서 중앙값까지 모든 빈을 합할 필요는 없으며, "중간값"을 조정하기만 하면 된다.포인터"를 선택합니다.예를 들어, 새 값과 제거 중인 값이 모두 현재 중위수보다 낮으면 변경되지 않습니다(표준 = 0).N이 너무 커서 쉽게 메모리에 저장할 수 없게 되면 메서드가 고장납니다.
다음은 Java 구현입니다.
package MedianOfIntegerStream;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class MedianOfIntegerStream {
public Set<Integer> rightMinSet;
public Set<Integer> leftMaxSet;
public int numOfElements;
public MedianOfIntegerStream() {
rightMinSet = new TreeSet<Integer>();
leftMaxSet = new TreeSet<Integer>(new DescendingComparator());
numOfElements = 0;
}
public void addNumberToStream(Integer num) {
leftMaxSet.add(num);
Iterator<Integer> iterMax = leftMaxSet.iterator();
Iterator<Integer> iterMin = rightMinSet.iterator();
int maxEl = iterMax.next();
int minEl = 0;
if (iterMin.hasNext()) {
minEl = iterMin.next();
}
if (numOfElements % 2 == 0) {
if (numOfElements == 0) {
numOfElements++;
return;
} else if (maxEl > minEl) {
iterMax.remove();
if (minEl != 0) {
iterMin.remove();
}
leftMaxSet.add(minEl);
rightMinSet.add(maxEl);
}
} else {
if (maxEl != 0) {
iterMax.remove();
}
rightMinSet.add(maxEl);
}
numOfElements++;
}
public Double getMedian() {
if (numOfElements % 2 != 0)
return new Double(leftMaxSet.iterator().next());
else
return (leftMaxSet.iterator().next() + rightMinSet.iterator().next()) / 2.0;
}
private class DescendingComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
public static void main(String[] args) {
MedianOfIntegerStream streamMedian = new MedianOfIntegerStream();
streamMedian.addNumberToStream(1);
System.out.println(streamMedian.getMedian()); // should be 1
streamMedian.addNumberToStream(5);
streamMedian.addNumberToStream(10);
streamMedian.addNumberToStream(12);
streamMedian.addNumberToStream(2);
System.out.println(streamMedian.getMedian()); // should be 5
streamMedian.addNumberToStream(3);
streamMedian.addNumberToStream(8);
streamMedian.addNumberToStream(9);
System.out.println(streamMedian.getMedian()); // should be 6.5
}
}
Java에서 실행 중인 중앙값이 필요한 사용자를 위해...우선 순위.큐는 당신의 친구입니다.O(log N) 삽입, O(1) 전류 중앙값 및 O(N) 제거.데이터의 분포를 알면 이보다 훨씬 더 잘 할 수 있습니다.
public class RunningMedian {
// Two priority queues, one of reversed order.
PriorityQueue<Integer> lower = new PriorityQueue<Integer>(10,
new Comparator<Integer>() {
public int compare(Integer arg0, Integer arg1) {
return (arg0 < arg1) ? 1 : arg0 == arg1 ? 0 : -1;
}
}), higher = new PriorityQueue<Integer>();
public void insert(Integer n) {
if (lower.isEmpty() && higher.isEmpty())
lower.add(n);
else {
if (n <= lower.peek())
lower.add(n);
else
higher.add(n);
rebalance();
}
}
void rebalance() {
if (lower.size() < higher.size() - 1)
lower.add(higher.remove());
else if (higher.size() < lower.size() - 1)
higher.add(lower.remove());
}
public Integer getMedian() {
if (lower.isEmpty() && higher.isEmpty())
return null;
else if (lower.size() == higher.size())
return (lower.peek() + higher.peek()) / 2;
else
return (lower.size() < higher.size()) ? higher.peek() : lower
.peek();
}
public void remove(Integer n) {
if (lower.remove(n) || higher.remove(n))
rebalance();
}
}
@mathog 생각에 근거해, 이것은 기존의 값의 범위를 가지는 바이트 배열에 대해서 실행중의 중앙값의 C# 실장입니다.다른 정수 유형으로 확장할 수 있습니다.
/// <summary>
/// Median estimation by histogram, avoids multiple sorting operations for a running median
/// </summary>
public class MedianEstimator
{
private readonly int m_size2;
private readonly byte[] m_counts;
/// <summary>
/// Estimated median, available right after calling <see cref="Init"/> or <see cref="Update"/>.
/// </summary>
public byte Median { get; private set; }
/// <summary>
/// Ctor
/// </summary>
/// <param name="size">Median size in samples</param>
/// <param name="maxValue">Maximum expected value in input data</param>
public MedianEstimator(
int size,
byte maxValue)
{
m_size2 = size / 2;
m_counts = new byte[maxValue + 1];
}
/// <summary>
/// Initializes the internal histogram with the passed sample values
/// </summary>
/// <param name="values">Array of values, usually the start of the array for a running median</param>
public void Init(byte[] values)
{
for (var i = 0; i < values.Length; i++)
m_counts[values[i]]++;
UpdateMedian();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void UpdateMedian()
{
// The median is the first value up to which counts add to size / 2
var sum = 0;
Median = 0;
for (var i = 0; i < m_counts.Length; i++)
{
sum += m_counts[i];
Median = (byte) i;
if (sum > m_size2) break;
}
}
/// <summary>
/// Updates the median estimation by removing <paramref name="last"/> and adding <paramref name="next"/>. These
/// values must be updated as the running median is applied. If the median length is <i>N</i>, at the sample
/// <i>i</i>, <paramref name="last"/> is sample at index <i>i</i>-<i>N</i>/2 and <paramref name="next"/> is sample
/// at index <i>i</i>+<i>N</i>/2+1.
/// </summary>
/// <param name="last">Sample at the start of the moving window that is to be removed</param>
/// <param name="next">Sample at the end of the moving window + 1 that is to be added</param>
public void Update(byte last, byte next)
{
m_counts[last]--;
m_counts[next]++;
// The conditions below do not change median value so there is no need to update it
if (last == next ||
last < Median && next < Median || // both below median
last > Median && next > Median) // both above median
return;
UpdateMedian();
}
실행 중인 중앙값과 비교 테스트, 타이밍:
private void TestMedianEstimator()
{
var r = new Random();
const int SIZE = 15;
const byte MAX_VAL = 80;
var values = new byte[100000];
for (var i = 0; i < values.Length; i++)
values[i] = (byte) (MAX_VAL * r.NextDouble());
var timer = Stopwatch.StartNew();
// Running median
var window = new byte[2 * SIZE + 1];
var medians = new byte[values.Length];
for (var i = SIZE; i < values.Length - SIZE - 1; i++)
{
for (int j = i - SIZE, k = 0; j <= i + SIZE; j++, k++)
window[k] = values[j];
Array.Sort(window);
medians[i] = window[SIZE];
}
timer.Stop();
var elapsed1 = timer.Elapsed;
timer.Restart();
var me = new MedianEstimator(2 * SIZE + 1, MAX_VAL);
me.Init(values.Slice(0, 2 * SIZE + 1));
var meMedians = new byte[values.Length];
for (var i = SIZE; i < values.Length - SIZE - 1; i++)
{
meMedians[i] = me.Median;
me.Update(values[i - SIZE], values[i + SIZE + 1]);
}
timer.Stop();
var elapsed2 = timer.Elapsed;
WriteLineToLog($"{elapsed1.TotalMilliseconds / elapsed2.TotalMilliseconds:0.00}");
var diff = 0;
for (var i = 0; i < meMedians.Length; i++)
diff += Math.Abs(meMedians[i] - medians[i]);
WriteLineToLog($"Diff: {diff}");
}
평활 평균만 필요한 경우 최신 값에 x를 곱하고 평균 값에 (1-x)를 곱하는 것이 빠르고 쉬운 방법입니다.이것이 새로운 평균이 됩니다.
edit: 사용자가 요구하는 것은 아니며 통계적으로 유효하지는 않지만 많은 용도로 사용할 수 있습니다.
(다운투표에도 불구하고) 검색하기 위해 여기에 두겠습니다!
값을 지정 시점의 함수로 참조할 수 있는 경우 부트스트래핑을 적용하여 값을 치환하여 샘플링하여 신뢰 구간 내에서 부트스트래핑된 중위수 값을 생성할 수 있습니다.따라서 들어오는 값을 데이터 구조로 계속 정렬하는 것보다 더 효율적으로 근사 중위수를 계산할 수 있습니다.
정확한 출력이 중요하지 않을 때(표시 목적 등) 사용할 수 있는 것을 다음에 나타냅니다.토탈카운트와 라스트미디안, 그리고 새로운 값이 필요합니다.
{
totalcount++;
newmedian=lastmedian+(newvalue>lastmedian?1:-1)*(lastmedian==0?newvalue: lastmedian/totalcount*2);
}
page_display_time과 같은 매우 정확한 결과를 생성합니다.
규칙: 입력 스트림은 페이지 표시 시간 순서대로 매끄러워야 하며, 카운트가 크고(>30 등), 중앙값이 0이 아니어야 합니다.
예: 페이지 로드 시간, 800개 항목, 10ms...3000밀리초, 평균 90밀리초, 실제 중위수: 11밀리초
30회 입력 후 중간값 오차는 일반적으로 <=20%(9ms)입니다.12 ms)로, 점점 적어집니다.800 입력 후 오류는 +-2%가 됩니다.
유사한 솔루션을 사용하는 또 다른 사고방식은 다음과 같습니다.Median Filter Super Efficient 구현
언급URL : https://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c
'programing' 카테고리의 다른 글
| PHP의 join()과 같은 어레이의 Java 함수? (0) | 2022.08.25 |
|---|---|
| vue-tables-2의 데이터 새로고침(Vuex) (0) | 2022.08.25 |
| @vue/cli-plugin-unit-mocha, TypeScript 및 SFC를 사용한 VueJ 프로젝트의 NYC 커버리지 보고서 생성 (0) | 2022.08.25 |
| java.util을 피하는 방법동시 수정Array List에서 요소를 삭제하고 반복할 때의 예외 (0) | 2022.08.25 |
| vue.display 내의 foreach 루프에서 액세스 변수 (0) | 2022.08.25 |