页面载入中..

回到页首回到页尾

Quick Sort

momo @ 2014.08.26 [ Development ]

快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3)从j开始向前搜索,即由后开始向前搜索(j–),找到第一个小于key的值A[j],将A[j]和A[i]互换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

原理:

代码示例(PHP):


Javascript 闭包

momo @ 2014.07.21 [ Development ]

闭包(Closure)的官方解释晦涩难懂,他是这么说的:

「闭包」,是指拥有多个变量和绑定了这些变量的环境的表达式(通常是一个函数),因而这些变量也是该表达式的一部分。

不拿代码举例的话,谁知道这说的是个什么玩意儿?直到我看到了如下说明:

闭包是个函数,而它「记住了周围发生了什么」。表现为由「一个函数」体中定义了「另个函数」。

这样说似乎还是不大容易理解,于是 MDN 写了这个例子(demo):

然后我们发现其实改成这样也是可以的(demo):

这个时候 func 是一个闭包,由返回的匿名函数函数和闭包创建时存在的 “Mozilla” 字符串形成。然后我们再来加点料(demo):

上述例子中会依次弹出「mozilla makes firefox」、「google makes chrome」、「apple makes safari」,new 了一个 class 的既视感有木有?

使用闭包还可以模拟私有属性和方法(demo):

这样做了以后就只有使用 setter 和 getter 才可以访问自己模拟的私有方法或属性了。

在循环中创建闭包时容易发生多个闭包共用最后一次循环时产生的数据这样的错误,MDN 给出的方案是使用更多的闭包(错误正确):

更复杂的例子

不过说了很多,其实最后发现「闭包」着实是一个比较蛋疼的技术,如果你只是常规的页面交互使用概率还是比较小的,关于此,MDN 如是说

如果不是因为某些特殊任务而需要闭包,在没有必要的情况下,在其它函数中创建函数是不明智的,因为闭包对脚本性能具有负面影响,包括处理速度和内存消耗。
例如,在创建新的对象或者类时,方法通常应该关联于对象的原型,而不是定义到对象的构造器中。原因是这将导致每次构造器被调用,方法都会被重新赋值一次(也就是说,为每一个对象的创建)。

参考资料:
Secrets of JavaScript Closures
闭包 – MDN


转载:下里巴症候群

momo @ 2014.07.14 [ Fun ]

上星期的某一天晚上,我和一位朋友在西单附近吃饭。席间我们高谈阔论,指点江山,臧否人物,言必及王小波、余杰、村上春树、奥尔罕·帕慕克,聊的十分尽兴。大约到了9点多,我们方才起身结帐,各自回家。我踏上地铁之前,忽然看到一处还没收摊的报刊亭,就走了过去。从西单到四惠东大约11站,全程要30多分钟,我必须得买点什么东西消遣。

我的视线从《科学美国人》扫到《译林》,然后又从《看电影》扫到《三联文化周刊》,来回溜达了五、六分钟仍旧游移不决,直到摊主不耐烦说要收摊了,我才催促自己下了决心,在摊子上抓了一本《读者》,匆匆离去。在地铁里,我捧着《读者》看的津津有味,全然不顾自己曾经一逮着机会就嘲讽这本杂志的种种劣行。《读者》杀时间很是不错,我在西单等地铁的时候翻开扉页寄语,在建国门看到中缝后的笑话栏目,然后四惠东地铁停稳的一瞬间,我刚好扫完封底的广告。

尽管我一下车就把《读者》顺手塞进垃圾筒内,扬长而去,但我必须得承认:我在刚才的30分钟过的很愉悦,那些小布尔乔亚式温情故事和心灵鸡汤让我发酵出一种中产阶级的微微醺意。

我上上星期去了一趟三联书店,用公司发的雅高卡买了许多一直想要但很贵的书,比如王鸣盛的《十七史商榷》、张岩的《审核古文<尚书>案》、杨宽的《中国古代都城制度史》、《百变小红帽-一则童话三百年的演变》,还有若干本“大家小书”系列的小册子。买新书是一件令人愉悦的事,尤其是买了这么多看起来既深沉又有内涵的文化书籍之后,感觉旁人注视自己的眼神都多了几分恭敬。我捧着这些书兴致勃勃地回到家里,把它们一本一本摆在书架上,心里盘算哪些书以后写东西用得着;哪些书以后吹牛用得着;哪些书可以增加自己的修为和学问。

盘算到一半的时候,腹中忽有触动,五谷轮回,山雨欲来。我的视线飞过这些崭新的内涵书,抽出一本机器猫,匆忙跑进厕所……

类似的事情其实经常发生。比如跑去看现代艺术画展,最后发现真正停留超过两分钟欣赏的,都是裸女主题油画;买来许多经典DVD,最后挑拣出来搁进影碟机的只有《恐怖星球》和《料理鼠王》,看到男主角居然是大厨古斯特的私生子时,还乱感动了一把;往PSP里灌了300多种历代典籍文献,然后只是一味玩《分裂细胞》——甚至当我前天偶尔在手机里下载了一款类似口袋妖怪的JAVA游戏以后,我连PSP都不玩了,每天在班车上和地铁里不停地按动手机键,就如同一位真正的无聊上班族。

我有一次看到《Little Britannia》里有个桥段:男主角之一跑去一家高级法国餐厅吃饭,对着白发苍苍的老侍应生说:“给我来份加大的麦辣汉堡。”这让我亲切莫名。

我把这个发现跟朋友们说,他们都纷纷表示自己也有类似的经历。有人拟定了全套瑜珈健身计划,然后周末在家里睡足两天;还有人买了精致的手动咖啡磨,然后摆在最醒目的位置,继续喝速溶伴侣。最后大家一起唉声叹气,试图要把这个发现上升到哲学高度,提炼出一点什么精神感悟,让自己上个层次什么的。

但是这个努力可耻地失败了,于是我们发现这是一种感染范围很广泛的疾病。

简单来说,下里巴症候群是这样一种病:我们会努力要作一个风雅的人、一个高尚的人,一个脱离了低级趣味的人,结果还是在最不经意的时候暴露出自己的俗人本质。我们试图跟着阳春白雪的调子高唱,脑子里想的却总是阳春面和白雪公主。

一般这种疾病分成两个阶段:第一个阶段是你发现了“超我”,折射到现实社会,就是你买了一台西电KS-16608L;第二个阶段是你发现了“本我”,每天晚上都用这玩意儿听《两只蝴蝶》。

其实仔细想想,这种疾病或者说生活状态很不错,一来可以满足自己的虚荣心;二来又不会真正让自己难受——要知道,让一个俗人去勉强风雅,比让一个风雅的人勉强去俗气更不容易,毕竟不是每个人都象郭沫若那样进退自如,能写出《凤凰涅磐》和《咒麻雀》来。

按照文法,在文章的结尾应该提纲挈领,但是刚才已经失败了,现在也不会有什么成功的可能。所以我还是以一个隽永温馨的哲理小故事作为结尾。

我有一个朋友R。有一次,我们一群人去看一部话剧。当时去的早了,话剧还没开演。百无聊赖之下,我们就跑到附近的一家书店闲逛。我偶尔瞥到其中一个书架上放着一些关于佛教的书,忽然下里巴症又发作,于是微皱眉头,用轻松安详的语气说恰好在旁边的A说:“最近俗务缠身,我忽然很想看看禅宗的精神,让自己的心空一下,也未尝不是件愉悦的事。”

Y没理我。我低头一看,R原来正蹲在地上,聚精会神地捧着从书架角落里拿出来的大书。

“你在看什么?”

A把书举了起来,我首先看到的是Y愉悦的表情,然后是封面硕大的字体:“慈禧美容秘籍。”

R的真诚和坦率就如同初春的阳光,我看到自己虚伪的面具惭愧地开始融化。心灵被震撼的我扔下了南怀瑾、南怀仁和慧能,毫无矫饰地抽出一本《奇侠杨小邪》。

我的内心学着《发条橙》结尾的阿历克斯,大声呐喊:“I was cured all right。”

真是个美好的故事。

via 马伯庸


亲历恐慌

momo @ 2014.06.19 [ 琐事 ]

2014年6月16日下午5点多,本人乘坐武汉轨道交通2号线从光谷广场前往金银潭的线路上,在即将到达宝通寺站时,经历了有生以来最心有余悸的一次集体恐慌事件。

当时并非上下班高峰,但不止为何车上还是不少的人(可能是因为学生即将放假去火车站的人比较多吧),由于我是起点站上车所以才有位置。

正用手机看新闻间,忽然后面的车厢有大群人快速的向我所在车厢涌来,并有人大喊「快跑」,夹杂着女性尖叫声。条件反射一样的我就站起来,手机还拿在手上,就往前面的车厢跑。

由于车厢有点抖动的感觉(不知道是因为车子在转弯,还是因为多人在涌动),第一感觉是这会不会是地铁撞车了?跑了一节车厢心说「这回老子不会交代在这儿了吧?」。

来不及细想,慌乱中询问后面的一个人,也说不知道,只有硬着头皮继续往前面车厢跑。往后一看,后面车厢往前面涌动的人越来越多了,让人有一种「僵尸世界大战(World War Z)」的既视感。

这时候有人说,不会是 XinJiang 人砍人吧?一股说不出的恐惧感油然而生,我仿佛看见了利刃从我喉间穿过的画面。话不多说,继续向前吧。话说平时加强体育锻炼关键时刻还是可以体现价值的,我的速度很快,并且很快的闪避了挡在我前面的人和各种前面的人丢弃的行李以及其他障碍物,尽量不与他人相撞减慢速度或者影响他人跑路。

途中看见有摔倒的人,可已经来不及去对他进行帮助了(这种时候还是保命要紧吧),也有抱着小孩跑路的,可以明显的发现大家并未因为急于跑路而与抱小孩的人挤在一起,以至于他们跑路的速度还挺快。这算是整个恐慌中难得的让人欣慰的事情吧。

等我跑到了所有车厢的最前面时,发现一个现实的问题,车还没停。车里的人焦灼了,气氛有些紧张,旁边一个女人带着哭腔喊道「快把门打开让我们出去吧!求求你们了!」。这时候广播响起「即将到达宝通寺站」,从经验来看车门应该会在1分钟左右打开的,这是这么多年来最难熬的1分钟吧,气氛有些沉闷,大家都不自觉的向车厢出口处靠拢。

站到门开,出门的秩序比我想象中要好得多,并没有出现过于拥挤的现象。检票管卡是跳过去的(我不知道自己为什么要如此,可能是因为前面的几个人也是这样吧)。上楼梯我速度也很快,旁人有些讶异,我出于善意的对询问的人说「快跑」。

终于出了地铁站,看见外面秩序井然我依旧没有松懈。第一感觉是最自己的生存能力表示满意,整个车厢这么多人,我应该是前十个跑出来的。

走到路边拦的士被一个号称病人的家伙抢了(心说积点德吧,咱就发扬风格)。在外面站了约莫10分钟的样子,警车到了,果然只有国家暴力机器的到位才能在这种情况下给人一点安全感啊。

由于此时我需要办一件急事去汉口,而来过武汉的朋友都知道,此时从宝通寺从马路上过江的话,没有1、2个小时是不可能的。所以我又硬着头皮带着十二分的警惕返回去坐地铁。询问了到场维持秩序的工作人员,其并未直接告诉我是怎么回事,只是说现在所有问题已经解除请我放心乘车。

当我乘坐另一辆地铁成功到达目的地的时候,真的有一点劫后余生的感觉。办完事回家以后,发现自己右脚脚面和右手臂有瘀伤,应该是撞到了什么地方,左右手臂有一条伤口,估计是被哪个的雨伞划了,而我当时却浑然不觉。

从微博上查询到事件的真相(地铁2号线两人争座打斗引发恐慌)已经是几小时以后的事情了,我不禁莞尔:现在国人对公共安全的信任程度果真已经到了冰点了吗?


Ticktick — 靠谱的 GTD 工具

momo @ 2014.06.17 [ Tools ]

说起 GTD 工具总让人有一种高大上、离自己生活很遥远的感觉。其实这样的工具我们小时候就在使用了,只是表现形式与现在的略有不同,比如:我们小时候把需要完成的作业记在一个本子上,完成一项就划掉;我们在冰箱的黑板上写下近期需要购买的食材,购买以后就划掉。

现如今有了智能手机和电脑,我们做这些事就可以抛弃纸和笔,并且将任务列表和进度通过云服务同步到自己所有的设备上,这就是 GTD 工具的功用了。

我并不是没有想过使用一款系统自带的 GTD 工具(无论是老 MOTO 的 Java 系统、黑莓,还是安卓、iOS、Mac 自带的应用,都有不尽如人意之处)。

所以后来我选用了 GTasks,这个应用的好处是与 Google Calendar 以及 Gmail 自带的 Tasks 小工具无缝集成,用 Google 账号即可完成数据的同步。这个应用我使用了很久,轻量级的日常个人任务管理还是可以胜任的,只是同步的时候,由于大家都懂的原因,很多时候会花费很长的时间、或者压根就不能同步,作为一个有强迫症的人,是不能容忍无法同步、并且同步的进程一直在转的时候你不得不将程序退出这种情况存在的,于是无奈之下我只有卸载了它。

之后辗转使用了各种 GTD 软件,比如 Any.do 什么的,但是始终觉得其 UI 和交互方式与我的审美存在严重的冲突,直到有一天经 Coolapk 评论区的讨论知道了 Ticktick

Ticktick 使用几个月下来,个人总结,这是一款堪称完美的 GTD 工具,理由如下:
1. 全平台覆盖,移动端有 Android 和 iOS 版本,PC 端可以用 Web 版,不用担心换机带来的困扰;
2. 免费版即可使用全部实用功能(虽然我还不曾研究过他的收费版,姑且让我这样认为吧,谁让我穷呢);
3. 使用了自己的云端服务器,这样可以规避很多由于qiang所带来的问题,同步的稳定性有了保障;
4. 交互模式非常合理,在条目上的左划和右划可以分别实现修改任务状态(完成情况,既打钩)、优先级、完成期限、分类/标签管理,更贴心的是对日常使用频率最高的完成期限修改操作做了深入的优化,使用效率大大提升;
5. 在 Android 平台上使用了跟系统一致的设计风格,不会让你有吃了苍蝇一样的感觉。

总体而言,这绝对是一款值得下载和使用的应用。附上下载地址:
iOSAndroid酷安)、Chrome