Menu Sidebar
Menu

Algorithm

读[Richardson Maturity Model]

原文地址: https://martinfowler.com/articles/richardsonMaturityModel.html#level0 这篇文章讲述了RESTful的定义和设计模型, 对于每个方法分开讲解了其特点和使用时的注意事项: GET vs POST: GET 返回的是HTTP 200 OK. POST返回的是HTTP 201 Created. 当GET不到东西时, 应该返回HTTP 200和空的数据结构, POST的东西已经存在时, 应该返回HTTP 409 Conflict。 在只获取数据而不改变数据时, 应该使用GET, GET应该伴随着caching的优化. GET应该是一个safe operation,对应着POST是一个non-safe operation. GET对应的是read, POST对应的是write在consistency model中. PUT vs POST: 这两个都是更新数据库的方法, 通常下认为PUT是update, POST是create. 但是和一般数据库定义的CRUD有区别, PUT更倾向于更新一个给定地址上的数据, 而POST仅仅是发布一个数据到一个link.比如: 当PUT /www.chenguanghe.com/article/123 时,后台应该: 找到文章id为123的文章 更新文章id为123的文章 返回HTTP 200 OK 当POST /www.chenguanghe.com/article 时, 后台应该: 创建一个文章, 比如其id为333 在333下创建POST的内容. 返回HTTP 201 […]

读[Seminal Ideas from 2007]

今天的google research 发布了ICML Test-of-Time Award 的一个视频介绍. 主要讲解了AlphaGo使用的算法和决策模型的建立. 使用的算法包括: Monte-Carlo Tree Search AlphaGo主体策略的数据结构, 其他的算法的输入, 输出, 都体现在这个数据结构基础上. 每个node代表一个状态, 如果是围棋,就是当前的棋盘状态和那一方执棋, Node包含以下信息: 来自于蒙特卡洛树的概率信息,比如4/5的意义是:4次取胜/5次当前状态 来自于online(当前棋盘)的RAVE(rapid action value estimation)信息,用于快速进行树的探索 来自于online(当前棋盘)的UCT(Upper Confident Bounder)信息,用于在subtree之间(Guess)跳转,避免local optimization. 来自于offline信息,用来对于当前node进行初始化(这个非常重要, 因为棋盘足够大的时候, 如果没有初始化, 那么一切决策都来自于online的信息, 这样当前node的胜利概率在一开始的时候, 将会非常不可靠, 从而影响整个策略的选择)和再次策略验证(当online策略不确定时,需要offline的数据支持, 可以想象成一个选手对于当前棋局由于不决的时候, 他会想起以前看的棋谱中大师是怎么决策的, 从而进行下一步策略分析) Reinforcement Learning: 用来训练机器对棋谱的认识, 从而记录大师的思路. Convolutional Neural Network: 用来训练机器对整个棋局的认识, 从而让机器模糊的对黑白子进行图像化记忆, 这可以让机器对棋盘的布局有一个总体的分析. 每个edge代表一个policy的使用. policy有两种层面: Tree Policy: 一种greedy policy,建立MCTS树的基本使用方法. Rollout Policy: 一种随机部分的policy,用来访问MCTS树的节点的policy. […]

[读] Consistent Hashing with Bounded Loads

Consistent Hashing with Bounded Loads 这篇paper是google research发布的一篇关于解决在很大的分布式系统下Consistent Hashing存在的一些问题 比如: Hashing分配不平均: 普通的Hashing存在分配不均的情况, 这会让有些服务器在突然上涨的流量下瞬间过载. Cache问题: Hashing的目的是分配, 但是这种离散式的分配方式会使得前端的Cache Hit下降, 一些hot的资源在没有足够的Cache Hit下, 会很快消耗掉所有当前服务器的资源, 造成lag或者server down. Hash 函数的问题: 如何选择一个对于当前资源最优的Hash方法. 特定的Hash方法会不会造成1中提到的分配不均问题? 文章的背景: 我看到的这个文章是从google talk里看到的, 里面vimeo的工程师阐述了他们遇到的一系列问题,最后提出了这个解决方案. Vimeo做的是online的视频服务, 当用户上传一个video时, 比如lady gaga上传了一个mtv, 这时服务器要分解这个video, 对每个模块做index,并使用Consistent Hashing搜索当前负载最小的服务器(least connection), 然后离散的把index放在上面, 并且put到 Index cache中, 最后把indexed video放到google cloud上. 当用户query这个视频时, 比如上文提到的lady gaga MTV, 这种很hot的资源会对cache index有极大的依赖, 但是问题出在离散分布的index, 有分配不均的情况, 这使得这种hot的资源瞬间占满了index服务器, 而这时, 一般服务器会认为是cache的问题, dump所有的cache来增加cache […]

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面试成功.

 

Older Posts

书脊

倾城与倾国, 佳人难再得