Menu Sidebar
Menu

Algorithm

读 Computing the nearest common ancestor

原文地址: http://codinggorilla.com/?p=91&cpage=1 这篇文章介绍了两种算法, Alstrup-Gavoille-Kaplan-Rauhe(AGKR) 和 Schieber-Vishkin. 他们是用来解决 Nearest Common Ancestor (NCA) 或者 Lowest common ancestor (LCA) 问题的. 首先, 文章给出了NCA/LCA问题的定义, 即在树状结构下, 求解任意两个node的最近公用node. 如上图中, node e和 node m 的公用node是a. 这个问题是 Alfred Aho教授提出的, 就是那个ac自动机匹配的那个a.. 文章给出了一个最简单的算法 这个算法是利用两个node的parent信息, 通过两个stack存储node的路径, 进而找到公用node. 这种解法的时间和空间复杂度是o(n). 最坏情况就是刚才的满树下的最左和最右. Schieber-Vishkin算法是由Baruch Schieber 和 Uzi Vishkin 通过简化 Harel and Tarjan的算法得来的. 它的复杂度包含了两个部分, o(n)的preprocessing(预处理)阶段和o(1)的query(解答)阶段. 在预处理阶段, Schieber-Vishkin算法需要重新编码整颗树: 首先假设一棵树是满树时, 对一棵树做inorder traverse. 并且加一个数字计数器, 便有下图: […]

读[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 […]

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 是因为第一次的时候, 第一个人已经跳过了

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

 

Newer Posts
Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.