Wednesday, January 27, 2010

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

小浣熊水浒卡: 吴用

记得小学的时候特别喜欢吃一种叫做"小浣熊"的干脆面, 并不是说有多么好吃, 主要是为了收集其中附赠的卡片, 吃面倒成了其次. 当时流行的是水浒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阶段所进行的一系列伯努利试验的次数ni是服从几何分布的随机变量, 根据几何分布的性质:

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

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

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

Thursday, January 14, 2010

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

VPN (Virtual Private Network, 虚拟专用网) 是一种在现有网络基础上建立的虚拟网络, 主要用于帮助两个网络通过VPN隧道 (tunnel) 进行通信. VPN的好处在于网络A中的电脑A1通过隧道与网络B中的电脑连接上后, A1将能够使用网络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转发?

  2. 查看"/proc/sys/net/ipv4/ip_forward"文件中的值是否为"1", 如果不是, 则需要在"/etc/sysctl.conf"文件中添加"net.ipv4.ip_forward=1", 然后执行以下命令:
    $ sudo /etc/init.d/procps restart
    
  3. 是否在VPN服务器上设置了对于客户端IP地址的NAT?

  4. 执行下面的命令查看表中是否有相应的表项:
    $ 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.

Tuesday, January 12, 2010

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

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

Monday, January 11, 2010

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

在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)"分别是变量abtmp在栈中的地址, 同时使用了寄存器"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者必备的好东西.