Menu Sidebar
Menu

Author: Readman

读[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, 我而立之年, […]

Educational Codeforces Round 1 D. Igor In the Museum

原题:http://codeforces.com/contest/598/problem/D 题目大意: 给一个图, 点(.) 是人可以待的位置, 星号(*) 是墙壁, 找出点和星号相邻的可能有多少个. 分析: 上来flood fill, 秒挂testcase 10, 加了visited[][] 秒挂testcase15, 后来发现里面重复请求非常多 真是[email protected]#@!#!, 于是记录一下每次请求的结果. 原想是用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); m & (1<<(k-i)) 是从m的第一个bit开始扫描.因为已知j-i = size of (m)2 ((m & (1<<(k-i)))<<i) 扫描后, 往左shift i位对准n上的i位. 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的, 就是说无限大, 然后线穿过的点要无限的小和无限的多, 也就是说, 你不能数出来这些点有多少, 但是你需要证明你这一条线是肯定穿的过去的.举几个反例:  <–这图来自于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

 

Older Posts

书脊

倾城与倾国, 佳人难再得