Menu Sidebar
Menu

Kolmogorov–Smirnov测试

今天看Apache Flink是怎么测试streaming data的random sampling的. 然后看到里面测试代码(https://github.com/apache/flink/blob/master/flink-java/src/test/java/org/apache/flink/api/java/sampling/RandomSamplerTest.java)用的是Kolmogorov–Smirnov测试, 就查了一下相关的文献, 发现这个测试真是好用.

首先, 这个测试有很多的用法, 我使用它的原因主要是用于测试sampling是否是随机的. 在分布式系统下的sampling, 不能紧紧通过观察结果就判断当前抽样函数是否是随机抽样, 这个测试可以快速的测试一个expected result(期待函数的抽样结果)和一个actual result(当前函数的实际抽样结果), 通过勾画两个生成抽样的函数, 找到其中排序后, 每个误差最大值, 然后累计相加, 取生成一个p值, 通过对比p值和d值(d值为一个固定量), 可以直到当前抽样是否接近于随机抽样. p如果小于d,则是类随机抽样, 反之则否.

p的公式很复杂, 但是代码很易懂,这里上下代码:

然后d值是一个固定值, 取决于两个样本集合的大小:

注意, 这里的1.63不是个常数!, 是需要查表: 表在

https://www.webdepot.umontreal.ca/Usagers/angers/MonDepotPublic/STT3500H10/Critical_KS.pdf

其中a是critical value

CommerceHub面试

因为要去Albany, 所以要面那边的公司, 就投了这个公司.

开始扔了一个作业过来, 让我两天就交, 我这边又答辩,又工作, 真是累死人了. 作业很简单, 就是实现一个数据仓库, 需要注意一下多线程同步访问的问题. Code: https://github.com/gaoyike/CommerceHub

交了后三天收到电面, 然后就开始各种不靠谱. 面我的是一个2016的新SDE, 问的题是, 让你设计一个300 room的旅店, 然后就没了, 我从底层开始讲设计, 一直讲到分布式. 对面一直嗯嗯嗯, 结果问我一个问题: 你用什么IDE….  我突然就愣了, 我说我用intellij idea, 他说, 有意思, 你继续…然后我讲怎么rollback, 怎么做memcache, 然后又一阵嗯嗯嗯, 然后问我, 如果系统死机, 或者很慢, 你怎么办, 我说加cache, 然后做冗余, 我越来越觉得我面的不是SDE….最后一个问题彻底击垮了我: 如果用户一直说很慢, 你首先检查什么部分. 我说我先看log服务器, 然后dump内存. 看看是不是哪里有bug. 对面说, 有意思….我操 ‘有意思’…..

结果两天就收到说不fit……我也觉得真不fit..

CAS (Compare-and-Swap) 以及相关问题

CAS (Compare-and-Swap) 是一种硬件上, 实现非锁同步的一种方法. 这种方法比传统的blocked方法在硬件上实现, 效率高而且内存命中率高.

CAS实现的是一种先验的赋值方法, 即: 给出一个当前值v, 当想改变这个当前值的时候, 一个线程需要进行先验操作, 以当前线程为观察者, 查看改变对象是否是当前线程中期待的对象的值. 如果是才去改变它.  整个行为并非通过锁住线程实现的, 而在硬件上, 访问一个内存片段上的速度远远快于在更高层锁住当前线程的速度. 所以CAS被认为是比所要快速的实现原子化操作的方法之一.CAS 和 CAS2 被用在了Java自带的AtomicInteger, AtomicBoolean, AtomicReference上. 这些变量都是可以常常用作判断线程进行状态的flag. 传统的关键字volatile只保证了变量的visibility, 却缺乏了accessibility. 而使用Java自带的原子变量, 可以更有效的, 快速的解决并发的实际问题.

一个CAS的赋值操作, 由一个pair组成: (expectedCurrentValue, newValue). 当赋值实现了CAS的变量一个新值的时候, 先验当前值是否等于expectedCurrentValue, 如果等于, 则赋newValue, 否则返回CAS变量的值, 这样, 通过比较返回的值, 就可以知道是否赋值成功.

通过以上的CAS, 延伸出了ConcurrentStack (Treiber, 1986), Non-blocking Queue (Michael and Scoot, 1996) 等non-blocking的数据结构. 这些数据结构因为更贴近硬件操作并且是线程安全的, 所以在新的JVM中, 很多Concurrent的数据结构都使用了这种CAS的思想.

但是设计一个CAS的数据结构, 需要充分理解数据结构在并发下的state机制, 设置一个或者两个CAS的flag解决对个state之间转换, 来增加运行速度, 当CAS的变量过多, 并发下, 其实与blocked的数据结构比并没有太大优势.

Shortest Word Distance

 

Educational Codeforces Round 1 A. Tricky Sum

原题: http://codeforces.com/contest/598/problem/A


题目大意: 给一个数字n, 求1…n的合, 其中如果遇到2的倍数的数,要当负数处理.


分析: 直接求O(n) 会超时, 所以会想到求和公式.

通过观察可以发现, 给一个n, 我们可以:

  1. 求1到n的合, 用等差数列求和公式.
  2. 找到1到n中,有多少个2的倍数, 用对数公式, 这里注意, 1也是, 所以求完log后要用flooring求包含几个2的倍数后, 要加上1.
  3. 用公式Screen Shot 2016-02-27 at 11.59.02 AM
  4. 减去两杯的上面公式的结果就是答案了.

Apache Flink中实现的两种水塘抽样算法

因为Flink和我毕设有关, 所以这几天一直在看Flink的源码. Flink中实现了两种水塘抽样算法:

  1. Reservoir Sampler With Replacement https://ci.apache.org/projects/flink/flink-docs-master/api/java/org/apache/flink/api/java/sampling/ReservoirSamplerWithReplacement.html
  2. Reservoir Sampler Without Replacement https://ci.apache.org/projects/flink/flink-docs-master/api/java/org/apache/flink/api/java/sampling/ReservoirSamplerWithoutReplacement.html

对应的paper是:

  1. Optimal Random Sampling from Distributed Streams Revisited http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/tw11.pdf
  2. Random Sampling with a Reservoir http://www.cs.umd.edu/~samir/498/vitter.pdf

两种抽样的区别,(假设, k是已知的抽样数量):

  1. With Replacement是先取第一个样品, 然后做k个’复制'(这里的复制是对象是样品的value, 每个复制都有一个weight, 这个weight是随机生成的, 在Flink中, 用的是XOrShift随机数), 装满 大小为k的PriorityQueue中, 然后每次取下一个样品, 都做k个’复制’,然后如果’复制’的样品的weight大于当前PriorityQueue中, 就Remove PriorityQueue中队列顶端元素, 然后把当前’复制’放入PriorityQueue.
  2. Without Replacement是现取k个样品, 存入大小为k的PriorityQueue中, 每次取新的样品时, 算一个随机数, 如果这个随机数比当前PriorityQueue的队列顶端元素的weight值大,就Remove PriorityQueue中队列顶端元素, 然后放入当前元素.

值得一提的是, Flink中, 虽然在partition过程中实现了以上两种算法, 但是在reduce的过程, 并没有区别, 全部都用的是[2]算法, 这里我想,也许是为了保证reduce的速度, 减少随机数的计算时间, 而做的改变. 详情请见: https://github.com/eBay/Flink/blob/master/flink-java/src/main/java/org/apache/flink/api/java/sampling/DistributedRandomSampler.java

Recover Rotated Sorted Array

 

Partition Array by Odd and Even

给一个数组, 把奇数放左边, 偶数放右边.

其实就是一个quicksort的partition的改写, 改写的地方很少, 就是判断条件从 nums[i] 对 nums[k]的比较改成nums[i] % 2 != 0的比较.

 

Happy Number

 

 

Maximum Minimum Path in Matrix

给一个矩阵,

  1. 先找所有从左上到右下的path.
  2. 找出每个path的最小值.
  3. 找出这些最小值中的最大值.

这题看着挺乱的, 给个例子就清楚了.

这个返回5

所有的path:

8->4->3->5->8 min:3

8->4->3->9->8 min:3

8->4->5->9->8 min:5

8->6->5->9->8 min:5

Result = Math.max(3,3,5,5,) = 5

Code:

 

 

Newer Posts
Older Posts

书脊

倾城与倾国, 佳人难再得