Menu Sidebar
Menu

Algorithm

2017年展望

近于而立之年, 一些回首和展望. 从前读过冯唐的一首诗,名为《可遇不可求的事》,就当个引子吧 可遇不可求的事 冯唐 后海有树的院子 夏代有工的玉 此时此刻的云 二十来岁的你 就从这个’诗’, 先来聊聊冯唐这个人: 写过很多’诗’, 这个引号是一定要的. 因为其中很多的, 已经远远不能用俗来形容了, 不过这并不影响受欢迎的程度, 究其原因, 一个是因为范冰冰那个电影, 另一个是因为他是北京人. 如果一个其他地方的人, 看这首诗, 也许只会理解成: 后海有树的院子很贵, 夏代有工的玉也很贵, 进而理解妹纸也是可遇不可求的. 不过作为北京人, 我其实越发觉得, 这些东西之所以可遇不可求,不是因为钱的问题, 而是因为已经不存在了,或者说存在的意义已经不重要了. 回首往事, 我能记得的, 也只有: 2000年, 伴随着千禧年的钟声和千年虫的困扰, 我在南京, 这个有五座长江大桥,一座隧道的城市, 在南京邮电和南工大的合作下, 跟随一个小组在做中国最大的国家性互联网工程: 南北互联. 2001年, 我在天安门的人流中, 欢庆着申奥成功. 2008年, 我在机场看着北京奥运会开幕式, 离开北京, 前往美国. 这一晃就是8年, 2016年, 我在纽约参议院, 见证川普的逆袭. 还有, 2016年, 我认识了她. 2017, 我而立之年, […]

Hilbert Curve 算法

最近看google的s2库, 里面用到了Hilbert Curve的算法,  算法早就忘了, 就记得那个图是以前家里厨房垫脚用的脚垫上面的图案, 当时还说了句, “看来这个设计师还是个数学家”. 先来个图: 是不是很像个迷宫. 这个图乍一看是有逻辑的, 但是很难立刻说出来, 因为上面的图没有划分boarder. 其实左上的图是order/level = 1的Hilbert Curve. 然后是2 3 4 5 6, 我怎么知道的?  先看看介绍: 在那遥远的年代, 18xx年吧..那时候有帮人,在研究: 如何将一个一维空间上的线映射到一个二维空间上, 致使线穿过二维空间上的每个点, 然后不交叉. 这个问题看起来很simple, 但是有好多条件哇, 首先是这个space是continue的, 就是说无限大, 然后线穿过的点要无限的小和无限的多, 也就是说, 你不能数出来这些点有多少, 但是你需要证明你这一条线是肯定穿的过去的.举几个反例:  <–这图来自于https://www.youtube.com/watch?v=DuiryHHTrjU 这个视频很好哇 上面的图就不行, 为啥呢?  因为上面的space是由边际的,所以你才知道啥时候拐弯不是么? Hilbert Curve的构建: 先画上面的图1 做4个图1的copy, 然后翻转上面2个. 交叉连接两个脚 继续做2~3步… Hilbert Curve 有很多很好的性质 (那个视频介绍了很多): 连续性:  作为一个continually mapping, Hilbert Curve能准确的:1) […]

Josephus problem 约瑟夫环问题

约瑟夫环问题的描述如下: n个人, 1,2,3….n. index从1开始, 踢出第k个. 然后问留下的几号? 这个和小时候分拨用的, “泥锅儿 泥碗儿 你滚蛋” 一模一样, “泥锅儿 泥碗儿 你滚蛋”是k= 9的约瑟夫环问题. 用动态规划, 可以得到一下公式: Base case是: f(1,k) 就是从1个人中踢出第k个, 因为只有一个人, 所以这个人就是留下的. 返回1. Recursion case: f(n,k)从n个踢出k个 n从1开始, f(n-1,k)踢出一个人后, 剩下的人继续玩, k-1是选k个人, +1 是因为第一次的时候, 第一个人已经跳过了

Quicksort for LinkList

当年微软面试题: 少了两个= null, 结果木offer

 

Teuvo Kohonen和他的SOM

Teuvo Kohonen是一位芬兰的科学家, 介绍满街都是,可以自行google, 我就贴一个google scholar (https://scholar.google.com/scholar?hl=en&q=Teuvo+Kohonen&btnG=&as_sdt=1%2C16&as_sdtp=) Kohonen博士为什么那么伟大呢? 让我慢慢道来, 在deep learning中, 无监督学习(unsupervised learning)一直是最受关注的焦点, 其中, 各种算法不计其数, 但是人工神经网络算法中, 最著名的算法, 就当属Kohonen博士开发的Kohonen SOM(Self-Organizing Maps), 这个著名有几个理由: 首先, Kohonen SOM是当今运用最广泛, 最贴近真实的神经激活方式的一种模拟人工神经网络, 这种真实体现在Kohonen博士对神经激活时, 状态的转换方程和激活后, 神经元之间关系的特殊理解. 举个栗子: 当你手指扎刺的时候, 神经传输到大脑, 你会感到疼痛, 但是当你脚趾扎刺的时候, 同样的疼痛, 你大脑反应会和手指不同, 因为神经元之间的固定初始位置,导致了神经冲动的传输有了衰减, 这种衰减可以被看做是learning rate的递减, 也可以想象成是一种regularization, 这种regularization是一种常态的regularization, 也就是说, 他并不是人为干预的衰减, 而是取决于神经元本身的固定属性(比如神经元之间的初始固定位置). 这也就是为什么Kohonen SOM是模仿人类神经冲动传导最好的人工神经网络. 其次, Kohonen SOM的neighborhood function, 在每次调用的时候, 更新当前随机选中的神经元,然后传导至所有的神经元. 这种全局更新的方法, 虽然很浪费时间, 但是保证了传导的准确性,举个栗子: 还是上面的例子, 虽然脚趾扎了个刺没有手指痛, 但是你不能不告诉大脑, 脚趾扎刺了. […]

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.  

 

Older Posts

书脊

倾城与倾国, 佳人难再得