Data Stream

Moving Median

这是和Moving Average一样的一个统计学常用的方法. 这个比那个average更(有用). 用一个最大堆和一个最小堆维护. 先往最小堆里放第一个元素, 然后其他元素就比一下, 如果比最小堆的顶元素小或者等于, 就放最小堆,不是就放最大堆. 然后还需要一个rebalance的方法, 如果其中一个堆比另一个堆多一个以上,就扔过去一个.

import java.util.Collections;
import java.util.PriorityQueue;

/**
 * Created by Chenguang He (readman@iastate.edu) on 10/5/15.
 */
public class MovingMedian {
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

    public void add(Integer i) {
        if (minHeap.isEmpty() && maxHeap.isEmpty())
            minHeap.add(i);
        else {
            if (i <= minHeap.peek())
                minHeap.add(i);
            else
                maxHeap.add(i);
            rebalance();
        }
    }

    private void rebalance(){
        if (minHeap.size() < maxHeap.size()-1) {
            minHeap.add(maxHeap.remove());
        }
        else if (minHeap.size() > maxHeap.size() +1){
            maxHeap.add(minHeap.remove());
        }
    }

    public float getMedian(){
        if (minHeap.size() == 0 && maxHeap.size() == 0)
            return -1;
        else if (minHeap.size() == maxHeap.size())
            return (float)(minHeap.peek()+maxHeap.peek())/(float)2;
        else
            return (minHeap.size() < maxHeap.size()) ? maxHeap.peek():minHeap.peek();
    }

    public static void main(String[] args) {
        int[] t = new int[]{4,-2,1,2,-3};
        MovingMedian m = new MovingMedian();
        for (int tt : t)
            m.add(tt);
        System.out.println(m.getMedian());
    }
}

import java.util.Collections;

import java.util.PriorityQueue;

/**

* Created by Chenguang He ([email protected]) on 10/5/15.

public class MovingMedian {

private PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

private PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

public void add(Integer i) {

if (minHeap.isEmpty() && maxHeap.isEmpty())

minHeap.add(i);

else {

if (i <= minHeap.peek())

minHeap.add(i);

else

maxHeap.add(i);

rebalance();

}

private void rebalance(){

if (minHeap.size() < maxHeap.size()-1) {

minHeap.add(maxHeap.remove());

}

else if (minHeap.size() > maxHeap.size() +1){

maxHeap.add(minHeap.remove());

}

public float getMedian(){

if (minHeap.size() == 0 && maxHeap.size() == 0)

return -1;

else if (minHeap.size() == maxHeap.size())

return (float)(minHeap.peek()+maxHeap.peek())/(float)2;

else

return (minHeap.size() < maxHeap.size()) ? maxHeap.peek():minHeap.peek();

}

public static void main(String[] args) {

int[] t = new int[]{4,-2,1,2,-3};

MovingMedian m = new MovingMedian();

for (int tt : t)

m.add(tt);

System.out.println(m.getMedian());

}

统计学的一个方法, 多用在股票上, 不过我不炒股, 我不知道这个东西学名叫什么. 给一个streaming data, 让你找到最近出现的k个元素的平均数. 我看到网上好多人用doubly queue. 感觉没必要, 可以用个fixed size array. 然后需要注意的是窗口展开的时候, 要特殊照顾一下. 当遇到k+1元素的时候, avg(k+1) = (item(k+1) + avg(k)*k)/(k+1).

/**
 * Created by Chenguang He (readman@iastate.edu) on 10/5/15.
 *
 * given streaming data, find the average of k latest elements;
 */
public class MovingAverage {
    private float avg;
    private int windowsSize;
    private float[] samples;
    private int index = 0;
    private int k = 0;
    public MovingAverage(int k){
        this.windowsSize = 0;
        this.k = k;
        samples = new float[k];
    }

    public void add(float val) {
        float pre = samples[index];
        samples[index] = val;
        if (windowsSize < k){
            avg = avg * ((float)windowsSize) / ((float)windowsSize+1);
            windowsSize++;
        }
        avg = avg + (val  - pre) / windowsSize;
        index = (index+1) % k;
    }

    public float getAvg(){return avg;}


    public static void main(String[] args) {
        MovingAverage average = new MovingAverage(2);
        average.add(5);
        average.add(11);
        average.add(3);
        average.add(3);
        average.add(3);
        average.add(3);
        average.add(3);
        System.out.println(average.getAvg());
    }
}

/**

* Created by Chenguang He ([email protected]) on 10/5/15.

* given streaming data, find the average of k latest elements;

public class MovingAverage {

private float avg;

private int windowsSize;

private float[] samples;

private int index = 0;

private int k = 0;

public MovingAverage(int k){

this.windowsSize = 0;

this.k = k;

samples = new float[k];

}

public void add(float val) {

float pre = samples[index];

samples[index] = val;

if (windowsSize < k){

avg = avg * ((float)windowsSize) / ((float)windowsSize+1);

windowsSize++;

}

avg = avg + (val - pre) / windowsSize;

index = (index+1) % k;

}

public float getAvg(){return avg;}

public static void main(String[] args) {

MovingAverage average = new MovingAverage(2);

average.add(5);

average.add(11);

average.add(3);

System.out.println(average.getAvg());

}

Data Stream

Moving Median

Moving Average

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags