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

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, 后来发现里面重复请求非常多真是!@#@!#!, 于是记录一下每次请求的结果. 原想是用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

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.

"Talk is cheap. Show me the code."
    - Linus Torvalds

1 2	"Talk is cheap. Show me the code." - Linus Torvalds

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

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

Date April 27, 2016
Author Readman
Comments No Comments

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

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

下面是code:

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

Date April 22, 2016
Author Readman
Comments No Comments

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

Teuvo Kohonen和他的SOM

Very Fast Reservoir Sampling by Erik Erlandson

书脊

倾城与倾国, 佳人难再得

Categories

Tags

Links

June 2017
M	T	W	T	F	S	S
« Jan
			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