CodingLabs -- IT技术博客大学习 -- 共学习共进步！

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

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

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

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

• 如何实现一个malloc

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

• 2048-AI程序算法分析

针对目前火爆的2048游戏，有人实现了一个AI程序，可以以较大概率(高于90%)赢得游戏，并且作者在stackoverflow上简要介绍了AI的算法框架和实现思路。但是这个回答主要集中在启发函数的选取上，对AI用到的核心算法并没有仔细说明。这篇文章将主要分为两个部分，第一部分介绍其中用到的基础算法，即Minimax和Alpha-beta剪枝；第二部分分析作者具体的实现。

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

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

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

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

• 使用SeaJS实现模块化JavaScript开发

SeaJS是一个遵循CommonJS规范的JavaScript模块加载框架，可以实现JavaScript的模块化开发及加载机制。与jQuery等JavaScript框架不同，SeaJS不会扩展封装语言特性，而只是实现JavaScript的模块化及按模块加载。SeaJS的主要目的是令JavaScript开发模块化并可以轻松愉悦进行加载，将前端工程师从繁重的JavaScript文件及对象依赖处理中解放出来，可以专注于代码本身的逻辑。SeaJS可以与jQuery这类框架完美集成。使用SeaJS可以提高JavaScript代码的可读性和清晰度，解决目前JavaScript编程中普遍存在的依赖关系混乱和代码纠缠等问题，方便代码的编写和维护。

• 我的博客系统折腾手记暨papery正式发布

上周花了一个周末的时间，把我自己的博客生成系统彻底重构成较为通用的系统了。这件事其实一直就想做，不过一直没想好怎么在简单和通用间做好权衡。上周接连接到几名同学在微博上问我的博客是用什么系统搭建的，终于促使我下决心把这件事情做掉。目前这个系统已经定名为papery，源码在github上，并发布到了npm。

• 算法分析中递推式的一般代数解法

因为递推式求解的重要性，许多算法书籍对其有专门介绍。Donald Knuth在Concrete Mathematics一书中多个章节都涉及递推式求解方法。算法导论也在第四章中专门论述的这个主题。在这些相关论述中，主要介绍了一些启发式方法，这些方法往往需要一些特殊的技巧和灵感才能完成。而本文将论述一种纯代数式的方法，这种方法将求解递推式转化为求解一个多项式的根和求解一组线性方程组，这样就使得整个求解过程不依赖于太多技巧，因此具有更好的易用性。

• 从抛硬币试验看概率论的基本内容及统计方法

这篇文章以抛硬币试验为引子引出了一系列现代数学中概率的基本模型、定理及基本的估计及显著性检验方法。写这篇文章是我无聊抛硬币时一时兴起，其中对很多东西只是给出一个轮廓，没有处处给出严格的定义和证明，不过大约说明了常用的一些统计方法及其理论基础，限于篇幅不能面面俱到，例如一个假设检验如果展开写可以单独写一篇文章。目前随着大数据概念的热炒，基于互联网的数据挖掘和机器学习也变得火热，其实很多数据挖掘和机器学习都是基于概率和统计理论的，很多方法甚至只是传统统计方法的应用。因此如果准备在这方面深入学习，不妨考虑先在概率论和数理统计方面打好基础。

• 为什么算法渐进复杂度中对数的底数总为2

在分析各种算法时，经常看到O(log2n)或O(nlog2n)这样的渐进复杂度。不知有没有同学困惑过，为什么算法的渐进复杂度中的对数都是以2为底？为什么没有见过O(nlog3n)这样的渐进复杂度？本文解释这个问题。

• 基数估计算法概览

基数估计算法使用很少的资源给出数据集基数的一个良好估计，一般只要使用少于1k的空间存储状态。这个方法和数据本身的特征无关，而且可以高效的进行分布式并行计算。估计结果可以用于很多方面，例如流量监控（多少不同IP访问过一个服务器）以及数据库查询优化（例如我们是否需要排序和合并，或者是否需要构建哈希表）。

• 聊聊如何检测素数

最近看到一则颇为有趣的新闻，说北大一名大一新生，以素数为标准选手机号，受到广大网友膜拜。其实素数的检测算法是很有趣的，并且会涉及到数论、概率算法等诸多内容，一直觉得素数探测算法是了解概率算法很好的入口。本文和大家简单聊聊如何确定一个数是素数。

• 浅析PageRank算法

这篇文章是我对一些资料的归纳汇总，简单介绍了PageRank的背景、作用、计算方法、变种、Spam及反作弊等内容。为了突出重点我简化了搜索引擎的模型，当然在实际中搜索引擎远没有这么简单，真实算法也一定非常复杂。不过目前几乎所有现代搜索引擎页面权重的计算方法都基于PageRank及其变种。因为我没做过搜索引擎相关的开发，因此本文内容主要是基于现有文献的客观总结，稍加一点我的理解。

• 发布一个查看PHP opcode的扩展模块及Web服务

最近花了大约一星期的时间写了一个PHP扩展模块Opdumer，并封装成了Web服务（点击这里访问）。这个模块的主要内容是输出PHP代码对应的opcode。其实之前已经有一些用于查看opcode的扩展模块，如比较有名的vld。之所以重新实现一个这样的模块，主要是因为vld不支持PHP_FUNCTION API，也就是说vld只能用于CLI形式，而Opdumer同时拥有CLI API和PHP_FUNCTION API，另外，也想借助编写这个模块的机会学习Zend Engine中opcode的编译和执行机制。个人打算后面专门针对opcode的编译执行机制写一篇文章，而本文主要描述Opcode的使用方法及对应Web服务的使用。

• PHP哈希表碰撞攻击原理

最近哈希表碰撞攻击（Hashtable collisions as DOS attack）的话题不断被提起，各种语言纷纷中招。本文结合PHP内核源码，聊一聊这种攻击的原理及实现。哈希表碰撞攻击的基本原理哈希表是一种查找效率极高的数据结构，很多语言都在内部实现了哈希表。PHP中的哈希表是一种极为重要的数据结构，不但用于表示Array数据类型，还在Zend虚拟机内部用于存储上下文环境信息（执行上下文的变量及函数均使用哈希表结构存储）。理想情况下哈希表插入和查找操作的时间复杂度均为O(1)，任何一个数据项可以在一个与哈希表长度无关的时间内计算出一个哈希值（key），然后在常量时间内定位到一个桶（术语bucket，表示哈希表中的一个位置）。

• 闭包漫谈（从抽象代数及函数式编程角度）

如果Google一下“闭包”这个词，会发现网上关于闭包的文章已经不计其数，甚至很多人将闭包看做面试JavaScript程序员的必考题（虽然闭包和JavaScript没有什么必然联系）。既然如此，我为什么还要写一篇关于闭包的文章呢？首先，虽然网上关于闭包的文章甚多，但是很少以较为形式化的角度阐述闭包，而我认为理解闭包的关键之一就是从形式化角度理解其涵义；其次，大多数文章将闭包的概念与JavaScript语言绑定太死，这样容易局限对闭包概念的理解，而难以窥探到其本质。从JavaScript去理解闭包，个人认为这是本末倒置的，应该先理解纯粹意义上的闭包，然后再理解JavaScript中的闭包机制。基于以上情况，本文将从较为形式化的角度阐述闭包概念，当做对现有网络的资料的一个补充。

• HTTP Server开发相关学习资料整理推介

本文整理了我在学习过程中接触到的一些与HTTP Server有关的资料、文章及书籍，在这里分享给大家，希望对大家有所帮助。 RFC及标准性文档 RFC2616 – Hypertext Transfer Protocol — HTTP/1.1 HTTP协议标准文档，所有从事HTTP相关开发的人员必备参考资料，建议仔细研读。 RFC793 – TRANSMISSION CONTROL PROTOCOL TCP协议标准文档。 The WWW Common Gateway Interface Version 1.1 CGI1.1协议标准文档，描述了Web Server与CGI Application通过CGI协议进行交互的所有细节。

• PHP Extension开发基础

这篇文章主要用示例方法介绍PHP Extension的开发基础。在PHP的使用中，也许是因为需要支持新的组件（如新的数据库），又或是业务需要或性能需要，几乎都会遇到需要开发PHP扩展的地方。后续如果有机会，我会写文章介绍一些关于扩展开发较为深入的东西，如扩展模块生命周期、INI使用以及编写面向对象的扩展模块等等。

• 如何使用PHP编写daemon process

今天下午在segmentfault.com看到一个提问，提问标题是“PHP怎么做服务化”，其中问道php是不是只能以web方式调用。其实很多人对PHP的使用场景都有误解，认为php只能用于编写web脚本，实际上，从PHP4开始，php的使用场景早已不限于处理web请求。从php的架构体系来说，php分为三个层次：sapi、php core和zend engine。php core本身和web没有任何耦合，php通过sapi与其它应用程序通信，例如mod_php就是为apache编写的sapi实现，同样，fpm是一个基于fastcgi协议的sapi实现，这些sapi都是与web server配合用于处理web请求的。但是也有许多sapi与web无关，例如cli sapi可以使得在命令行环境下直接执行php，embed sapi可以将php嵌入其它语言（如Lua）那样。