Menu Sidebar
Menu

Data Stream

Moving Median

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

 

Moving Average

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

 

书脊

倾城与倾国, 佳人难再得