Tag: 算法

Categories
读书有感

重学动态规划(dynamic programming)

这真的不是什么可以引以为豪的事情....我一直认为我是懂动态规划的，直到这两天重新看到动态规划的代码发现自己看不懂，然后恍然间意识到上次看懂都是7年前的事情了。google了一番搜到自己的blog真的是欲哭无泪，然后痛定思痛，觉得这次把它搞懂，重新写一篇笔记，这样万一若干年之后再回头看这个，至少保证这次的笔记有更多的含金量自己可以看懂。（更惭愧的是，高级宏观的时候天天在手动解动态规划，最多的就是无穷期动态规划，现在居然不怎么记得当年是怎么解的了...）

动态规划的用处还真多。很多例子都是斐波那次数列的，但是其实我感觉这样的例子并没有很明显的感觉。倒是今天看到一个文本排列的例子觉得很有意思，原来latex计算每行放多少词是用动态规划算的。想想word打字的时候也是不时会重排一下，所以大概也是在后面不停的算动态规划的最优结果吧。

动态规划的想法其实并不麻烦，大致就是一种以空间换时间的交换。今天耐着性子把youtube上mit公开课关于动态规划的两节看完了（19节和20节），顺便拿笔在旁边记了一堆笔记。然后找了两个例子用python练习了一番，又看了一下其他人的答案，开车回家的路上顺便又想了一下，这才觉得这次好像是想明白动态规划了。所以在这里记一下。

最短路径的动态规划解法

先来个简单的例子？路径问题好了。这个好像是最经典的动态规划例子了。我这里随便画了一个图（神器在此）。

Screen Shot 2016-02-10 at 9.35.00 PM

假设如同上图所示，我希望从A走到D，其中各条路径的长度已经标注在图上。那么最短的路径是哪条呢？

最笨的办法，我们可以把每条路径都列出来，一个一个走一遍呗。这里的可能性就是

  • A -> B1 -> C1 -> D： 3＋3+10 ＝ 16
  • A -> B1 -> C2 -> D：3+5+2 ＝ 10
  • A -> B2 -> C1 -> D：4+6+10 ＝ 20
  • A -> B2 -> C2 -> D：4+8+2=14

所以很显然，最短路径是第二条：A -> B1 -> C2 -> D。

那么如果问题再复杂一点呢？

Screen Shot 2016-02-10 at 9.42.49 PM这里我们还是可以继续采用笨办法，只是可能的路径多了一点：

  • A -> B1 -> C1 -> D1 -> E： 3＋3+10+6 ＝ 22
  • A -> B1 -> C1 -> D2 -> E： 3＋3+4+2 ＝ 12
  • A -> B1 -> C2 -> D1 -> E：3+5+2+6 ＝ 16
  • A -> B1 -> C2 -> D2 -> E：3+5+6+2＝ 16
  • A -> B2 -> C1 -> D1 -> E：4+6+10+6 ＝ 26
  • A -> B2 -> C1 -> D2 -> E：4+6+6+2 ＝ 18
  • A -> B2 -> C2 -> D1 -> E：4+8+2+6 = 8
  • A -> B2 -> C2 -> D2 -> E：4+8+6+2 = 20

所以很显然，第二条胜出。在这个过程中我们一共计算了8条路径、24次加法。有没有发现什么规律呢？我们其实有很多重复的计算：比如C1 -> D1 -> E我们计算了两遍。总结一下：

  • 不管我们是怎么走到C1的，从C1到最后终点E的最短路径一定是C1 -> D2 -> E，距离为6。同理，不管我们怎么走到C2的，从C2到E怎么走都是8的距离。
  • 这样，继续往前推，不管我们是怎么走到B1的，若是从B1到C1再到E，最短距离就是3+6＝ 9 （C1 -> D1 -> E）；若是从B1到C2再到E，最短距离就是5+8=13，所以从B1到E的最短距离就是9。同理，不管我们怎么到B2的，从B2到E的最短距离是 6+6<8+8，故为12。
  • 那么回到最初的起点，A到B1再到E，最短距离就是3+9=12；A到B2再到E，最短距离就是4+12=16。

所以在这个过程中，每一步其实我们只进行局部计算就好了，不需要把各种可能性都列出来。下面是我们在每一步可以排除的路径。

 

  • A -> B1 -> C1 -> D1 -> E：
  • A -> B1 -> C1 -> D2 -> E： 3＋3+4+2 ＝ 12
  • A -> B1 -> C2 -> D1 -> E：
  • A -> B1 -> C2 -> D2 -> E：
  • A -> B2 -> C1 -> D1 -> E：
  • A -> B2 -> C1 -> D2 -> E：4+6+6+2 ＝ 18
  • A -> B2 -> C2 -> D1 -> E：
  • A -> B2 -> C2 -> D2 -> E：

这就是动态规划的力量了：在我们这个例子中，我们可以倒推出来，给定某一步的各种可能性、后面的最优走法。然后这样每次前面的只需要对比怎么走下一步、后面的最优路径就已经计算好了。

这大概是我自己对动态规划最直观的理解了：每一步都是相对独立的，所以可以先不管前面的、针对后面的进行优化、然后慢慢往前推。因为只要到了某步、后面的结果其实并不取决于是怎么到当前步的。

斐波那次数列的动态规划解法

然后看一下最著名的斐波那次数列好了，就是那个著名的数兔子数列：第一年没有兔子，第二年一只兔子，第三年1一只兔子，第四年2只兔子，第五年3只兔子，第六年5只兔子...每次都是前两年的兔子的和。

这个例子是绝佳的演示为什么动态规划体现了用空间换时间。比如我们要算第10年几只兔子，然后上面已经算好了直到第6年的兔子。我们先来看一种最笨的算法。括号里面的数字是倒推出来写的。

第十年的兔子 ＝ 第八年的兔子（5＋5+3）＋第九年的兔子（5+5+3+5+3）

第九年的兔子 ＝ 第八年的兔子 （5＋5+3）＋ 第七年的兔子（5+3）

第八年的兔子 ＝ 第六年的兔子 （5）＋ 第七年的兔子 （5+3）

 

第七年的兔子 ＝ 第六年的兔子（5） ＋ 第五年的兔子（3）

.....

一直算下去的话，为了算第10年的兔子，我们要算7次加法。这个过程中可以看出来，除了第五年和第六年的兔子是已知的之外，我们算了两遍第七年的兔子、两遍第八年的兔子、一遍第九年的兔子，然后才算出来第十年的兔子，显然是重复计算。

那动态规划这里怎么用呢？很简单啊，算过的我们就存起来，然后下一次再问到就不用算了呗；没算过的就现算呗。同样，我们已知的是｛第一年，0｝，｛第二年，1｝，｛第三年，1｝，｛第四年，2｝，｛第五年，3｝，｛第六年，5｝。

所以这个过程就是：

  • 为了算第十年的，我需要知道第八年的和第九年的，然后这俩都要算。
  • 为了算第九年的，我需要知道第七年的和第八年的，然后这俩都要算。
  • 为了算第八年的，我需要知道第七年的和第六年的，然后第七年要算。
  • 为了算第七年的，我需要知道第六年的和第五年的，这俩都知道，所以第七年是8。
  • 这样，第八年的就是8+5=13。
  • 这样，第九年就是8+13 ＝ 21。
  • 这样，第十年就是，13+21=34。

于是，每一年我只算了一遍，算好了就存起来了，下次备用就好了。

于是有童鞋说，另外一种办法就是从头到尾算就好了嘛、一个一个往后算、到了第10年停就是了。其实这样从前往后和刚才倒推＋存储是一摸一样的计算过程、每一年只算了一遍。因为有存储的存在、动态规划会极大降低时间复杂度。不过显然最省内存的就是从头往后算了，因为我只需要记住n－1和n－2两年的兔子就可以了，不需要知道再往前的年份的。这又体现了一种相对独立的感觉：给定n－1和n－2，n跟n－3...等等就完全没关系了，想想这不就是类似时间序列中的AR(2)过程嘛！

<不过话说最高效的算法，还是通项公式吧，直接就出结果了。但那个就跟这里没关系了呢。>

强盗问题的动态规划解法

最后再来俩个比较好玩的问题吧。House Robber problem，直接复制一下别人的翻译：

你是一名专业强盗，计划沿着一条街打家劫舍。每间房屋都储存有一定数量的金钱，唯一能阻止你打劫的约束条件就是：由于房屋之间有安全系统相连，如果同一个晚上有两间相邻的房屋被闯入，它们就会自动联络警察，因此不可以打劫相邻的房屋。

给定一列非负整数，代表每间房屋的金钱数，计算出在不惊动警察的前提下一晚上最多可以打劫到的金钱数。

我们先来看一下简单的情况。

Screen Shot 2016-02-10 at 10.45.17 PM如图，这条街上一共有6栋房子，我们假设它们依次有1-6块钱。然后可行的打劫策略有：

  • 打劫1
    • 打劫3
      • 打劫5：  1+3+5=9
      • 打劫6： 1+3+6 ＝10
    • 打劫4
      • 打劫6： 1+4+6=11
  • 打劫2
    • 打劫4
      • 打劫6： 2+4+6 ＝ 12
    • 打劫5： 2+5 ＝ 7

所以简单计算可知，2，4，6是最佳打劫策略。在这个过程中有没有什么熟悉的感觉？比如，给定打劫4，最优的策略一定是打劫6；给定打劫3、最优的策略已经是打劫6。所以我们可以一步步倒推出来、给定某个点、往后最优策略是什么，然后往前慢慢比较前一步怎么走到这个点就可以了。其实无非就是另外一个最短（长）路径问题。

那大致思路就是：已知第i步最优策略，那么只需要比较从i-2走过来和i-3走过来哪个更优就可以了。而我们又知道，这个过程可以借助存储表来降低时间复杂度，而借助存储和从头到尾算又是等价的，所以如果采取从头到尾写的话，就是上面链接给出的代码了：

状态转移方程：

dp[i] = max(dp[i - 1], dp[i - 2] + num[i - 1])

其中，dp[i]表示打劫到第i间房屋时累计取得的金钱最大值。

时间复杂度O(n)，空间复杂度O(n)

直白的讲，就是第i步的累积最大值是比较 第i－1步的累积最大值（此时不打劫i） 和 第i-2步累积最大值＋第i步金钱（此时打劫i）。

类似的还有一个好玩的问题：

如果这些房子是相互连城圈的，就是第1间和最后一间连在一起，那么就不能同时打劫第1间和最后一间了，此时的最优策略是什么？

答案无非就是，把一个list分别去掉头保留尾、去掉尾保留头，然后分别算一遍动态规划，看看哪个是最优的就可以了。

今天就写到这里吧，希望日后回头看自己还能看得懂...

Categories
读书有感

继续抄笔记——KMP算法

在今天以前我也不知道有个大名鼎鼎的KMP算法，也是偶然看到的。KMP算法解决的是文本匹配的问题，比如我要在字符串“今天天气特别好”里面找到“特别”的位置（对应第5-6位），或者简单如我在word里面点击“查找”，然后搜索一个关键词。一般来说，如果是编程中为了解决这种问题，我就特别习惯的去写正则表达式了...从没想过正则表达式后面他们到底会怎么算。当然直到此刻我也不知道正则表达式会不会调用KMP算法。

在上面那个例子中，只要我慢慢从左到右一个个对比“今天天气特别好”和“特别”就很容易找到“特别”的位置，无非就是到第5位的时候发现“特”是匹配上的，然后对比一下第6位是不是一样。但是如果前面那句话变成了“今天特热，但天气特别好”，按照上面的算法，我就会在第三位发现“特”是匹配上的，但是第四位没有匹配到，于是我又开始从第四位开始重新一个个看、什么时候可以依次匹配到“特”和“别”。

这大概是最直观的算法了，写起来也并不麻烦。就是有点暴力的感觉：穷尽所有的可能、总能找得到是不是。

当查找的字符串简单如“特别”的时候，确实用不用kmp算法不会有任何区别。可是有的时候我们要查找的字符串比较长，那这样的暴力算法就有点浪费了——因为可能已经做过一些比较了。

举个例子。我现在想在“今天天气很好，街上人来人往好不热闹，我们一起出去玩好不好”这句话中寻找“好不好”。那么第一个“好”出现在“今天天气很好”，然后发现嗯，下面一个是逗号，所以继续从逗号开始找下一个“好”；然后找到“好不热闹”，发现“好不”都被匹配到了，但是最后一个“好”没有匹配到，所以我们还得继续找。那么这时候是应该直接跳到哪里呢？“闹”、“热闹”呢，还是“不热闹”这里开始比较？显然看我们要寻找的字符串，“好不好”的第一位和第三位是一样的，然后第二位和他们俩都不一样，所以我们其实知道在“好不热闹”这个局部中，第二位的“不”不可能和“好”匹配，第三位的“热”也不可能和“好”匹配，所以我们可以直接跳到第四位“闹”。

这大概就是kmp的基本直觉了：先看一下我要搜寻的这个东西自己是不是有一定的模式，算一张局部匹配表（Partial Match Table），然后按照这个表就可以知道当每次前面部分匹配、而后面不匹配的时候，可以直接跳过几个格子往下走。(至于这个表格怎么算的，还是有点麻烦的....）

我是看这个解释看懂的：

http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

然后matrix67也有一篇有点历史的文章来解释这个：http://www.matrix67.com/blog/archives/115

 

Categories
读书有感

抄抄笔记——格雷码

想起来差不多十年前从图书馆里面一本又一本的借出来各种算法和数据结构的书籍，却从来没读完过...

今天看到一个东西，格雷码。看了半天硬是没怎么看懂（除了第一种递归的办法）...一看到二进制我就懵掉了，脑子里面一点线索都没有的悲催感。想想这块儿的知识应该也会挺有意思的吧？什么二叉树啊，红黑树啊，好像我都完全不了解是怎么个玩法。唉。

抄一点百度百科的笔记。争取过段时间再来看，能多看懂一些...现在脑子里面完全没有一点感觉。

递归生成码表

这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：
  1. 1位格雷码有两个码字
  2. (n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0
  3. (n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1[3] 
2位格雷码 3位格雷码 4位格雷码 4位自然二进制码
00
01
11
10
000
001
011
010
110
111
101
100
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

异或转换

二进制码→格雷码（编码）：
此方法从对应的n位二进制码字中直接得到n位格雷码码字，步骤如下：
  1. 对n位二进制的码字，从右到左，以0到n-1编号
  2. 如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）[3] 
公式表示：

（G：格雷码，B：二进制码）

例如：二进制码0101，为4位数，所以其所转为之格雷码也必为4位数，因此可取转成之二进位码第五位为0，即0 b3 b2 b1 b0。
0 xor 0=0，所以g3=0
0 xor 1=1，所以g2=1
1 xor 0=1，所以g1=1
0 xor 1=1，所以g0=1
因此所转换为之格雷码为0111
格雷码→二进制码（解码）：
从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。
公式表示：

（G：格雷码，B：二进制码）

原码：p[n:0]；格雷码：c[n:0](n∈N）；编码：c=G(p）；解码：p=F(c）；
书写时按从左向右标号依次减小，即MSB->LSB，编解码也按此顺序进行
举例：
如果采集器器采到了格雷码：1010
就要将它变为自然二进制：
0 与第四位 1 进行异或结果为 1
上面结果1与第三位0异或结果为 1
上面结果1与第二位1异或结果为 0
上面结果0与第一位0异或结果为 0
因此最终结果为：1100 这就是二进制码即十进制 12
当然人看时只需对照表1一下子就知道是12
...................c[n]=p[n]，
解码：

利用卡诺图

利用卡诺图相邻两格只有一位变化以及卡诺图的变量取值以低阶格雷码的顺序排布的特征，可以递归得到高阶格雷码。由于此方法相对繁琐，使用较少。生成格雷码的步骤如下：
  1. 将卡诺图变量分为两组，变量数目相近（最好相等）
  2. 以逻辑变量高位在左低位在右建立卡诺图
  3. 从卡诺图的左上角以之字形到右上角最后到左下角遍历卡诺图，依次经过格子的变量取值即为典型格雷码的顺序
三位格雷码（三位格雷码由建立在二位基础上）
AB╲ C
0
1
00
0→
1↓
01
↓2
←3
11
6→
7↓
10
4
←5
格雷码次序：000起点→001→011→010→110→111→101→100终点
四位格雷码
AB╲CD
00
01
11
10
00
0→
1→
3→
2↓
01
↓4
←5
←7
←6
11
12→
13→
15→
14↓
10
8
←9
←11
←10
格雷码次序：0000起点→0001→0011→0010→0110→0111→0101→0100→1100→1101→
1111→1110→1010→1011→1001→1000终点

使用异或乘除

用异或代替加减进行二进制竖式乘除，称为异或乘除，它的特点是无进退位。
如：10101除以11将变成1100余1。
二进制转格雷码：
只要异或乘以二分之三，即二进制的1.1，然后忽略小数部分；也可以理解成异或乘以三（即11），再右移一位。
格雷码转二进制：
异或除以三分之二，即除以1.1，忽略余数；或者左移一位，再异或除以三，忽略余数。
Categories
读书有感

python小试

今天非常无聊的决定去试一下python。找了一个题，大意如下：

  • 给定一个输入字符串，找出最漂亮的无重复子字符串。
  • 子字符串：从原字符串中减掉某些字符可得到的。
  • 无重复字符串：没有重复的字符
  • 甲比乙漂亮：甲的长度>乙，或者甲的字典排序在乙之后。

因为都是无重复的，所以肯定不需要甲的长度大于乙，故而是所有长度一样的无重复子字符串中，找出字典排序最大的。

这个先用R写的，为的是写出一个有效的算法来。基本的思路就是强行的逐层递归。

x = 'nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle'

x_split = strsplit(x,split="")[[1]]
unique_x = unique(x_split) 
unique_x_order = sort(unique_x,decreasing=T) 
x_remain = character() 

# find the largest character than can be remained

#initialize
current_string = x_split
current_unique = unique_x
current_order = unique_x_order
while ( length(x_remain) < 20) 
{ 
  for(i in 1:length(current_order))
  { character = current_order[i]
    index = which(current_string == character)
    sub_string = current_string[min(index):length(current_string)]  
    if (length(setdiff(unique(current_string),unique(sub_string)))==0) #no lose of characters
    {x_remain = c(x_remain,character);
     current_string = current_string[-c(1:min(index),index)];
     current_unique = unique(current_string);
     current_order = sort(current_unique,decreasing=T);
     break;
    }
  }
}

#answer is 'tsocrpkijgdqnbafhmle'

后面用python重写了一遍。基本就是等价函数的替换...我是不是在暴殄天物的利用python？完全不理解program on the fly的感觉...

x = 'nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle';
x_split = list(x);
unique_x = list(set(x_split));
unique_x.sort(reverse=True)
x_remain = list();
###initialize
current_string = x_split;current_unique = unique_x;current_order = unique_x;
while len(x_remain) < len(unique_x):
	for character in current_order:
		index = current_string.index(character);
		sub_string = current_string[index:len(current_string)];
		#print(character);
		if (len(set(current_string)-set(sub_string))==0): #no lose of characters
			x_remain.append(character);
			for i in range(sub_string.count(character)):
				sub_string.remove(character);
			current_string= sub_string;
			current_unique = list(set(current_string));
			current_unique.sort(reverse=True);
			current_order = current_unique;
			break;
print(x_remain);

最后好不容易写完python之后，发现网断了...没法在线提交了。等重新连上，时间已经过了，sigh。就当周末无聊历练一下了。

Categories
读书有感

papers I read in eBay

只是罗列一些这一两年比较关注的具体领域。

  • 自然语言处理与分词：看了很多分词类的算法，从字符匹配、MMSeg、HMM，到条件随机场之类。主要是为了提取关键词作为regressors。当然做这个一方面是好玩（周围很多朋友都在玩），另一方面也是不想被专家忽悠...嗯。另外就是TD-IDF、余弦相似度这些纯粹是为了不被忽悠。
  • 稀疏矩阵：稀疏矩阵完全是从上面继承而来的，往往分词之后搞来一个很大很稀疏的矩阵，为了降低computational cost或者干脆就是考虑到computational capacity，这个不得不做，然后就可以开始奇异值分解了。后面恍然发现，这丫不就是adjancy list和matrix的区别么...顿时为自己的智商隐隐担忧。
  • 近似计算方法：主要是binning methods，起因是觉得teradata算variance比较慢，所以看了一下能不能先binning再算variance以节省计算时间（说白了就是在teradata现有的map-reduce上想个更好的办法）。实用主义嘛。最后的感想就是，其实对于variance这种linear method，分布式已经蛮成熟了，在每一个map步能降低的computational time还是有限的...
  • 异常点识别：这个主要是有段时间在研究怎么可以有效的去掉outlier，不让这些点干扰计算（尤其是涉及均值的）。当然基本的就是基于ranking，后面发现这东西水还蛮深的，牵扯到distance measurement，stratified sampling等等。
  • 分布式计算：有段时间想了解一下Hadoop map reduce，所以去看了一些基本的分布式计算的东西。好吧，其实我还是觉得hadoop接口不够那么人性化，基于java的东西我还一时半会儿搞不定（从伪代码到代码到命令调度及debug还有好长的路要走...）。
  • 实验设计：这个貌似一直都在断断续续的看一些文章，从基本的随机试验的思想到后面各种具体环节的实现，以及不理想状况下的一些修正（比如连续实验、网络中实验、spillover effects等）。最近在试图利用RDD来改善一些现有实验设计和评估，此外不时瞅一下有没有好玩的网络实验的机会。（对eBay 3.0无限期待中...）
  • 贝叶斯网络：从MCMC开始的吧，陆陆续续看了好多马尔可夫网络和贝叶斯网络的东西，什么Belief Propagation。当然这里面也包括了Conditional Random Field这些语音识别、图像识别的基本原理和常用方法什么的。这也有种不被专家忽悠的想法，毕竟看来看去也就是这几种常见的算法的不同应用嘛。（修PGM那门课真的可以列作年度噩梦之一了...）
  • 拍卖设计：这个完全是由于随便搜搜eBay基本上都牵扯到auction design，所以顺带看一下...总的大趋势还是排名在向一口价转变，多少也有种一手市场快速增长的感觉。哎，consumer theory大爱的东西啊。
  • 社群识别：最近遇到一些这方面的挑战...一方面是clustering，另一方面是sparcification。总的感觉是，无论是稀疏矩阵还是矩阵稀疏化，都是去除噪音找到有用信号的过程...
  • 协同过滤：其实collaborative filtering是很久以前看的了，当时工作需要（印象最深的就是IBM的三篇笔记）...现在感觉看过这类方法的好处就是，很多问题越来越能和后面接触到的直觉相契合，感觉很多具体的算法和想法实践都是在这个框架之下或简或繁的变化，万变难离其宗嗯。

总而言之，我觉得我越来越不像一个学经济学的孩子...可怜。好吧，这些最多算是紧跟潮流吧，很多东西回头看看也没觉得多有意思。

被一份工作逼到如此程度也算是奇葩了...哎。最近的感觉就是，我还是去关注一下business side的一些趋势吧，多看一些new business models，毕竟这才是真正创造出来价值的。