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面试成功. public class ReadWriteLock { interface Mutex {// given an mutex public void lock(); public void unlock(); } Mutex readLock; // read lock, in order to support PRAM CREW. it only lock when Mutex writeLock; // write lock. only lock […]

Date November 18, 2015
Category Algorithm
Comments No Comments

Moving Median

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

Moving Average

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

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. package Learning;/** import java.util.*; public class NextHigherKeyinBST { static class TreeNode { // Node 有 parent TreeNode parent; TreeNode left; TreeNode right; int val; private TreeNode(){} public TreeNode(TreeNode p, int val) { this.parent = p; this.val = val; } […]

Swap Two Integer without Temporary Variable

How to swap two integer without temportary variable ? 可以用XOR: public class SwapTwoIntegerWithoutVariable { public static void main(String[] args) { int a = Integer.MAX_VALUE; int b = Integer.MIN_VALUE; a = a^b; b = a^b; a = a^b; System.out.println(“a “+a); System.out.println(“b “+b); } }

Date September 21, 2015
Category Algorithm
Comments No Comments

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是当前数据流.

Date August 7, 2015
Category Algorithm
Comments No Comments

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

给一个数组, 找数组中的一个点, 使在这点的左边数的和,等于右边的和. 注意: 这里不是sorted数组. 所以我们用meet in middle的做法. 而且数组会有负数, 对于负数, 我们需要在另一边加上这个数. public int find (int[] nums) { int l = 0; int r = nums.length – 1; int suml = 0; // sum of left side int sumr = 0; // sun of right side while (l <= r) { if (l == r && […]

[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的倍数了. public static boolean isPowerof4(int n) { return (n&n-1)+n%3==1; } 下边是power of 8 public static boolean isPowerof8(int n) { return (n&n-1)+n%7==1; }

Date August 2, 2015
Category Algorithm Geeksforgeeks Interview Question
Comments No Comments

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公式的原因. 所以任意给一个正整数序列, 都能对上一棵树… 其他应用…我还真是不知道…