珠海半程马拉松

以前在学校有跑步锻炼,基本是每周一两次5公里跑操场,时间在半小时以内。来了公司两年,也一直坚持跑步,但都是在跑步机上面跑,基本每周一次,按照10公里每小时速度匀速跑5 6 公里左右,有一次状态较好跑了10公里。觉得自己跑步还可以,于是9月份脑子一热就报名参加珠海半程马拉松,而且直接就报了最长的21公里。结果是悲剧的,但还是长了见识,锻炼了身体,总结了经验。所以在此写一点经验感受,希望对长跑有兴趣的同学有所帮助。

装备

俗话说工欲善其事,必先利其器。以前在学校跟在公司跑步机上跑都是随便穿些的运动鞋跑的,也没啥其他装备,但现在到公路上跑就不一样了。

首先一双减震效果好的运动鞋是十分必要的,因为在跑步机或者塑胶操场上跑步,本身就有减震效果,但到公路上则不是了,一开始跑公路多多少少膝关节或踝关节都有点受不了,所以一双好的运动鞋十分重要。我买的是nike 的air max 全掌气垫跑步鞋,虽然看专业的跑步论坛高手似乎都不穿这种鞋,但我自己穿着觉得还可以。

接着上公路跑步,手机钱包钥匙是不可能装口袋里的了,所以跑步的腰包或臂包还是十分必要的,这些功能性差距不太大的东西,如果不是要追求高端大气上档次的话,淘宝淘些过得去的就可以了。

如果你想实时观察自己的速度、距离、时间、心律等数据的话,跑步手表是很好的选择。虽然现在手机上的一些软件(咕咚运动之类)也可以做到,但跑的时候总拿着手机看一来费劲二来不安全。跑步手表品牌方面,专业的基本是松拓或者Garmin,大众一点的就是nike+那款跑步手表,带GPS功能的基本在1千以上。综合考虑价格跟功能,我买的是moto的一款跑步手表moto actv,国内已经没卖的了,上淘宝找海外代购最后手表+心率带1千6左右成交,还不算坑,但就是等了三四周才到货。各种手表的特点这里就不展开介绍了,有兴趣的大家可以上网搜搜。

Continue reading

《数学之美》

咋一看这书的名字,都会以为是一本数学书,但其实跟数学关系不算很大。作者吴军,清华毕业,去美国读博,研究语音识别,自然语言处理。毕业后在Google做搜索,现在在腾讯。这书《数学之美》,主要是作者在Google黑板报上连载的系列博客整理合集。不到300页的书分了29章,内容比较广,有涉及一定的数学知识,不过没有深入讲,大部分是科普性质,点到为止。

书本开头介绍了语言处理的发展历史。在上世纪70年代以前,所有科学家考虑机器处理自然语言问题时,都是按照人的思维模式,希望通过语法规则去分析语言样本,然后解析出各种要素。这样的处理方法计算量非常大,并且规则复杂多变,所以70年代以前自然语言处理没什么进步。而后统计语言学的出现使得自然语言处理快速发展,直到现今为止,基于统计的文本处理,语音识别,已经非常准确了。介绍了语言处理的发展历史后,科普了一下统计语言模型和隐含马可夫模型,还有语言处理相关的一些算法和数学知识。

接着书本开始讲搜索引擎,先介绍了搜索引擎的粗略模型。其实搜索引擎就是写一个网络爬虫,不停的从网上扒数据下来,然后在这些海量的数据里找出用户想要搜索的东西给用户。这个过程中会用到的许多算法和数学知识,书中也简单的介绍了。例如网络爬虫编,信息的特征向量(怎么知道两篇报道都是讲体育新闻的),网页排名以及对应的作弊反作弊等等。

最后书本中还介绍了一些其他相关或不相关的知识,包括密码学算法,布隆过滤器,贝叶斯网络,维比特算法,云计算等。还介绍了几位大神(贾里尼克、辛格、马库斯)的事迹以及学术贡献。

除了数学、算法以外,在作者的字里行间,传达了两个思想我觉得很有价值。一个是大道至简,一个是以道御术。大道至简讲的是作者在语言处理以及搜索引擎上面工作多年,发现好的算法、数学模型,都应该是简单的,而不是复杂的。这个理念同样被乔布斯在工艺设计,美学上极力推崇(Simple is Beautiful)。至于以道御术,术指的是做事情的具体方法,道指的是做人做事的道义道理。无论是做技术,做事,还是工作生活,都有“术”与“道”之分,我们要善于以道御术。这一点的确值得我们多多思量。

总的来说,《数学之美》这本书以点盖面的介绍了很多语言处理与搜索引擎相关的算法和数学知识,尽管有些看不懂,很多仅仅是一带而过,但让我们这些外门汉对这些领域有了一定的了解,增长了见识,还是很有意义的。

布隆过滤器

布隆过滤器是Burton Bloom 在1970年提出的,用于解决打标记的问题。对于每个字符串,利用k种不同的字符串hash算法,生成k个哈希值,然后把这k个值打入大小为m个bit的槽中,用以标记这个字符串已经出现。举个简单的例子,对于字符串”blog.vvbin.com”,利用k=4种不同的字符串哈希算法,产生4个哈希值:4216,3054,1017,2222。然后采用求模的方式打入m=31的bit槽中,结果如下图:

bloom-bit

在查询时,只要查看对应的k个bit位是否为1,就可以知道当前字符串是否已经存在。

布隆过滤器通常只需传统哈希表1/8的存储空间,就可达到很好的哈希效果。假设我们有10万个字符串,鉴于hash表的存储效率大约是50%,这样我们需要20万个槽,每个槽是一个32位(8字节)的DWORD,这样我们需要160万字节空间来存储。而如果采用布隆过滤器,对于10万个字符串,我们采用160万个槽来存储,每个槽是一个bit,那么我们总共只需160万bit,也就是20万字节,即可达到比较理想的哈希效果。

Continue reading

侯捷老师《C++及标准库》课程培训 记录

这周一至周三(2013.07.22-2013.07.24)三天时间,有幸参加到侯捷老师的《C++及标准库》课程培训,不仅加深了对C++的理解,了解了STL的许多细节,而且重温了大学课堂的生活,十分高兴。感谢公司给予这样宝贵的机会,感谢侯捷老师的精彩课程,更加感谢他创作,翻译了这么多优秀书籍,为广大国内程序员指点迷津,授业解惑。

这次课程面向的是初级程序员,所以有些知识点在大学中已经接触到,但温故而知新也不失为一件乐事。以下是我对于这三天课程的一些知识点总结。

Continue reading

为什么求模运算要用素数(质数)—— 哈希表设计

在设计用除法来散射的哈希表时,我们都会用数值模哈希表大小,得到的余数来作为ID存入哈希表对应格子中。所有文章都表明要用一个较大的素数来作为哈希表的大小,也就是要模一个较大的素数。但为什么就是要用素数呢?简单分析一下可以看出玄机。

先看看如果用一个合数8作为哈希表大小,0-30在哈希表中的散射情况:

(表1)

mod8

再来看看用质数7作为哈希表大小,0-30在哈希表中的散射情况:

(表2)

mod7

Continue reading