2012年5月25日星期五

flip遍历

问题
遍历长度为n的所有可能的0-1向量(N=2^n个),使得相邻输出的两个向量可以通过某一个下标取反得到。

算法1
O(N)时间,O(n)空间
n=4
l=[0]*n
def f(n):
if n<=0:return
n-=1
f(n)
l[n]=1-l[n]
print l
f(n)
f(4)
足够简洁,注意到递归的函数栈深度为n,所以空间复杂度为O(n)

算法2
O(N)时间,O(1)空间
n=4
l=[0]*n
print l
N=pow(2,n)
for step in xrange(1,N):
for p in xrange(1,n+1):
if step%pow(2,p)==pow(2,p-1):
l[p-1]=1-l[p-1]
print l
break
虽然两重循环,看似时间复杂度为O(nN),其实有内层循环有1/2的概率第一次if就break了,有1/4的概率第2次就break了,。。。有1/2^k的概率第k次就break了。
而级数sum{k/2^k}收敛,有上界,上界与n无关。故均摊内层循环时间为O(1),总时间就是O(N)了。

2012年5月12日星期六

新浪App Engine

1分钟点亮,不得不赞。
Google App Engine需要装SDK配yaml,AWS需要有git插件和信用卡绑定。
SAE最简单最符合国情:只需要SVN就能跑了!

2012年5月7日星期一

aws试用小记

有一天晚上,老婆说想弄个网站,搞基于数据分析的新闻调查。我觉得这个交叉学科的小项目很有意思,就开始忙活起来。
step 1 买域名
俗话说,名不正,言不顺。从国内某个从来没听说过的小破网站买了一个看起来很权威的域名www.data-journalist.com
step 2 买主机
国内的主机想都没想,调研了几家国外的VPS,好像都挺贵。于是想起了AWS。AWS已经火了好几年了,前几天和Diane聊天的时候,她提及想找人调研一下。正好我也想借data journalist这个小项目尝试一下传说中的"云计算",就冲向了AWS。注册、身份验证、关联信用卡,这一路没什么难的,新人貌似还有免费试用?
step 3 冒烟elasticbeanstalk
elasticbeanstalk用国内那些小破网站的话说就是一个"一键式建站服务",整合了AWS众多基础设施服务。什么IaaS啦PaaS啦神马的,都是浮云。先搞起再说!
按照官方在线教程get start点了点鼠标,很快搭建了一个php的小网站,程序是AWS自带的,大致内容是"恭喜您blabla"
然后从console里下载了这个示例程序的php代码,貌似入口是index.php
step 4 部署自己的程序
按照另一篇教程deploy下载了git,aws的git插件(有用的就一个shell脚本),稍加配置,然后把自己hack过的index.php给一键部署上去了git aws.push,相比于小时候玩的IIS和Apache,aws真的是太方便了。
console上有一个测试网址
点进去,work了!
step 5 绑定域名
不知道静态IP是啥,可能压根就没有吧。就先用CNAME凑合着吧,回头仔细研究。

P.S. 让人很伤心的是AWS貌似部分被墙了TT