有趣的数学: 小浣熊干脆面与伯努利试验

记得小学的时候特别喜欢吃一种叫做"小浣熊"的干脆面, 并不是说有多么好吃, 主要是为了收集其中附赠的卡片, 吃面倒成了其次. 当时流行的是水浒108将, 那些卡片外观精美, 正面是每一个水浒好汉的生动造型, 背面则是人物介绍, 我最喜欢的是那些关于武器、必杀技、攻击力之类的, 总之很迷恋, 对于那些名词很是敏感. 那时候每一个买这种干脆面的小孩子的最大愿望肯定都是把108张卡片全部集齐, 我几乎是每天一包的买, 下课就会冲向小卖部, 呵呵~ 不过在我集齐之前就厌倦了吃干脆面的日子, 小孩子嘛, 都比较喜新厌旧, 印象比较深的是我有排名考前的几张以及第108张"鼓上蚤——时迁". 现在淘宝上已经有人在卖这个系列的卡片, 都很便宜. 这里也有对于其中部分卡片的精彩点评.

这和伯努利试验 (Bernoulli trial) 又有什么关系? 主要是我今天在看CLRS的时候突然想用概率的知识来算算到底我需要买多少袋干脆面才能集齐108张水浒卡片, 这个应该不算很蛋疼吧, 囧. OK, 闲话少说, 现在我们的目标是收集108张各不相同的卡片, 收集到一张就算成功一次. 那种结果或者成功, 或者失败的试验就叫做伯努利试验, 因此如果我们要集齐的话, 就需要进行n次伯努利试验, 这个n也就是一共需要购买干脆面的期望袋数. 把这n次试验分成108个阶段, 每一个阶段代表上一次收集成功到这一次收集成功间的过程, 比如第108阶段就是在成功收集到107张之后至收集到108张这之间需要经历的过程. 每一个阶段又是一系列小的伯努利试验, 把所有阶段的试验次数加起来也就得到了n的值.

在搞清楚基本原理之后, 来计算一下每一个阶段成功的概率, 也就是我在买了无数袋干脆面之后终于拿到一张不是重复卡片的概率. 假设现在是第i阶段, 证明我已经成功收集了i - 1张卡片, 还剩下108 - i + 1张没有被拿到. 每一张卡片被拿到的概率是1/108, 108 - i + 1张卡片被拿到的概率就是(108 - i + 1)/108, 即是每一个阶段成功的概率. 而第i阶段所进行的一系列伯努利试验的次数n_i是服从几何分布的随机变量, 根据几何分布的性质:

上面的期望值就是每一个阶段成功时进行的试验次数, 正如前面所说, 把每一个阶段的试验次数都加起来也就得到了总的试验次数, 也就是我需要买的干脆面袋数, 计算过程如下:

算下来大约需要购买506袋干脆面才能集齐卡片, 也许当时我再坚持那么一下下就可以了, :)

这个问题的变种还有将球投入n个盒子中, 计算需要投多少个球才能让每一个盒子中都至少有一个球.

在Ubuntu中配置可供Windows主机共享上网的VPN服务器

VPN (Virtual Private Network, 虚拟专用网) 是一种在现有网络基础上建立的虚拟网络, 主要用于帮助两个网络通过VPN隧道 (tunnel) 进行通信. VPN的好处在于网络A中的电脑A₁通过隧道与网络B中的电脑连接上后, A₁将能够使用网络B的网络环境. VPN分为加密与不加密两种, 通常我们使用的都是加密VPN. 加密VPN常用的协议有SSL、PPTP等, 其中PPTP是Windows系统内置的协议, 因此如果想要搭建一个支持Windows电脑接入的VPN服务器, 最好是使用PPTP服务器软件. 当前VPN的主要用途有在异地接入一个内部网络, 以及翻越功夫网.

注意: VPN服务器必须是具有外网IP的电脑, 如果IP地址属于10.0.0.0~10.255.255.255, 172.16.0.0~172.31.255.255, 192.168.0.0~192.168.255.255这三个IP地址段, 则不具备搭建VPN服务器的条件.

Poptop是一款Linux下的PPTP服务器软件, 今天我们就主要借助它来完成一个VPN服务器的配置. Ubuntu系统使用如下命令安装Poptop:

$ sudo apt-get install pptpd

如果你的Linux的内核版本低于2.6.15, 那么需要先检查一下是否支持MPPE:

$ sudo modprobe ppp-compress-18 && echo "success"

若是没有输出"success"则证明内核不支持, 可以跟随这里的步骤进行内核的配置.

Poptop安装完毕之后需要简单配置一下, 打开"/etc/pptpd.conf"文件, 添加下面两行, 或者这个文件已经有了一些示例, 只需要去掉注释符号.

localip 192.168.0.1
remoteip 192.168.0.234-238,192.168.0.245

"localip"表示VPN隧道中服务器 (server) 的IP地址, "remoteip"表示VPN隧道中客户端 (client) 可以分配的IP地址. 关于"pptdp.conf"文件的更多选项, 可以阅读它的man page.
然后设置用于登录的用户名和密码, 打开"/etc/ppp/chap-secrets"文件, 添加下面一行, 中括号部分代表需要配置的地方:

[username] pptpd [password] *

最后重启Poptop:

$ sudo /etc/init.d/pptpd restart

现在试试用其它电脑是否可以成功连上, 注意客户端填写的IP地址是VPN服务器的外网IP, 而不是刚才配置的"localip".

虽然可以成功建立VPN连接, 但通常情况下还不能通过VPN服务器连接到Internet. 原因有多种, 先来看看客户端通过VPN服务器与Internet上的服务器通信的全过程:

client <--> client ppp0 <--> VPN server ppp0 <--> VPN server <--> VPN server eth0 <--> Internet server eth0 <--> Internet server

"ppp0"其实是VPN虚拟的一个网络接口 (可以想象成这是一个虚拟的网卡), VPN隧道就是通过客户端与服务器的这两个网络接口建立的. 而"eth0"则代表服务器上真实存在的物理网卡, VPN服务器与外网通信就需要通过它. 具体流程是: 客户端通过"ppp0"向VPN服务器发出请求, VPN服务器侦测到之后, 再将请求通过"eth0"转发出去, 当请求到达目的地之后, Internet服务器就根据请求做出相应的回复, 这个回复再按照刚才来的路径返回到客户端, 这样客户端就成功与Internet服务器完成一次通信.

上面图示中的箭头部分 ("<-->") 就是可能造成无法连接Internet的关键, 因此需要针对每个部分一一排查. 这里只对可能性最大的两个地方进行介绍, 想要了解每一个关键点的检测方法的同学可以阅读"Diagnosing Forwarding on pptpd"这篇文章.

1. 是否已经打开IP转发?

查看"/proc/sys/net/ipv4/ip_forward"文件中的值是否为"1", 如果不是, 则需要在"/etc/sysctl.conf"文件中添加"net.ipv4.ip_forward=1", 然后执行以下命令:

$ sudo /etc/init.d/procps restart

2. 是否在VPN服务器上设置了对于客户端IP地址的NAT?

执行下面的命令查看表中是否有相应的表项:

$ sudo iptables --table nat -L POSTROUTING

如果没有则执行以下命令:

$ sudo iptables --table nat --append POSTROUTING --out-interface eth0 --jump MASQUERADE

在完成上面两个检查之后, 应该就可以成功通过VPN服务器与Internet进行通信, 一个VPN服务器也基本配置完毕.

参考资料: Debian pptpd HOWTO, #13, Diagnosing Forwarding on pptpd.

Android系统在发送短信后报错的解决

今天在发送短信的时候, 每发完一条就提示"The application Messaging (process com.android.mms) has stopped unexpectedly. Please try again.", 很是烦人, 还以为是系统出问题了, 然后在这里找到了解决方法, 说来也简单, 把所有短信删了就行了... 难道是存储的短信太多造成的? 太诡异了, 我手机里总共也没多少, 不过反正有一个叫做"SMS Backup"的软件, 重要的以后就备份到Gmail去算了.

流言终结者: 使用位运算交换变量的值

在C语言中怎样交换两个变量的值? 我们通常的做法是:

tmp = a;
a = b;
b = tmp;

那怎样不使用中间变量交换两个变量的值? 也许你看过这样的方法:

a ^= b;
b ^= a;
a ^= b;

这是一个借助于位运算的小伎俩, 但一般在实际编程中是不推荐使用的, 原因在大多数人看来应该是降低了代码的可读性, 其实还有一个被忽视的地方. 在多数人的直觉中位运算绝对比普通的运算符要快, 不过刚才的例子是一个反例.

现在让我们来看一下上面两段代码对应的汇编代码, 这里使用gcc作为编译器. 首先是使用了中间变量的那几句:

movl    -4(%ebp), %eax
movl    %eax, -12(%ebp)
movl    -8(%ebp), %eax
movl    %eax, -4(%ebp)
movl    -12(%ebp), %eax
movl    %eax, -8(%ebp)

"-4(%ebp)"、"-8(%ebp)"、"-12(%ebp)"分别是变量a、b、tmp在栈中的地址, 同时使用了寄存器"eax". 可以看出, 上面的代码一共对内存进行了3次读操作和3次写操作.
再来看看使用位运算的汇编代码:

movl    -8(%ebp), %eax
xorl    %eax, -4(%ebp)
movl    -4(%ebp), %eax
xorl    %eax, -8(%ebp)
movl    -8(%ebp), %eax
xorl    %eax, -4(%ebp)

一次"xorl"异或操作包含一次读和一次写, 因此一共是6次读操作和3次写操作.
通过比较可以看出位运算在I/O速度上已经不占优势, 再比较一下两种代码所需的内存空间, 下面这段汇编是公共的代码.

pushl   %ebp
movl    %esp, %ebp
subl    $16, %esp

两种方法都在栈中分配了16个字节的空间, 因此在空间上的比较是一样的. 这样看来, 使用位运算交换两个变量的值真是装B者必备的好东西.

/\13y3$-|-

其实我一直认为搞计算机的, 特别是那种顶级黑客, 骨子里都是有一种狂放不羁, 玩世不恭的态度的, 带着一些Hacker特有的幽默. 让我们来欣赏其中的一些吧.

0xDEADBEEF: 乍一看, 这只是一个普通的十六进制数, 但你再仔细看看那几个十六进制字母, 是否恍然大悟? 不要小看这样一个数字, 它可是有特殊用途的. 在早期的IBM RS/6000系列电脑里, 如果在内存中新分配了一块地址, 那这块地址中就全部使用"0xDEADBEEF"填充, 这样做可以很好地防止"heisenbug" (这个有趣的bug后面还会讲到) 的出现. 类似于这样的用法还有很多, 统称"Hexspeak", 也就是用十六进制来表示英语单词, 仅有的六个字母肯定不够用, 于是又用数字"0"来表示"O", "1"表示"I" (i的大写形式), "5"表示"S", "6"或者"9"表示"G"或者"g". 这种通过替换英文字母来表示的行为在网上很是流行, 术语叫做"leet", Google也有一个全部使用leet字母显示的神秘主页, 欢迎围观. 有关"0xDEADBEEF"的更多信息可以阅读Raymond的介绍.

heisenbug: 这名字很眼熟对吧? 其实从前有一个量子物理学家叫做Heisenberg... 噢, 这群人居然都敢开物理学家的玩笑了. 其实不然, 这个名字主要还是源于Heisenberg Uncertainty Principle (海森堡测不准原理), 这不禁让我想到高中时马老那闪烁着智慧光芒的眼镜. "heisenbug"用于描述那些当你试图去了解、探查时莫名消失或者改变的计算机软件bug, 在C语言中, 十有八九"heisenbug"都是由于未初始化的变量引起的.

Bohr bug: 这同样是来自于物理学, 不过这次是原子物理. "Bohr bug"是"heisenbug"的反义词, 这种bug很稳定, 不会到处乱跑, 不过通常也隐藏得比较深, 不容易被发现, 典型的是"缓冲区溢出".

schroedinbug: 还是物理学, 我几乎怀疑计算机学是否是由物理学家开创的. 这个bug源于著名的量子物理学实验: Schrödinger's cat (薛定谔的猫), 具体内容我就不细说了, 详情参见《The Big Bang Theory》第一季17集由Dr. Sheldon带来的权威解释, :) "schroedinbug"是一个神奇的bug, 它只会在你查看源代码或者在特定条件下运行程序时才会出现, 真够纠结的, 但这种bug的的确确是存在的.

还有很多这样的非常规bug, Wikipedia上有详细介绍. 无论怎样, Hacker绝对是这个世界上很有趣的一群动物之一.

编程学习的本质是什么?

很早之前就想写这样一篇文章, 但因为种种原因而耽搁. 今天在思考怎样学习C++时又想到了这个问题, 把它写下来, 作为我自己的一些感想.

作为一个程序员, 真得好好想想我们在学习编程的时候什么是最重要的, 到底什么才是我们追寻的本质? 是把ASP.NET、PHP、JSP、Ruby、Python、C#、Java、C++都学会? 是可以纯熟地使用VS、GTK+、Qt、wxWidgets、Tk来编写图形界面? 是学会各种框架、各种库? 是可以利用JavaScript编写出各种网页特效? 是对于各种浏览器的插件开发了然于胸? 是可以利用系统API开发出各种应用? 在我看来, 这些都不是. 诚然, 以上这些都很有用, 也很重要, 但绝不是一个优秀程序员应该不停追求的.

为什么会有人认为我掌握了这门语言就成了编程高手? 君不见你学的这门语言10年前可能根本不存在, 并且10年后也极有可能不存在. 老有人说IT界知识更新速度太快, 的确, 如果你5年停止学习, 那你在5年后多半就成了一个"废人". 但有一样东西是不会变的, 那就是大师们常说的"内功". 为什么"内功"如此重要? 看看李开复读大学的例子, 1980年李开复在哥伦比亚大学读本科时, 流行的是Pascal和C语言, 以及Fortran, 再看看今天, 除了C语言依旧傲视群雄外, 其它两个早就划归到历史的长河中去了, 只能作为那个年代的特有记忆而保留着. 而30年前李开复在学算法, 在学操作系统, 在学计算机网络, 在学计算机体系结构, 在学离散数学, 30年后的我们依旧需要学习, 依旧需要掌握. 这才是一个程序员需要以及值得追寻的本质.

刘未鹏在"你应当如何学习C++(以及编程)(rev#1)"中提到"一般性的编码实践准则，以及基本的编程能力和基本功，乃至基本的程序设计理论以及算法设计。才是真正需要花时间掌握的东西。"这些都涉及到两个字: 基本. 计算机的基本功无非是刚才说的那几样, 再加上一点数学知识, 但这在很多人眼里却只是考试的时候 (包括找工作时的笔试和面试) 用用而已. 一个真正伟大的程序员会懂得如何通过加强自己的内功, 从而把编程能力发挥到极致.

刚才的言论难免会引来一些实用主义者的辩驳, 工程上的各种新技术、新框架肯定是需要的, 某种程度上来说是要用来吃饭的, 并且也必须借助那些技术才能应用到实际中来. 但凡事都有主次, 这个领域总会不断地冒出新奇的玩意出来, 吸引着好奇的人们去尝试. 就像这个世界也总是充满了各种诱惑, 每个人都可能像海藻那样飘浮不定, 随波逐流. 不过还是有着需要我们坚持的东西. 也许在10年后, 20年后, 你会发现, 你所坚持的东西是多么得宝贵.

2 Years

Our Anniversary, 亲爱的, 有你陪着真好.

Yet Another Gmail Row Highlight 0.0.1 Released! 键盘流的Gmail利器

昨天花了点时间写了一个Greasemonkey脚本, 功能和上一篇介绍的Gmail - Add Row Highlight (以下简称GARH) 很像, 只不过GARH是当鼠标滑过时高亮, 而我的这个脚本是在使用键盘浏览邮件时高亮小箭头指示的那行. 说得有点复杂, 上图:

脚本主页是: http://userscripts.org/scripts/show/62644, 不过目前Chrome/Chromium用户还无法使用.

大家多多提意见, 提交bug和建议请到: http://code.google.com/p/fancyweb/issues/list

推荐几个Chrome/Chromium使用的扩展和Greasemonkey脚本

介绍几个我正在使用的用于Chrome/Chromium的扩展和Greasemonkey脚本, 今天Google还公布了官方扩展网站, 相信不久之后Chrome/Chromium扩展将会迅速发展.

1. Vimlike Smooziee

   Firefox下的Vimperator是我的大爱, 像Vim一样浏览网页, 这是一件既酷又便捷的事情. Vimlike Smooziee即是Chrome/Chromium下的Vimperator, 不过现在的功能还没有后者强大, 只支持基本的操作, 如j、k、H、L、d、u、f、F、gg、G、zi、zo、zz等. 让我们期待以后的发展吧.

2. gPDF

   有时我们不想下载PDF文件, 而是直接在浏览器里打开看看, 以前的方法是安装Adobe Reader, 这样就会在点击PDF链接时自动使用Adobe Reader在浏览器中打开. 不过Adobe Reader实在是有点庞大, 每次打开都要花很长的时间. 现在使用gPDF扩展可以使用Google Docs来打开, 速度很快, gPDF还提供有Greasemonkey脚本和Firefox扩展.

3. Folders4Gmail

   

   这是一个Greasemonkey脚本, 和下一个将要介绍的一样, 属于Firefox扩展Better Gmail 2的其中一个组件. 最新版的Chrome/Chromium已经支持安装Greasemonkey脚本了, 不过还是会发生无法使用某些脚本的杯具. Folders4Gmail脚本的作用是利用Gmail的标签建立树形列表, 如图中所示, 将标签命名为"eBook/Biography", 这样"eBook"就是"Biography"的父目录. 这个脚本对于标签分类很有用处.

4. Gmail - Add Row Highlight

   这个脚本可以让鼠标滑过的邮件高亮显示, 在邮件很多时可以不至于眼睛看花, XD

让IPython支持清屏

IPython是一个增强型的Python Shell, 比Python自带的那个功能更强大. 在普通Python Shell里可以通过"Ctrl+l"来清屏, 可在IPython里这个快捷键就不起作用了. 为了达到这个目的, 我们需要对IPython进行一点设置.

在这篇文章中我找到了方法, 需要修改"~/.ipython/ipythonrc"文件, 可现在IPython更推荐通过修改"~/.ipython/ipy_user_conf.py"文件来设置IPython. 打开"ipy_user_conf.py"应该可以看到一些示例, 我们需要做的是调用"parse_and_bind()"函数来增加新的键绑定. 在"main()"函数中添加以下语句, 注意你的配置文件中可能已经包含了部分语句, 只需要去掉注释符号就行了.

def main():   
    ...

    import readline
    readline.parse_and_bind('\C-l: clear-screen')

不过这样还不算完成, 需要检查一下"ipythonrc"文件中是否有相互冲突的配置, 比如在我的文件里包含下面一行:

readline_parse_and_bind "\C-l": possible-completions

注释掉即可, 现在进入IPython去试试吧.