小纸片到核当量 — 费米估算的用处

这是在中小学课本上一个著名的故事，第一颗原子弹爆炸的时候，现场的物理学家费米同志往天上撒纸片玩儿，根据爆炸的气浪吹飞纸片的距离，计算核当量。这种估算方式现在被称为费米估算（Fermi estimation），常用于进行量级上的大致估算。

 

学会了这招，再遇到Google面试题中类似一个倒霉的校车能装多少高尔夫球之类的问题就能解决了。比如在Fermi problem的维基上的“芝加哥有多少钢琴调琴师”的问题，通过如下假设：

 

1. 大约有5,000,000 人生活在芝加哥。

2. 在芝加哥平均每个家庭有2个人。

3. 大约在20个家庭中有1个家庭有定期地需要调钢琴。

4. 定期调琴的钢琴每年需要调整一次。

5. 每个调琴师大约需要2小时调琴，包括路上时间。

6. 每个调琴师每天工作8小时，一周5天，一年50周。

 

估算出每年在芝加哥需要调整的钢琴数量为：

 

(5,000,000 人在芝加哥) / (2 人/家) × (1 架钢琴/20 家) × (1 架钢琴调整/1年) = 125,000 架钢琴在芝加哥每年被调整。

 

类似地计算出平均每个调琴师：

 

(50 周/年)×(5 天/周)×(8 小时/天)/(1 架钢琴/2小时) = 1000 架钢琴每年/1调琴师。

 

再一除，结果就出来了：

 

(125,000 架钢琴在芝加哥每年被调整) / ( 1000 架钢琴每年/1调琴师) = 125 个调琴师在芝加哥。

 

我之所以想写这个问题是因为在《编程珠玑》(Programming Pearls)的第七章<The Back of the Envelope>，专门讲程序员的估算问题，其方法正是费米估算。这类估算在工程中很有用，比如你想知道一百万个某种数据结构的实例会消耗多少内存，某段程序估计会运行多长时间。通过ping判断大概每分钟能传输多少数据等等，在这里就不赘述了。

 

不难发现，这种估算的背后都需要对常识有个大致的了解，如果连for loop执行一个赋值运算语句的时间都不知道，怎么估算它运行1000000次的时间。Peter Norvig在其《Teach Yourself Programming in Ten Years》也提到过这个问题，并给出了一些常用数据（根据摩尔定律，这个数据现在的有效性不敢保证了），大家可以试试：

 

execute typical instruction	1/1,000,000,000 sec = 1 nanosec
fetch from L1 cache memory	0.5 nanosec
branch misprediction	5 nanosec
fetch from L2 cache memory	7 nanosec
Mutex lock/unlock	25 nanosec
fetch from main memory	100 nanosec
send 2K bytes over 1Gbps network	20,000 nanosec
read 1MB sequentially from memory	250,000 nanosec
fetch from new disk location (seek)	8,000,000 nanosec
read 1MB sequentially from disk	20,000,000 nanosec
send packet US to Europe and back	150 milliseconds = 150,000,000 nanosec

 

———————————————————————

转自：http://mp.weixin.qq.com/s?__biz=MzA5NjQ2MTgzMw==&mid=200065264&idx=1&sn=556f07fbe98bb42a80cc7d9c2160fa21&3rd=MzA3MDU4NTYzMw==&scene=6#rd