Functional Programming For The Rest Of Us

Via https://github.com/justinyhuang/Functional-Programming-For-The-Rest-of-Us-Cn/blob/master/FunctionalProgrammingForTheRestOfUs.cn.md

傻瓜函数式编程

2006年6月19日,星期一

开篇

我们这些码农做事都是很拖拉的。每天例行报到后,先来点咖啡,看看邮件还有RSS订阅的文章。然后翻翻新闻还有那些技术网站上的更新,再过一遍编程论坛口水区里那些无聊的论战。最后从头把这些再看一次以免错过什么精彩的内容。然后就可以吃午饭了。饭饱过后,回来盯着IDE发一会呆,再看看邮箱,再去搞杯咖啡。光阴似箭,可以回家了……
(在被众人鄙视之前)我唯一想说的是,在这些拖拉的日子里总会时不时读到一些不明觉厉的文章。如果没有打开不应该打开的网站,每隔几天你都可以看到至少一篇这样的东西。它们的共性:难懂,耗时,于是这些文章就慢慢的堆积成山了。很快你就会发现自己已经累积了一堆的收藏链接还有数不清的PDF文件,此时你只希望隐入一个杳无人烟的深山老林里什么也不做,用一年半载好好的消化这些私藏宝贝。当然,我是说最好每天还是能有人来给送吃的顺带帮忙打扫卫生倒垃圾,哇哈哈。

我不知道你都收藏了些什么,我的阅读清单里面相当大部分都是函数式编程相关的东东:基本上是最难啃的。这些文章充斥着无比枯燥的教科书语言,我想就连那些在华尔街浸淫10年以上的大牛都无法搞懂这些函数式编程(简称FP)文章到底在说什么。你可以去花旗集团或者德意志银行找个项目经理来问问1:你们为什么要选JMS而不用Erlang?答案基本上是:我认为这个学术用的语言还无法胜任实际应用。可是,现有的一些系统不仅非常复杂还需要满足十分严苛的需求,它们就都是用函数式编程的方法来实现的。这,就说不过去了。
关于FP的文章确实比较难懂,但我不认为一定要搞得那么晦涩。有一些历史原因造成了这种知识断层,可是FP概念本身并不难理解。我希望这篇文章可以成为一个“FP入门指南”,帮助你从指令式编程走向函数式编程。先来点咖啡,然后继续读下去。很快你对FP的理解就会让同事们刮目相看了。

什么是函数式编程(Functional Programming,FP)?它从何而来?可以吃吗?倘若它真的像那些鼓吹FP的人说的那么好,为什么实际应用中那么少见?为什么只有那些在读博士的家伙想要用它?而最重要的是,它母亲的怎么就那么难学?那些所谓的closure、continuation,currying,lazy evaluation还有no side effects都是什么东东(译者:本着保留专用术语的原则,此处及下文类似情形均不译)?如果没有那些大学教授的帮忙怎样把它应用到实际工程里去?为什么它和我们熟悉的万能而神圣的指令式编程那么的不一样?
我们很快就会解开这些谜团。刚才我说过实际工程和学术界之间的知识断层是有其历史原因的,那么就先让我来解释一下这个问题。答案,就在接下来的一次公园漫步中:

继续阅读

[时间复杂度 Time Complexity of Algorithms

神犇说世上的美有三种,一是优美精致的数据结构,二是巧夺天工的神奇算法,三是你温暖世界的笑容

计算机之所以叫做计算机,就是因为它在“计算”这一件事上做的可以比人类快。而我们的任务,就是告诉计算机要如何去进行一个计算,也就是要实现一个算法。
想要让程序更快,除了要提升计算机处理器的运行速度之外,最重要的就是要提升算法的效率,以及算法的在这个计算机上实现的的速度。
做同样的一件事情,可以有无数种做法。比如说给一些数字排序,就有好几种做法。那么要怎么比较他们的速度呢?
最直观的做法自然是写出对应的程序,给定一个输入,然后比较一下他们的运行时间。这样的做法简单粗暴,然而并不能给我们关于这些算法的更多信息,也只能反映这些算法在这个特定输入的情况,误差也不容小视。
更为严谨的做法,是对这个算法进行数学上的分析,以得出这个算法在理论上的运行效率。
以选择排序为栗子把
(然后把栗子剥开吃掉~

来看看他的运行原理
选择排序
第零轮从所有的n个数据中找出最小的,需要对每个\(j\in \left ( 0,n \right )\)进行一次比较,共n-1次
第一轮从剩下的n-1个数据中找出最小的,需要对\(j\in \left ( 1,n \right )\)每个进行一次比较,共n-2次
……
第i轮从剩下的n-i个数据中找出最小的,需要对\(j\in \left ( i,n \right )\)每个进行一次比较,共n-i-1次
第n-2轮从剩下的2个数据中找出最小的,需要进行一次比较

总共需要进行 \(\sum_{k = 1}^{n-1} k=\frac{n\left ( n-1 \right )}{2}\)次比较
然后每轮需要对数据进行一次交换,合计是\(\left ( n-1 \right )\)次交换
也就是说,这个程序所需要运行的时间大致上是
\(T=\frac{n\left ( n-1 \right )}{2}T_{0}+\left ( n-1 \right )T_{1}\),其中\(T_{0}\)为一次比较需要的时间,\(T_{1}\)为一次交换所需要的时间
当n很大的时候,对T的量级起到决定性作用的将会是什么呢?
(还记得函数在无穷大的极限吗?
n趋向于无穷大时,起作用的将会是n的二次项,也就是\(\frac{n^{2}}{2}T_{0}\)
那么可以看出,选择排序的算法的运行时间在n充分大的时候,大致正比于\(n^{2}\)
继续阅读

……其实只是想给这几天啥都没干找个借口而已嘛

Win10

GTA GTC15前就看到10240出来,抱着尝鲜的心态下了偷跑的ISO刻了个U盘,备份一下就从Win8.1U1Home升级到了Win10Pro……额果然没办法激活,先KMS撑了几天。

回来后就听说Win10开始推送了,想一想KMS续命可麻烦了……老老实实OTA

还原8.1,联想一键备份duang的一下告诉我“不能访问文件”……呵呵你把我C盘格了再告诉我没法还原?

神奇的是一个NTFS分区被格居然搞的我的Ubuntu都起不来了,我望着我电脑上唯一能用的系统——android5.1在月光下凌乱。

用U盘全新安装了个Win10Home,还是没法激活,先将就用着

折腾了半天备份文件确认是C盘的备份文件在备份时就损坏了,还原前赶时间没有备份Win10呵呵C盘所有数据都丢了吧

想一想有一个原厂Win8镜像恢复上,然后再安装Win10Home……嗯还是没办法激活。孩子激活老不好,多半是SKU废了

找了个OEM的镜像果然可以哈哈哈哈

然后我的GRUB呢?
继续阅读

Windows 10 vs Longhorn

习惯了Start Screen和Charm Bar,现在在WindowsXP上关机都不会关了。想想不久以前还在迷恋Windows7酷炫的Aero、为了Mac的壁纸把Windows 7彻底搞成Mac的样子以及成功的在Windows上玩了一把桌面立方体……LOL,现在还不是Modern UI的支持者。

 

想起来家里买的台式机,大概就是Vista出来后第二年,标配Vista,貌似有Aero……之所以说貌似是因为抱回家的时候就变成蓝天白云一片绿了。现在想想刷回XP还是挺正确的。

XP诞生之时,正好是桌面系统飞速发展的时候,各家各户都用上了电脑。中国电脑桌面系统的标配,从DOS+WPS到了XP+OFFICE。开发软件的越来越多,打包盗版系统的也越来越多,玩游戏的也越来越多……就这样,XP在中国乃至世界的PC上站稳了脚跟。有一台装着XP的电脑,握着一台诺基亚就算是紧跟潮流了。

 

微软也没闲着,时代总要进步嘛,他们也在继续研发,Longhorn,Longhorn Reset,Vista。好吧这是退步了。

继续阅读