我们经常听到这个说法——不要重复发明轮子,并对别人重复性的劳动表示不屑。这里其实混淆了两个概念,即学习和发明。对于学习来说,最好的方式就是自己造轮子。我们可以拿游泳作比方,你如果想学会游泳,首先应该去模仿别人怎么游,而不是自己发明泳姿。同样的道理也适用于Scheme实现,如果你想实现一个基本的Scheme,最好的方式是先去看看别人是怎么实现的。
SICP换零钱问题的线性迭代解法
SICP的1.2.2节里提到了一个换零钱的问题
给了半美元、四分之一美元、10美分、5美分和1美分的硬币,将1美元换成零钱,一共有多少种不同方式?
书里给了一个树形递归的解法,思路非常简单,把所有的换法分成两类,包含50美分的和不包含的。包含50美分的换法里,因为它至少包含一张50美分,所以它的换法就相当于用5种硬币兑换剩下的50美分的换法;不包含50美分的,只能用4种硬币兑换1美元。这样用5种硬币兑换1美元就等价于用5种硬币兑换50美分的换法加上用前4种硬币兑换1美元的换法。以次类推,用4种硬币兑换1美元的换法就等价于用4种硬币兑换75美分的换法加上用3种硬币兑换1美元的换法。
假设用1种硬币求换法数量的函数是f(n),用2种的是g(n),3种的是h(n),4种的是i(n),5种的是j(n),那么
j(100) = j(50) + i(100)
j(50) = j(0) + i(50)
j(0) = 1 #有1种兑法兑换0元,那就是一个硬币都没有
i(100) = i(75) + h(100)
i(75) = i(50) + h(75)
i(50) = i(25) + h(50)
i(25) = i(0) + h(25)
i(0) = 1
程序如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
这个算法非常的简单,但是它的效率很低,有大量的重复计算,比如i(50),它的时间复杂度是指数级的,在我的电脑上(2.2GHz i7)计算500块就需要15秒了,根本不实用。书中给读者留了一个挑战,找出线性迭代的解法。这是个难的问题,我在Stackoverflow上找到了一点思路,用动态规划的方法从0到100“推”出结果。这个算法的核心思想跟之前的递归其实是一样的,只不过是反过来推,先算出f(1)到f(100)(都是1),将所有的结果保存到一个数组里,再算g(1)到g(100),保存到另一个数组里,因为计算g(n)所需要的数据g(n-5)和f(n)都已经准备好了,这样就可以避免重复的计算。接着再算h(1)到h(100),i(1)到i(100),最后是j(1)到j(100)。程序如下
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 |
|
这种解法只需要循环5遍就可以得到结果,所以它的时间复杂度是O(n),比书中的例子快多了。但是因为它至少需要保存两个长度为n的数组,所以它的空间复杂度也是O(n),还不能算是线性迭代的解法,因为它要求空间复杂度是O(1)。 我们再仔细观察下这个动态规划的过程,可以发现,当我们从1推到100的过程中,有很多值是没必要存储的。
j(100)=j(50)+i(100)
j(50)=j(0)+i(50)
j(0)=1
i(100)=i(75)+h(100)
i(75)=i(50)+h(75)
i(50)=i(25)+h(50)
i(25)=i(0)+h(25)
i(0)=1
对于j(100),我们只需要存储j(50),j(25)和j(0) 对于i(100),我们只需要存储i(75),i(50),i(25)和i(0) 对于h(100),我们只需要存储h(90),h(80),h(70),h(60),…,h(10),h(0),但是为了辅助i(75),我们还需要多存h(75),h(65),…,h(5) 对于g(100),我们只需要存储g(95),g(90)直到g(5),g(0)
如果我们改变下循环的次序,先计算f(0)到j(0),再计算f(5)到j(5),接着是f(10)到j(10),最后f(100)到j(100),这样就可以节省很多不必要的空间。当我们计算j(100)时,j(25)对我们来说已经没有意义了,我们只需要知道j(50)就够了,计算i(100)时,只用i(75)也就够了,所以对于每一个函数,都只用保存一个值。但一个值其实是不够的,我们可以从h(0)推到h(10)再推到h(100),但是没法从h(0)推到h(75),只能从h(5)开始推起,所以对于函数h,我们需要保存两个值,一个用于推出h(100),一个用于推出h(75)。为什么i不需要保存两个值呢,因为50是25的整数倍,所以当我们推导i的时候,会自动包含h所需要的值,而25并不是10的整数倍,所以需要为其单独保存一个值。这里不管是哪个函数我们都是从0开始推的,因为0是100除以所有硬币的余数,当我们要算99块钱的兑法时,就不能从0开始了,对于j,我们需要知道j(49),对于i,我们则需要知道i(24),而对于h,则需要h(9)和h(4)了,h(4)怎么算出来的呢,(99-25)%10。所以对于每一个函数,我们只需要保存最多两个值就够了,一个推出f(n),一个推出f(n-V),这里的V是下一种硬币的面值。
我用两个长度为硬币种数的数组来保存计算结果,一个是用来保存f(n)到j(n)的counts,一个是用来保存f(n-Vg)到i(n-Vj)的counts-alt。
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 |
|
cc是主函数,有两层循环,外层循环从0到100,内层循环从1美分到50美分,对于每一个index,都计算一次包含当前coinIndex的情况下,有多少种换法,由counts或counts-alt里已计算好的值来得出。
append-count是一个辅助函数,用来更新数组,当index超出数组长度时,自动补零。
cal-count计算f(n)到j(n)的counts,cal-count-alt计算f(n-Vg)到i(n-Vj)的counts-alt。这两个函数的逻辑基本上一样的,只是计算新值的条件不同。在index从0涨到100的过程中,假设coinIndex为3,即10美分,只有当index除以10的余数和100除以10的余数相同时,才会计算新的counts,否则不用计算,因为h(20)=h(10)+g(20),h(11)到h(19)对我们来说都没意义。每次计算counts里某个coinIndex的值时,都是由现有的值加上一个counts或counts-alt里coinIndex-1的值,是counts还是counts-alt取决于余数的状态。计算counts-alt时,则是考虑当前coinIndex的值是否对coinIndex+1有用,也是通过余数来比较。
这个版本的算法空间上的需求是O(1),满足线形迭代的要求,在计算较大数目的时候不管是时间还是空间的优势都很明显,但是理解起来就比树形递归那个难多了。
我的Vim配置(三)
继续之前的Vim配置系列,这次我将介绍两个插件和PHP相关的配置
使用taglist来实现IDE中的outline功能
以前使用IDE时,有个很贴心的功能我很喜欢,就是把当前文件的类函数全部列出来,这样当你的函数很多时,能很方便的找到自己想要的,而不需要在代码里翻来翻去。taglist就是这样的一个插件,它使用ctags动态生成当前文件的tag并在一个新窗口里显示出来,你只需点击这个窗口里的函数名,就能快速定位到某个函数的开始位置,非常好用。安装也很简单,跟以前一样将这个插件放到bundle目录下,就能使用了。因为我主要使用MacVim,所以我添加了以下配置信息到.gimvrc里,使用起来更加方便。
1 2 3 4 |
|
使用snipMate减少你的敲代码字数
对于程序员来说,snipMate可是不可或缺的利器,它可以帮你自动完成一些代码片段,省去你不少敲击代码的时间,尤其是当你手动编辑html标签时,会觉得如释重负!比如当你输入div再按下tab键,一个完整的div标签就输入完整了,不需要一堆尖括号反斜杠等等重复烦人的输入,而且光标还会自动停留在id上等你来修改! snipMate支持几乎所有主流语言,PHP,HTML自然不在话下,你可以放心使用!使用这个插件注意要在.vimrc中加入以下这行
1
|
|
让Vim能检查PHP语法错误
Vim默认带了PHP的语法高亮,但这还不够,它不如IDE那样能帮你自动检测语法错误,但要实现这功能也不难,在.vimrc文件里添加以下配置,就能使用CTRL-L键来检查语法,如果有错误,它会告诉你在哪一行。注意你的PHP路径可能和我的不一样。
1
|
|
让taglist能正确显示PHP的类函数
当使用taglist时,我发现它不能很好的支持PHP文件,每个方法和变量都显示了两次,在网上搜了下,发现这是ctags的问题,添加以下配置到.ctags文件,就能解决,注意这个文件是ctags的配置,和Vim没有关系。
1 2 3 4 5 6 7 8 |
|
让snipMate识别模版文件
snipMate会自动根据文件名的后缀来判断文件类型,但是我使用的cakephp框架里有自定义的.ctp模版文件,我需要它能同时支持html和php的snip,节省我敲代码的数量。很简单,在.vimrc中添加以下配置,将.ctp文件的类型同时设为php和html就可以了
1
|
|
我已经更新了github,并把之前的.ctags文件也加了进来,去看看吧 :)
我的Vim配置(二)
上次讲了一些Vim的基本配置,这次我将介绍三个必装的Vim插件
使用pathogen来管理你的插件
安装vim插件是件很麻烦的事情,首先要把*.vim文件放到plugin目录里,其次要把文档放到doc目录里,而很多插件还自带了一些文件和目录,久而久之,.vim文件夹就显得臃肿不堪了,你都不知道哪个文件是属于哪个插件的!pathogen就是一个专门对付这种问题的插件。装了此插件后,你其他所有的插件都可以放到.vim/bundle目录下,每个插件对应的是一个单独的目录,这样插件自带的文件就不会混在一起,管理起来就轻松多了! pathogen的安装我就不多说了,链接里介绍的很清楚。
NERDTree
NERDTree是我装过的第一个插件,它可以在vim里显示目录和文件的结构,类似IDE里的Navigator功能,方便你找到文件,非常好用,安装也很简单,参照链接里的指示就行了。不过我建议你安装Github里的最新版本,命令如下
1
|
|
它将nerdtree的git repository作为一个子项目下载到bundle目录里,并可以通过以下命令更新
1
|
|
这样你就可以方便的更新你的vim插件,并同时管理好你自己的vim配置了! 此外,NERDTree的书签功能是我的最爱,我将常用的几个项目地址设为书签,这样就可以很方便的在不同项目间导航! 为了更方便的使用,你可能还需要下面3行配置
1 2 3 |
|
因为我使用的是MacVim,所以我将以上三行放到了.gvimrc里。放在.vimrc里的话,NERDTree会占用很大的空间,而通常终端窗口都很小,所以不推荐。
Command-T
Command-T是一个比NERDTree更好用的插件!使用NERDTree打开文件你还需要从目录树里层层打开文件夹,找到文件再按o打开,使用Command-T,你只需要输几个简单的字符,它就能帮你定位到pwd目录下最匹配的那个文件!类似你在使用google搜索时,下面实时反馈的搜索建议。具体演示可看链接里的第一个视频,非常强大! 然而使用Command-T有一个条件,就是你的vim得支持ruby,通常原生的vim是不带这个这个功能的,不过MacVim没有这个问题,大可以直接安装这个插件。Command-T的安装过程比NERDTree稍微复杂点,需要编译,不过这个文档说得也很清楚了,注意第四节,使用pathogen。 安装好了后就可以直接使用了,添加以下两个快捷键可以让你用的更加顺手!
1 2 |
|
Github
我将我的vim配置上传到github上了,感兴趣的可以去看看 :)
我的Vim配置(一)
使用vim开发有一段时间了,经常会做些配置装些插件,导致.vimrc变得臃肿不堪,.vim文件夹也很混乱,很多配置和插件自己都忘了有什么用处,所以今天打算好好整理下,写篇博客做下总结,因为要配置的东西很多,所以我计划分成几篇来写。
使用Git来管理vim配置,并使用Dropbox备份
因为vim的配置很多很乱,时间长了难免忘记,所以我打算用版本控制工具来管理,为了避免误删文件夹,我打算用dropbox来将vim配置备份。vim的配置有三部分,.vimrc文件,.gvimrc文件,.vim文件夹,我将他们都设为软连接,指向~/Work/Tools/Vim文件夹下,再将Vim文件夹使用Git来管理(Git是我最爱用的版本控制工具)。再用Dropbox把这个文件夹云备份,这样我就可以高枕无忧的使用vim啦!
程序员通用的配置
下面我就介绍一些vim的基本配置,这些配置不管你是写什么语言的都会用到
1 2 3 4 5 6 7 8 9 10 |
|
以上就是一些程序员常用的基本配置,我会在后续的博客中介绍更多的配置和插件。
为什么要使用正版软件
今天我将Mac上的盗版软件全部卸载了,决定从此只用正版软件。为什么呢?
首先,正版软件其实很便宜
在Mac App Store里的大多数软件都只要几美元,而像Keynote这样的“大”软件也只要20美元,折合成人民币也就一百出头,两个人在海底捞随便吃一顿就不止这个数了,但是海底捞满足的只是一时口快,而好的软件则可以用一辈子。我的iPhone一直没有越狱,因为那些1美元的软件实在是不贵,麦当劳吃顿早餐还要6块呢,但是越狱带来的麻烦则更多。
其次,正版让你的软件更强大
现在是网络时代,所有的软件几乎都需要通过网络来自动更新,以解决bug或增加功能,正版能让你的软件自由的更新,保持最新最稳定的状态,而盗版则不可能,因为你没法通过搜来的密钥绕过服务器的验证。而像iPhone这样的设备,ios和app的更新更加频繁,越狱的机器是无法自如的更新的。
最后,你的时间更加值钱
也许你觉得软件的自由更新无所谓,你总是可以通过搜索引擎找到破解的办法来安装新的版本,但是你有没有注意到你为此付出的成本?为了让你的盗版软件能正常工作,你也许要花几个小时甚至一下午的时间来折腾,你的时间全浪费在这些一点小钱就可以解决的问题上面了。技术的每一次创新都是让你的劳力得到更多的释放,好腾出时间来做更多更重要的事情。而你的行为恰恰和人类进步的主旨相反。
关于Linux有人曾说过,”Linux is only free when your time is cheap”,这样的道理也同样适用于你的盗版软件。
Cakephp、yii、kohana性能比较
周末闲来无事,测了下三个php框架的性能,图表如下
framework | reqs | reqs with apc | |
---|---|---|---|
cake 1.3.11 | 12569.8 | 32786 | |
yii 1.1.8 | 24382.6 | 115272 | |
kohana 3.2.0 | 23275.2 | 32784.4 |
我的测试方法是ab -t 60 -c 10 url,测试页面是输出一个hello world,没有任何附加的组件,纯粹比较框架的自身开销。 当不开启apc时,cake的性能较差,60s内平均完成12569.8次请求,只有yii和kohana的一半,开启apc后,cake的性能和kohana一样了,提升较kohana明显,但是yii却达到了恐怖的115272次,将近5倍,我很好奇它是怎么实现的。
编程不是绣花
编程不是绣花,没必要做到完美。
程序员很容易有洁癖,觉得不“正统”,不“完美”的解决方案是不能接受的,所以喜欢跟一个问题死磕到底,不找出一个百分百另自己满意的解决方案不肯罢休。最后往往把自己搞的筋疲力尽,耽误了进度,而最完美的方案却依然没有找到,不得不采用不那么“完美”但可行的方案,让自己沮丧。
其实解决问题最好的方法是绕过那个问题,没必要跟它死磕。当找不到更好地解决方案时,先将问题封装起来,继续推进,等以后有空了再来优化。
没必要死磕还有一个原因,那就是这个问题可能会因为功能的变动而消失,那么,当初苦苦找寻的“最佳方案”岂不是白费力气?
昨天在做一个Facebook应用时,发现官方提供的API不能实现我想要的效果,虽然我马上通过Google找到了答案,但我不信Facebook的文档会有问题,肯定是自己哪里看漏了,所以我不肯罢休,一定要找出“官方”的解决方案。结果耗费了一下午的时间,最后到下班也没达成心愿,不得不接受之前通过Google找到的答案,很是沮丧,有感而发,便有了这篇日志。
Cakephp优化总结
对于网站来说,响应速度是一件非常重要的事情,虽然打开一个页面的80%的时间是耗费在网络传输上,服务器本身的响应速度也不容忽视,当服务器负载上升后,响应速度直接影响到了服务器的吞吐率。假设一个PHP脚本的平均执行时间是100毫秒,那么在只有一个CPU的服务器上,每秒钟最多也就能响应10次请求,如果代码写的不好,执行时间需要500毫秒,那么服务器每秒钟则只能响应2个请求。
减少代码的执行时间,关键在于减少重复的操作,尽可能的利用缓存。下面我便介绍一下我在使用cakephp这个开源框架中总结的优化经验。
将索引文件缓存到memcached
当开启缓存后,cakephp会建立一个文件和目录的索引,大幅降低加载Component和Model的时间。这些索引通常是保存在app/tmp/cache/persistent目录下的,但是当你使用memcached来作为默认缓存引擎时,这些文件则无法缓存,索引则不能保存下来,这丝毫不能降低加载代码的时间。解决的办法其实很简单,在core.php下,定义一个名为’_cake_core_’的缓存配置,如下
1 2 3 4 5 6 7 |
|
这样,这些文件就能成功被缓存。
将数据库表结构缓存
原理同上面的文件索引一样,cakephp可以把数据库的表结构缓存起来,免去重复读取和处理表结构的操作,当开启memcached的时候,这些缓存也不能直接缓存,需要定义以下规则
1 2 3 4 5 6 7 |
|
将Controller需要加载的Model序列化
在MVC框架中,Controller的定位是处理请求并返回操作结果,具体的业务逻辑则交给Model来做,这样Controller在处理请求的过程中,通常会加载很多Model,与其每次都重复引入文件,解析类,再生成对象,不如将这些常用的Model序列化成字符串保存起来,需要时再反序列化成对象,可以直接使用,节省大量的加载时间。这样做有一个前提,那就是在反序列化的过程中,类的构造函数__construct不会被执行,所以写代码时要注意不要在构造函数里保存状态。实现也很简单,在Controller里定义一个公共属性
1 2 |
|
我会在AppController里定义这个变量,这样所有的Controller都默认继承了这一优化。
代码更新时要即使清空缓存
使用以上这三个缓存技巧时,要注意每当有代码更新时,比如新加了一个Component,或者Model的代码有更新,或者数据库表的结构有变化时,要及时清理相应的缓存,不然会产生找不到文件或代码未更新的bug,具体做法是删除以下缓存
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 |
|
省去Model间的关联
上面解决的是减少加载时间的问题,下面介绍的是怎样省去不必要的加载。 当我们使用cakephp脚手架生成User和Group这两个Model时,会在User类加上这样一行代码
1 2 |
|
它的作用是在加载User这个Model时同时加载Group,这样能使得你能很方便的通过外键来访问其他Model,如果你的应用并不需要这一功能,那么你就可以将这行代码删除,换取更快的加载时间。
不使用Controller的默认加载
Controller有两个属性,$uses和$components,可以让你的Controller自动加载Model和Component,然而相较于Controller的loadModel方法,$uses的开销更大,而且当你的Action不需要默认的Model时,自动加载的Model也显得多余,成为负担,解决的办法是在Controller里定义$uses为空的数组
1 2 |
|
components原理同样,虽然Cookie,Session,Auth,Acl这几个Component是属于比较常用的,但是也不见得所有的Controller和Action都会使用到,所以明智的做法是在Controller的constructClasses()方法里再根据action选择性的引用,如
1 2 3 4 5 6 7 |
|
总结
总结以上的优化,关键就在于两点,缓存和减肥,将重复性的操作缓存起来,提高效率,将不必要的代码去掉,减少负担,通过以上的优化,我的服务器的平均响应时间已从350毫秒降到了50ms左右,减少了6倍!
使用grep和正则来分析Web服务器日志
前两天因为第三方游戏服务器掉线,导致大量用户同时登录我的服务器,将服务器负载瞬间提高到200+,如此恐怖的数字让我不得不考虑增加服务器来抵抗问题重现,然而我的服务器平时负载都很低,0.1都不到,增加服务器来应付这样短暂的风暴未免太过于浪费,于是我决定从日志下手,找到我的网站的瓶颈,希望能通过改善程序来解决这个问题。
第一步,定位时间
我的日志文件里包含了最近一个礼拜的数据,然而我需要的只是风暴发生时产生的数据,总共不超过20分钟,怎么取呢?因为我的Web服务器采用的是标准的combined格式
1 2 |
|
而且全部是PHP动态请求,所以我决定从time_local下手,找到并发访问量最高的时间段,这很容易办到:
1
|
|
得到如下结果(部分)
从18点43分开始,我的服务器每秒需要响应120多次动态请求,而18:46:49秒更加变态,211次!看来把我服务器拖垮的,就是18点43分到18点50分这一段。
第二步, 过滤脚本
定位好了时间,现在要做的,就是取出这一时间段的日志再做分析,使用以下脚本将18:43分到18:50分之间的日志取出来
1
|
|
第三步, 找出元凶
得到了storm.log,下面我便要找出拖垮我服务器的元凶,及访问数量最高的$request。因为$request都是 “GET /*** HTTP/1.1” 或 “POST /***” 这样的格式, 所以可以通过简单的正则取出$request,如下
1 2 |
|
(?<=GET\s)这个正则叫作零宽断言,是将要被匹配文字前面的条件,即除非前面有’GET ‘出现,后面的才匹配。 上面的脚本得到以下结果:
从这张图我们便可以找出程序方面的瓶颈了,因为上面这些请求大部分都是ajax请求,所以明显的,像’users/getuser’、’games/getservers/sxd’这样的数据请求完全可以被浏览器缓存起来,而’users/logoutService’根据我们的业务逻辑也显得毫无必要,将这三项请求砍掉能节省将近60%的资源! 以下便是通过优化程序代码后13号应对的又一次风暴结果。
看到没,’/users/getuser’请求减少了将近一半,而’/games/getserver/sxd’则减少了近75%,总量减少了近40%!然而’/users/logoutService’却不尽如人意,只少了三成,我们待会再寻找其原因。
通过以上程序的优化和一些系统配置的调整,这次风暴只将我的服务器负载升高到了10+,并在十几秒后就很快地平稳了下来,和前一天的200+相比,可以说成功地解决了短暂风暴的问题。
第四步,找出来源
上一步遗留了一个问题,即我明明优化了程序,去掉了不必要的’users/logoutService’,为何在风暴中,它依然出现了那么多次,所以我决定分析$http_referer,找出这些请求都是从哪来的。 根据日志的格式,$http_referer前面都有一个$body_bytes_sent、一个空格和一个双引号,例如
1 2 3 |
|
因为$body_bytes_sent始终是个数字,这样就可以通过以下正则来找出来源
1 2 |
|
先过滤出logout的日志,再通过零宽断言找出来源。得到的结果出乎我意料,来自于一个我在上一步中已经调整过的页面,明明去掉了不必要的’users/logoutService’请求,为何还会重复出现?仔细观察代码后并没发现可疑的地方,于是推测是CDN缓存的问题,这些用户用的JS版本可能还是前一天的,清理缓存,加上版本号,期待下次风暴来验证这一推论!