对论文《A Mathematical Theory of Communication》的简要解读

香农在1948年发表了一篇著名的论文A Mathematical Theory of Communication,作为现代信息论的奠基之作,不管是从理论角度还是对人类实际生活的贡献,再怎么强调这篇论文的重要性都不过分。虽然之前对信息论已经有所了解,但是为了向信息论鼻祖致敬,最近还是拜读了这篇论文。这篇论文自成体系,可以说是字字珠玑,读完后对整个信息论的来龙去脉有了更加深入的了解。其实这篇论文主要就是要解决如何用数学方式去度量信息的价值,虽然核心思想及方法非常简单明了,但是由于

如何实现一个malloc

任何一个用过或学过C的人对malloc都不会陌生。大家都知道malloc可以分配一段连续的内存空间,并且在不再使用时可以通过free释放掉。但是,许多程序员对malloc背后的事情并不熟悉,许多人甚至把malloc当做操作系统所提供的系统调用或C的关键字。实际上,malloc只是C的标准库中提供的一个普通函数,而且实现malloc的基本思想并不复杂,任何一个对C和操作系统有些许了解的程序员都可以很容易理解。 这篇文章通过实现一个简单的malloc来描述malloc背后的机制。

生成特定分布随机数的方法

生成随机数是程序设计里常见的需求。一般的编程语言都会自带一个随机数生成函数,用于生成服从均匀分布的随机数。不过有时需要生成服从其它分布的随机数,例如高斯分布或指数分布等。有些编程语言已经有比较完善的实现,例如Python的NumPy。这篇文章介绍如何通过均匀分布随机数生成函数生成符合特定概率分布的随机数,主要介绍Inverse Ttransform和Acceptance-Rejection两种基础算法以及一些相关的衍生方法。下文我们均假设已经拥有一个可以生成0到1之间均匀分布

2048-AI程序算法分析

针对目前火爆的2048游戏,有人实现了一个AI程序,可以以较大概率(高于90%)赢得游戏,并且作者在stackoverflow上简要介绍了AI的算法框架和实现思路。但是这个回答主要集中在启发函数的选取上,对AI用到的核心算法并没有仔细说明。这篇文章将主要分为两个部分,第一部分介绍其中用到的基础算法,即Minimax和Alpha-beta剪枝;第二部分分析作者具体的实现。 基础算法 2048本质上可以抽象成信息对称双人对弈模型(玩家向四个方向中的一个移动,然后计算机在某个空

抓取网页内容生成Kindle电子书

自从买了kindle后,总是想着如何最大效用发挥其效用。虽然多看上有很多书可以购买,网上也有很多免费的电子书,但是仍然有很多感兴趣的内容是以网页的形式存在的。例如O’Reilly Atlas就提供了诸多电子书,但是只提供免费的在线阅读;另外还有很多资料或文档都只有网页形式。于是就希望通过某种方法讲这些在线资料转为epub或mobi格式,以便在kindle上阅读。这篇文章介绍了如何借助calibre并编写少量代码来达到这个目的。 Calibre Calibre简介 Calibr

开始使用Ubuntu作为工作环境

2012年3月,我自购了一台13寸的Macbook Air,从那时开始至今近两年时间,我一直用它作为工作本。但是最近越来越觉得4G的内存和128G的SSD力不从心,苦于Air无法升级硬件,于是终于下决心拿出入职时公司给配的Dell E6410,自己买了内存和SSD,升级成了8G内存+370G混合硬盘(120G SSD做主盘,250G硬盘做从盘)。 硬件升级事小,关键是系统的迁移代价比较大。我在Dell本上装的是Ubuntu 13.10,由于我平时习惯使用Dropbox等云端服

一个故事告诉你比特币的原理及运作机制

周末花时间看了一些比特币原理相关的资料,虽然不敢说把每个细节都完全搞懂了,不过整体思路和关键部分的主要原理还是比较明白。写一篇文章分享给大家。这篇文章的定位会比较科普,尽量用类比的方法将比特币的基本原理讲出来。这篇文章不会涉及算法和协议中比较细节的部分,打算后面会再写一篇程序员视角下的比特币原理,那里会从技术人员的视角对比特币系统中较为关键的数据结构、算法和协议进行一些讲解。 在这篇文章中我会给出一个虚拟的村庄叫“比特村”,整个文章会以讲故事的方式,逐步告诉大家比特币提出的动

MySQL索引与Index Condition Pushdown

大约在两年前,我写了一篇关于MySQL索引的文章。最近有同学在文章的评论中对文章的内容提出质疑,质疑主要集中在联合索引的使用方式上。在那篇文章中,我说明联合索引是将各个索引字段做字符串连接后作为key,使用时将整体做前缀匹配。 而这名同学在这个页面找到了如下一句话:index condition pushdown is usually useful with multi-column indexes: the first component(s) is what index

使用MPlayer观看Coursera课程视频的一些心得

之前一直是在线看Coursera上的课程视频。最近迫于租住的房子网速太差,加之Coursera访问经常不稳定,为了使得流畅学习的过程不被破坏,开始考虑将视频下载到本地观看。 因为之前一直没有在本地看视频的习惯,很少使用播放器,所以找个顺心的播放器就成了重中之重。经过一番折腾,最终选择了MPlayer,原因主要有如下几点。 免费的。 MPlayer同时支持Mac和Linux。因为我公司用的是Mac,而住处用的是Linux,所以播放器能跨这两个操作系统很重要。 通过命令行操作,

五种常用基数估计算法效果实验及实践建议

之前我曾写过一系列关于基数估计(cardinality estimation)算法的文章,文中介绍了一些常用基数估计算法的原理。最近对常用的基数估计算法做了一些实验,这篇文章描述了实验结果,包括这些算法的估计效果及误差状况,主要通过图表展示。通过观察实验数据和可视化图表可以加强对各种基数估计算法理论分析的直观理解。 文章首先会对实验做一些说明,然后通过图表详细展示实验数据,最后会根据实验结果总结一些实践中有用的结论。 实验说明 算法选择 这次实验共选择了五种基数估计算法,分别