Menu Sidebar
Menu

Algorithm

Very Fast Reservoir Sampling by Erik Erlandson

今天正式的把这个抽样算法加到Apache Flink里了, 这个算法是Erik Erlandson在他的博客上公布的大概是迄今为止最快速的抽样算法的. 这个算法采用了流行的gap distribution的方法抽样, 有效的在减少cpu使用的情况下, 减少了内存的占用, 通过生成抽样之间的gap, 进行近似随机抽样. 在他的博客http://erikerlandson.github.io/blog/2015/08/17/the-reservoir-sampling-gap-distribution/中,  证明了抽样可以通过生成gap实现随机抽样, 大大减少了随机数的生成时间和占用的内存, 实际应用下, 可以大大增加整体系统的运行效率. 他的博客中, 有基于Bernoulli Distribution(https://github.com/apache/flink/blob/master/flink-java/src/main/java/org/apache/flink/api/java/sampling/BernoulliSampler.java)和Poisson Distribution(https://github.com/apache/flink/blob/master/flink-java/src/main/java/org/apache/flink/api/java/sampling/PoissonSampler.java)的两种实现, 在Apache Flink中, Bernoulli分布实现了非replacement的抽样, 而Poisson分布实现了replacement的抽样. 这个新的优化算法, 使用了几何分布(https://en.wikipedia.org/wiki/Geometric_distribution)的思想, 对于样品大小远远小于数据大小 (1000000倍以上)的情况下, 样品的抽样率近似于P = R/j, R是样品集合大小, j是当前数据的总数. 这个算法有两部分组成. 作者定义了一个阈值T, T=4R, R是样品集合的大小. 这里的4是由随机数的好坏确定的. 确定的方法很复杂. 如果数据量小于阈值T, 则使用传统的水塘抽样. 这里使用水塘抽样的原因是, 如果当前的数据量小, 则生成gap会大大影响抽样结果的分布. 因为这个算法的gap是通过累计分布最后达到均匀分布的, 少量的gap会产生极大的误差. 通过实验表明, KS-test下, 如果样品大小是100,数据量是100000, 那么与随机抽样比较, 误差远远超过了 KS-test的容忍值D. 在数据量小的情况下, 生成少量随机数并不会对系统产生太大的负担, 这种trade-off是可以接受的. 水塘抽样的分布和数据量无关, 所以即使抽样大小和数据量很接近, […]

ReadWriteLock

给一个Mutex,里面有lock(),unlock() 实现一个ReadWriteLock, PRAM CREW (同步读, 读时lock写, 写时lock写). 需要实现的方法有, readLock(), readUnlock(), writeLock(), writeUnlock() 这个没什么好讲的…基础os操作… 这题好像软软经常出, 所以我就做一下, 保佑onsite面试成功.

 

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).

Find Next Higher Key in BST (Given Parent)

找后继节点, 但是这里给了父节点. 很简单的考虑一下几种情况: 引用一下http://www.algoqueue.com/的图 比如3, 有右节点, 所以我们返回右节点的最左节点(后继).. 比如2, 没有右节点, 但是2是父节点3的左节点, 所以返回3. 假设没有7, 6没有右节点(没有7), 但是6是3(父节点)的右节点,所以我们只能往上找, 直到找到3是8的左节点, 返回8.

Swap Two Integer without Temporary Variable

How to swap two integer without temportary variable ? 可以用XOR:

 

Reservoir Sampling 水塘抽样

水塘抽样是一组解决数据流取样的方法, 有很多的变种. 它适用的问题有如下特点: 对象为无法在内存中放下的数据, 如不间断数据流, 或者巨大的文件, 数组等. 样本集的大小为k, 并且要求每个样本的取样概率相等. 取样概率可以通过添加权重(weight)来改变取样概率. 一般(无weight)水塘抽样的每个样本的取样概率为: k/(n+1) 水塘抽样的算法实现非常简单, 而且证明简练. 算法如下: 预设数组A, 大小为k. 先取样k个元素. 放入A中. 从k+1元素开始, 每次取得随机数r, 范围为(0,k+1). 如果r <= k, A[r] = S[k+1], S是当前数据流.

Find the point in array with equal sum of left and right. 找数组中的一个点, 使左右的合相等

给一个数组, 找数组中的一个点, 使在这点的左边数的和,等于右边的和. 注意: 这里不是sorted数组. 所以我们用meet in middle的做法. 而且数组会有负数, 对于负数, 我们需要在另一边加上这个数.

 

[Google] isPowerof4 O(1)找4的倍数.

Google电面的Bit操作题, 问你能不能用一个O(1)的方法, 判断n是不是4的倍数. 既然是O(1), 所以不能用循环, 先把n对n-1取&, 假设n = 16, 即10000. n-1=15,即01111.  但是我们还需要判断这个数是不是0. 所以我们让n对一个比它小的质数取mod. 比如4%3==1, 这样就可以判断n是不是4的倍数了.

下边是power of 8

 

Prufer Sequence 普吕弗序列

最近在翻看伯克利的组合数学课, 恰巧看到了这个. 当时对Prufer的认知, 仅限于他能压缩一个标号树(labeled tree), 后来看到Prufer证明Cayley公式: The number of labeled tree with n nodes is n^(n-2). 感觉这个东西还稍微有点用, lol. 要知道什么是Prufer Code, 首先要了接什么是labeled tree. 标号树就是一棵树, 把每个node从1开始标号. 因为是组合数学, 所以问的是, 对于标号n的树, 有几种可能的情况, 这个是Cayley公式. Prufer用Prufer Code证明了这个公式,当然这不是第一次证明. Prufer Code很好理解, 每次拿出编号最小的node, 然后把它的邻居放到序列里, 直到剩下两个点. 逆Prufer Code也好写, 先列1~n个数, 然后拿出(不放回)没有在序列中的最小的数, 和序列首项连起来, 然后删除序列首项, 直到最后剩下两个点, 然后把这2个顶点连起来. Prufer Code最大的应用就是它的唯一性, 即: 唯一的code对唯一的labeled tree. 这也是它被发明出来证明Cayley公式的原因. 所以任意给一个正整数序列, 都能对上一棵树… 其他应用…我还真是不知道…

Newer Posts
Older Posts

书脊

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

December 2022
M T W T F S S
 1234
567891011
12131415161718
19202122232425
262728293031