Menu Sidebar
Menu

2017年展望

近于而立之年, 一些回首和展望.

从前读过冯唐的一首诗,名为《可遇不可求的事》,就当个引子吧

可遇不可求的事

冯唐

后海有树的院子

夏代有工的玉

此时此刻的云

二十来岁的你

就从这个’诗’, 先来聊聊冯唐这个人: 写过很多’诗’, 这个引号是一定要的. 因为其中很多的, 已经远远不能用俗来形容了, 不过这并不影响受欢迎的程度, 究其原因, 一个是因为范冰冰那个电影, 另一个是因为他是北京人.

如果一个其他地方的人, 看这首诗, 也许只会理解成: 后海有树的院子很贵, 夏代有工的玉也很贵, 进而理解妹纸也是可遇不可求的. 不过作为北京人, 我其实越发觉得, 这些东西之所以可遇不可求,不是因为钱的问题, 而是因为已经不存在了,或者说存在的意义已经不重要了.

回首往事, 我能记得的, 也只有:

2000年, 伴随着千禧年的钟声和千年虫的困扰, 我在南京, 这个有五座长江大桥,一座隧道的城市, 在南京邮电和南工大的合作下, 跟随一个小组在做中国最大的国家性互联网工程: 南北互联.

2001年, 我在天安门的人流中, 欢庆着申奥成功.

2008年, 我在机场看着北京奥运会开幕式, 离开北京, 前往美国.

这一晃就是8年,

2016年, 我在纽约参议院, 见证川普的逆袭.

还有, 2016年, 我认识了她.

2017, 我而立之年, 总觉得要发生点什么. 无论好坏, 希望是不平凡的一年.

Educational Codeforces Round 1 D. Igor In the Museum

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


题目大意: 给一个图, 点(.) 是人可以待的位置, 星号(*) 是墙壁, 找出点和星号相邻的可能有多少个.


分析: 上来flood fill, 秒挂testcase 10, 加了visited[][] 秒挂testcase15, 后来发现里面重复请求非常多 真是!@#@!#!, 于是记录一下每次请求的结果. 原想是用uf记录, 后来想了想有现成的k, 就用k记录了…一个hashmap来的比uf方便的多.

 

Educational Codeforces Round 1 B. Queries on a String

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


题目大意: 给一个string, 给l,r,k三个数, l和r是其中的char的index(以1为底), 求k次右shift后的string


分析: 没有什么算法, 就是注意是以1为底, 然后特殊情况有两种, 一个是k比r-l+1大, 所以取余, 另一个是r==l, 别的都是照常实现就好.

[LintCode] Update Bits

n = n & ~(1 << k); 就是把n中的第k个bit设为0

n = n | ((m & (1<<(k-i)))<<i);

  1. m & (1<<(k-i)) 是从m的第一个bit开始扫描.因为已知j-i = size of (m)2
  2. ((m & (1<<(k-i)))<<i) 扫描后, 往左shift i位对准n上的i位.
  3. n = n | ((m & (1<<(k-i)))<<i) 把n的第i位到j位设为m的0~(j-i)位

Hilbert Curve 算法

最近看google的s2库, 里面用到了Hilbert Curve的算法,  算法早就忘了, 就记得那个图是以前家里厨房垫脚用的脚垫上面的图案, 当时还说了句, “看来这个设计师还是个数学家”.

先来个图:

是不是很像个迷宫. 这个图乍一看是有逻辑的, 但是很难立刻说出来, 因为上面的图没有划分boarder. 其实左上的图是order/level = 1的Hilbert Curve. 然后是2 3 4 5 6, 我怎么知道的?  先看看介绍:

在那遥远的年代, 18xx年吧..那时候有帮人,在研究: 如何将一个一维空间上的线映射到一个二维空间上, 致使线穿过二维空间上的每个点, 然后不交叉. 这个问题看起来很simple, 但是有好多条件哇, 首先是这个space是continue的, 就是说无限大, 然后线穿过的点要无限的小和无限的多, 也就是说, 你不能数出来这些点有多少, 但是你需要证明你这一条线是肯定穿的过去的.举几个反例:

Screen Shot 2016-05-04 at 11.48.14 AM <–这图来自于https://www.youtube.com/watch?v=DuiryHHTrjU 这个视频很好哇

上面的图就不行, 为啥呢?  因为上面的space是由边际的,所以你才知道啥时候拐弯不是么?

Hilbert Curve的构建:

  1. 先画上面的图1
  2. 做4个图1的copy, 然后翻转上面2个.
  3. 交叉连接两个脚
  4. 继续做2~3步…

Hilbert Curve 有很多很好的性质 (那个视频介绍了很多):

  1. 连续性:  作为一个continually mapping, Hilbert Curve能准确的:1) 将一个数字比如(0.24) 映射到二维空间上的一点, 并且维度增加时,比如level: 2->4, 点不移动, 2) 因为数字是连续的, 比如0.24,0.25….., Hilbert Curve能做到数字映射后的curve中的点也是连续的. 这个是其中一个精髓.
  2. 可扩展性: 比如上面的snake curve当空间扩展的时候, 图像上的点要flip到其他位置, 这意味着每个点的位置当空间扩展时都要update, 这个update是指数时间的(空间扩展是指数的), 而上面红色Hilbert Curve可以保证只需要重新连接固定的几个点, 就实现了无限扩展的空间.
  3. 稳定性: 和可扩展性类似, 随着level的增加, 每个点在图上的移动距离会越来越小, 而因为level增加, 图形越来越大, 使得点的移动变得不再重要.所以可以看做不移动.
  4. 相关性: 连续的数字对应的点也是相近的, 但是相近的点不一定对应相近的数字

Google的s2库资料很少, 但是Hilbert Curve的算法却很经典, 不过我仔细看了一下, 发现在做点的查询的时候,Google进行了很多优化..具体为什么, 我还需要时间看下..不过构建Hilbert Curve的方式一样. Google用的是level30的Hilbert Curve, 约等于2^30, 真是很大的图,哈哈哈.

这里有个demo, 不是我写的哈:

http://bit-player.org/extras/hilbert/hilbert-mapping.html

Josephus problem 约瑟夫环问题

约瑟夫环问题的描述如下:

n个人, 1,2,3….n. index从1开始, 踢出第k个. 然后问留下的几号?

这个和小时候分拨用的, “泥锅儿 泥碗儿 你滚蛋” 一模一样, “泥锅儿 泥碗儿 你滚蛋”是k= 9的约瑟夫环问题.

用动态规划, 可以得到一下公式:

f(n,k)=((f(n-1,k)+k-1) \bmod n)+1,\text{ with }f(1,k)=1\,,

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

 

Integer Break

找规律:

 

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, 在每次调用的时候, 更新当前随机选中的神经元,然后传导至所有的神经元. 这种全局更新的方法, 虽然很浪费时间, 但是保证了传导的准确性,举个栗子: 还是上面的例子, 虽然脚趾扎了个刺没有手指痛, 但是你不能不告诉大脑, 脚趾扎刺了. 当然, 有时候,真的因为这个神经冲动太小了, 脚上干裂了个小口子, 很多时候人自己感觉不到. 但是即使是很小的冲动, 也要更新所有的神经元, 这个思路是没错的.

displaymath1981

这个就是neighborhood function, a(t) 是个递减函数, 没啥大意思, 我就用了一个线性递减, ri和rc是两个神经元, theta(t) 是个衰减参数.

最后, Kohonen network的本质是由两个hidden layer的神经网络组成, 首先是一个Hamming network, input是低维vector的数组(n-tuple), 然后通过全联通网络, 返回互相直接的weight. 然后是一个maxnet network, maxnet的input是一个weight vector, 通过递归的方法, 返回最大weight神经元的index, 并且让其它的神经元同比衰减. 因为有maxnet的存在, 所以Kohonen SOM是Winner Take-All learning.

下面是一个用KNN实现的模拟解决TSP(Travelling Salesman Problem)的demo:

http://www.chenguanghe.com/project/tsp.html

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是当前数据的总数. 这个算法有两部分组成.

  1. 作者定义了一个阈值T, T=4R, R是样品集合的大小. 这里的4是由随机数的好坏确定的. 确定的方法很复杂. 如果数据量小于阈值T, 则使用传统的水塘抽样. 这里使用水塘抽样的原因是,
    1. 如果当前的数据量小, 则生成gap会大大影响抽样结果的分布. 因为这个算法的gap是通过累计分布最后达到均匀分布的, 少量的gap会产生极大的误差. 通过实验表明, KS-test下, 如果样品大小是100,数据量是100000, 那么与随机抽样比较, 误差远远超过了 KS-test的容忍值D.
    2. 在数据量小的情况下, 生成少量随机数并不会对系统产生太大的负担, 这种trade-off是可以接受的.
    3. 水塘抽样的分布和数据量无关, 所以即使抽样大小和数据量很接近, 比如R=100, j=10000, 也可以完美的进行随机抽样.
  2. 当数据超过T, 开始使用几何分布的抽样,我们用如下的方式计算gap:
    1. 首先算出p, 即理想的随机抽样下,  当前样品被抽中的概率, 显而易见, p = R/j
    2. 1-p 就是没有被抽中的概率, 那么生成u, 一个(0,1)的float, 做Math.log(u)/Math.log(1-p) <—这个公式的意义是, 在1-p的周围取gap.
  3. 然后通过省略gap个元素, 取下一个, 就可以实现随机抽样.

 

这个算法非常依赖于抽样大小和数据量之间的关系, 如果前者不是远远小于后者, 那么gap的大小会导致分布极度不均, 这种不均会使样品的误差很大.

下面是code:

https://github.com/gaoyike/flink/blob/81e0622b20d8bc969dec1555bd55d4230d9b38de/flink-java/src/main/java/org/apache/flink/api/java/sampling/VeryFastReservoirSampler.java

Older Posts

书脊

倾城与倾国, 佳人难再得