书脊 | 倾城与倾国, 佳人难再得

读[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.
- (其实这两种policy已经涵盖在上面的learning机制中)

视频中还提到AlphaGo是一个12层的深度神经网络，里面已经涵盖了大部分已知高手的棋谱和思路，并且能通过修改策略参数, 自动进行训练……

Date September 7, 2017
Author Readman
Comments No Comments

[读] 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 hit rate. 然而在这种情况下, cache不会帮助增加用户的相应速度(因为问题不在cache).

解决方案:

文章中提到的分配算法:

算出当前所有server的平均load (avg load).
定义一个参数 f, f的可以理解为一个服务器所能承受的压力的tension(张力), e.g. f = 25%
算出threshold = avg load * f
使用常见的Consistent Hashing 找到一个index服务器, 如果这个服务器当前load超过threshold, 继续找下一个
直到找到下一个小于threshold load的服务器, 执行服务.

Date August 24, 2017
Author Readman
Comments No Comments

2017年展望

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

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

可遇不可求的事

冯唐

后海有树的院子

夏代有工的玉

此时此刻的云

二十来岁的你

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

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

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

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

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

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

这一晃就是8年,

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

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

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

Date January 5, 2017
Author Readman
Comments No Comments

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方便的多.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int m = in.readInt();
        int k = in.readInt();
        char[][] map = new char[n][m];
        int[][] visited = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = in.readCharacter();
            }
        }
        Map<Integer,Integer> list = new HashMap<>(); //记录一下已经算过的
        for (int i = 0; i < k; i++) {
            int t1 = in.readInt() - 1;
            int t2 = in.readInt() - 1;
            if (visited[t1][t2] > 0) {//如果已经算过了, 找出第几次算的答案
                out.printLine(list.get(visited[t1][t2]));
            } else {//如果没算过
                int ans = solve(map, t1, t2, visited, i + 1);//从1开始到k， 每次
                out.printLine(ans);
                list.put(i+1,ans);//记录一下算的结果
            }
        }
    }

    private int solve(char[][] map, int i, int j, int[][] visited, int id) {
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.add(Pair.makePair(i, j));
        int count = 0;
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> cur = queue.poll();
            if (visited[cur.first][cur.second] > 0) {
                continue;
            }
            visited[cur.first][cur.second] = id;
            if (map[cur.first + 1][cur.second] == '.') {
                queue.add(Pair.makePair(cur.first + 1, cur.second));
            } else {
                count++;
            }
            if (map[cur.first - 1][cur.second] == '.') {
                queue.add(Pair.makePair(cur.first - 1, cur.second));
            } else {
                count++;
            }
            if (map[cur.first][cur.second + 1] == '.') {
                queue.add(Pair.makePair(cur.first, cur.second + 1));
            } else {
                count++;
            }
            if (map[cur.first][cur.second - 1] == '.') {
                queue.add(Pair.makePair(cur.first, cur.second - 1));
            } else {
                count++;
            }
        }
        return count;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

public void solve(int testNumber, InputReader in, OutputWriter out) {

int n = in.readInt();

int m = in.readInt();

int k = in.readInt();

char[][] map = new char[n][m];

int[][] visited = new int[n][m];

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

map[i][j] = in.readCharacter();

}

Map<Integer,Integer> list = new HashMap<>(); //记录一下已经算过的

for (int i = 0; i < k; i++) {

int t1 = in.readInt() - 1;

int t2 = in.readInt() - 1;

if (visited[t1][t2] > 0) {//如果已经算过了, 找出第几次算的答案

out.printLine(list.get(visited[t1][t2]));

} else {//如果没算过

int ans = solve(map, t1, t2, visited, i + 1);//从1开始到k，每次

out.printLine(ans);

list.put(i+1,ans);//记录一下算的结果

}

private int solve(char[][] map, int i, int j, int[][] visited, int id) {

Queue<Pair<Integer, Integer>> queue = new LinkedList<>();

queue.add(Pair.makePair(i, j));

int count = 0;

while (!queue.isEmpty()) {

Pair<Integer, Integer> cur = queue.poll();

if (visited[cur.first][cur.second] > 0) {

continue;

}

visited[cur.first][cur.second] = id;

if (map[cur.first + 1][cur.second] == '.') {

queue.add(Pair.makePair(cur.first + 1, cur.second));

} else {

count++;

}

if (map[cur.first - 1][cur.second] == '.') {

queue.add(Pair.makePair(cur.first - 1, cur.second));

} else {

count++;

}

if (map[cur.first][cur.second + 1] == '.') {

queue.add(Pair.makePair(cur.first, cur.second + 1));

} else {

count++;

}

if (map[cur.first][cur.second - 1] == '.') {

queue.add(Pair.makePair(cur.first, cur.second - 1));

} else {

count++;

}

return count;

}

Date June 13, 2016
Author Readman
Comments No Comments

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, 别的都是照常实现就好.

public class TaskB {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        String s = in.readLine();
        char[] chars = s.toCharArray();
        int n = in.readInt();
        for (int i = 0; i < n; i++) {
            int l = in.readInt();
            int r = in.readInt();
            int k = in.readInt();
            solve(chars,l-1,r-1,k);
        }
        out.print(chars);
    }

    private void solve(char[] ary, int l, int r, int k){
        char[] tmp = new  char[r-l+1];
        k %= r-l+1;
        for(int i = l; i <= r; i++){
            tmp[(i-l+k)%(r-l+1)] = ary[i];
        }
        for(int i = l; i <= r; i++){
            ary[i] = tmp[i-l];
        }
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

public class TaskB {

public void solve(int testNumber, InputReader in, OutputWriter out) {

String s = in.readLine();

char[] chars = s.toCharArray();

int n = in.readInt();

for (int i = 0; i < n; i++) {

int l = in.readInt();

int r = in.readInt();

int k = in.readInt();

solve(chars,l-1,r-1,k);

}

out.print(chars);

}

private void solve(char[] ary, int l, int r, int k){

char[] tmp = new char[r-l+1];

k %= r-l+1;

for(int i = l; i <= r; i++){

tmp[(i-l+k)%(r-l+1)] = ary[i];

}

for(int i = l; i <= r; i++){

ary[i] = tmp[i-l];

}

Date June 13, 2016
Author Readman
Comments No Comments

[LintCode] Update Bits

class Solution {
    /**
     *@param n, m: Two integer
     *@param i, j: Two bit positions
     *return: An integer
     */
    public int updateBits(int n, int m, int i, int j) {
        // write your code here
        for(int k = i ; k <= j; k++) {
            n = n & ~(1 << k); // set kth bit in n to 0
            n = n | ((m & (1<<(k-i)))<<i); //set kth bit in n to m's kth bit
        }
        return n;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution {

/**

*@param n, m: Two integer

*@param i, j: Two bit positions

*return: An integer

*/

public int updateBits(int n, int m, int i, int j) {

// write your code here

for(int k = i ; k <= j; k++) {

n = n & ~(1 << k); // set kth bit in n to 0

n = n | ((m & (1<<(k-i)))<<i); //set kth bit in n to m's kth bit

}

return n;

}

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)位

Date May 7, 2016
Author Readman
Comments No Comments

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

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

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

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

Date May 4, 2016
Author Readman
Comments No Comments

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

Date April 30, 2016
Author Readman
Comments No Comments

Quicksort for LinkList

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

    public static ListNode sort(ListNode head){
        if (head == null)
            return head;
        ListNode pivot = new ListNode(head.val);
        head = head.next; // remove pivot
        ListNode lessDummy = new ListNode(0);
        ListNode moreDummy = new ListNode(0);
        ListNode lessP = lessDummy;
        ListNode moreP = moreDummy;

        ListNode p = head;
        while (p != null){
            if (p.val < pivot.val){
                lessP.next = p;
                lessP = lessP.next;
                p = p.next;
            }else {
                moreP.next = p;
                moreP = moreP.next;
                p = p.next;
            }
        }
        lessP.next=null;//<-----当年少了这两个
        moreP.next= null;//<----
        lessDummy = sort(lessDummy.next);
        moreDummy = sort(moreDummy.next);
        lessP = lessDummy;
        moreP = moreDummy;
        if(lessP != null) {
            while (lessP.next != null) {
                lessP = lessP.next;
            }
            lessP.next = pivot;
            pivot.next = moreP;
            return lessDummy;
        }
        else {
            pivot.next = moreDummy;
            return pivot;
        }

    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

public static ListNode sort(ListNode head){

if (head == null)

return head;

ListNode pivot = new ListNode(head.val);

head = head.next; // remove pivot

ListNode lessDummy = new ListNode(0);

ListNode moreDummy = new ListNode(0);

ListNode lessP = lessDummy;

ListNode moreP = moreDummy;

ListNode p = head;

while (p != null){

if (p.val < pivot.val){

lessP.next = p;

lessP = lessP.next;

p = p.next;

}else {

moreP.next = p;

moreP = moreP.next;

p = p.next;

}

lessP.next=null;//<-----当年少了这两个

moreP.next= null;//<----

lessDummy = sort(lessDummy.next);

moreDummy = sort(moreDummy.next);

lessP = lessDummy;

moreP = moreDummy;

if(lessP != null) {

while (lessP.next != null) {

lessP = lessP.next;

}

lessP.next = pivot;

pivot.next = moreP;

return lessDummy;

}

else {

pivot.next = moreDummy;

return pivot;

}

Date April 28, 2016
Author Readman
Comments No Comments

Integer Break

找规律:

IntegerBreak_Clone
n	max
3	2*1
4	2*2
5	3*2
6	3*3
7	3*4
8	35=3(3*2)
9	333

public class Solution {
    public int integerBreak(int n) {
        if(n == 2)
            return 1;
        if(n == 3)
            return 2;
        if(n == 4)
            return 4;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 4;
        for(int i = 5; i <=n; i++) {
            dp[i] = 3*Math.max((i-3),dp[i-3]);
        }
        return dp[n];
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

public class Solution {

public int integerBreak(int n) {

if(n == 2)

return 1;

if(n == 3)

return 2;

if(n == 4)

return 4;

int[] dp = new int[n+1];

dp[0] = 0;

dp[1] = 1;

dp[2] = 1;

dp[3] = 2;

dp[4] = 4;

for(int i = 5; i <=n; i++) {

dp[i] = 3*Math.max((i-3),dp[i-3]);

}

return dp[n];

}

Date April 27, 2016
Author Readman
Comments No Comments

读[Seminal Ideas from 2007]

[读] Consistent Hashing with Bounded Loads

比如:

文章的背景:

解决方案:

2017年展望

Educational Codeforces Round 1 D. Igor In the Museum

Educational Codeforces Round 1 B. Queries on a String

[LintCode] Update Bits

Hilbert Curve 算法

Josephus problem 约瑟夫环问题

Quicksort for LinkList

Integer Break

书脊

倾城与倾国, 佳人难再得

Categories

Tags

Links

September 2017
M	T	W	T	F	S	S
« Aug
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30