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

在Linux 2.4 IPv4 FIB的数据结构基础上实现IPv6的FIB是否可行呢？如果读了我前面这篇文字你应该会有一个判断。IPv4的FIB实现可以说有些拙劣，如果照搬一个IPv6版本，最差情况下需要进行128次hash key计算这还不包括链表的查找过程。看了一下Linux 2.6的IPv6 FIB实现，已经有了调整，用了Patrix(Radix)树实现了这个算法，下面是一些背景知识：首先是Trie树，下图是Wiki http://en.wikipedia.org/wiki/Trie 之中的一个例子 Trie树，尤其是二叉Trie树属于：是一直被使用，从未被(教科书)重视的东东。其特点是键值的内容成为树的检索路径，例如上图的to，tea等几条键值标明的路径。如果要对trie分类的话，我想只能按照出度来分类，上图假定键值的每一字节取值a-z，则这个trie是26叉trie树，最小

• 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList

List是工程师的基本功，这里并不描述list增删这些细节的内容，仅仅根据我的理解写一下工程中List库的设计和实践考量。看过几个不同的list库的实现，基本上涉及到如下的设计考量： 1.List数据结构上的差异有没有头结点，是否循环，是否双向。这样就有多种组合，不罗嗦。 2.list的读写的保护。 3.List直接指针遍历还是仿照STL的Iterator方式遍历。 4.List同实际用户数据是采取一体式还是干湿分离式。 5.系统对于数据结构和算法的影响 1.从数据结构上将，Linux Kernel之中的List是双向无头节点链表。空链表如下：非空链表如下：我觉得维护头结点的理由之一就是可以存放list size，而无需用户在应用部分进行维护。如果没有list size，用户需要在List删减的结束的时候维护list size，如果不愿意如此麻烦，只能悲催的在需要读取

• 开源世界中的算法与数据结构 2 -- Linux Skbuff实现

兼回忆贴，大概在03年开始接触Linux的协议栈代码，那个时候还找不到什么参考书，有些东西自己搞明白了但是也从来没想过在那个论坛发个帖子什么的，也没有现在的记录总结的习惯. 后来有一本08年版的《TCP/IP Architecture, Design and Implementation in Linux》其中解析了Linux2.4 协议栈的多数代码，其中第五章专门涉及skbuff的代码实现讲解，非常详细，这个小短文不翻译整个章节，各种网文很多，只是想根据关键部分说一下我理解的设计背后的原因。 skbuff的形态1 上面是最基本的一个sk_buff了，一个TCP报文的skbuff示意图，这里隐含着一些内容：报文分析的标准模式 skbuff采用的大块控制结构对象指向数据区是标准的实现模式，例如BSD这样的OS以及工程实现中都是这样的。参数的集中与其提供多个对象或者多个参数保存

• 开源世界中的算法与数据结构 1 -- Linux FIB实现

在Linux2.4的时候，对于Linux的FIB表有些研究。凭着残存的记忆和code，恢复一下FIB的数据结构。首先扫盲一下几个路由协议架构相关的概念：上图为路由协议的基本架构，相关内容在Cisco出版社出版的某一本图书上有概念描述，大概是《Routing TCP》。 1．每个路由协议根据自己收集到的路由信息产生内部的路由表。所有的路由协议的路由信息汇聚到统一的RIB之中。 2． RIB的管理模块根据RIB之中的路由条目按照优先级优选出实际用于转发的路由下发到FIB之中。 3．最终在Packet到来的时候，系统查找FIB表做路由查找。对于FIB的主要需求有两个： 1. 组织和存储选出的路由表项。 2. 按照LPM(最长掩码匹配)算法提供路由检索接口。下图是Linux24之中的FIB表中几个主要的数据对象的数据结构关系。具体字段不做解释，最终的目的就是找到dn_fib_n

• Riak Core说明

riak_core是一个单独的OTP应用，提供了所有必须的服务，以完成一个现代化的、表现良好的分布式应用。riak_core开始于Riak的一部分。当代码在建立各种分布式应用普遍有用时，我们决定重构并且分离出来核心部分，使其便于使用。分布式系统是复杂的，riak_core可以满足这些大量复杂的需求。在深入代码之前，我将分离这些需求为明显的分类，且给出每项的概况。注：如果你是急性子，想跳过后面的直接读代码，你可以通过hg或者git检出riak_core的代码。节点存活 & 节点关系 riak_core_node_watcher是负责反馈riak_core_cluster内部节点状态的进程。它使用net_kernel有效地监控了许多节点。riak_core_node_watcher也有能力将一个节点按程序预定踢出clus

• Ameba , 一个简单的 lua 多线程实现

几个月以前，在我在 blog 上曾谈及 Lua 5.2 的改进。它可以用来实现抢占式多线程。周末休息，我把这桩事挖出来娱乐一下，花了一整个晚上做了实现。把 lua 的每个线程锁定在独立的 lua state 中，强迫线程之间通过消息管道的方式通讯。经过测试，Lua 5.2 每个独立的 state 占用的内存很小。通过自定义 alloc 函数可以测算出，一个干净的 32bit state ，不含任何库函数时，占用内存量在 2K 以下(1726 bytes)。如果加载基本库，也仅仅占用不到 4K (3265 bytes)。若把所有 lua 官方标准库加载进来，才会上升到 10K 以上(12456 bytes)。对于 luajit 2 ，这个基础开销会大一些，最小开销也在 10K 左右 (8058 bytes) 。加上 ffi 达到 30k (31605 bytes)。不过 ffi 可

• MMORPG 中场景服务的抽象

MMORPG 中，场景信息同步是很基础而必不可少的服务。这部分很值得抽象出来，专门做成一个通用的服务程序。此服务无非提供的是，向有需求的对象，同步场景中每个实体的状态信息。那么，我们分解需求，可以看到两点，一是提交状态，二是同步状态。每条状态信息其实是由三部分构成，状态对象名(key)、状态值(value)、时间。玩家、NPC、场景中的可变物品，其实都有可改变的状态。比如对象的位置坐标是最常见的状态。其它的状态还有玩家或 NPC 做的动作，玩家离线，上线，等等。可以有若干数据源向这个服务提供数据，如果借用 zeromq 中的模式的话，这个服务应该使用一个 PULL socket 收集数据。它获取从不同数据源 PUSH 来的，key-value 。然后打上时间戳，储存在内存中。这个服务另外提供一个发布服务，向所有订阅者广播其收到的状态改变信息，每条信息包括推送来的 key-

• 一些有意思的算法代码

Keith Schwarz是一个斯坦福大学计算机科学系的硕士研究生。他对编程充满了热情。他的主页上他自己正在实现各种各样的有意思的算法和数据结构，http://www.keithschwarz.com/interesting/，目前这个网页上有88个（见下面的列表），但这位大哥要干135个，你可以看看他的To-Do List。从这个列表上，我们可以看到，他从去年7月份就在自己实现这些东西了，我把他实现的这些算法转过来，一方面我们可以学习一下这些算法和代码，因为很多东西对我来说都比较新，我以前列举过一些经典的算法，算法和数据结构词典，还有可视化的数据结构和算法，不过感觉都没有这个全。另一方面我希望这个事可以影响到一些正在学习编程的人。看看别人是怎么学习编程的，希望对你有借鉴作用。

• 经典证明：不断把凹的部分翻出来，总能把凹多边形变凸吗？

左图是一个凹多边形，而且凹得相当厉害。作为一个完美主义者，我很难容忍这么一个图形，总想着要把凹进去的部分翻出来，把它还原为一个凸多边形。不幸的是，翻折之后的结果仍然不是凸多边形，图中又产生了新的凹陷。于是，我们想继续把凹进去的部分往外翻，直到整个图形变成凸多边形为止。问题是，这个过程有完吗？换句话说，我们一定能通过有限多步翻折，把凹多边形变成凸的吗？这个问题有着非常纠结复杂的历史。这个问题最早可能是由数学家 Paul Erd\"os 正式提出的。 1935 年，他在 American Mathematical Monthly 上猜想，经过有限步翻折之后，凹多边形一定能变凸。 1939 年， Béla Sz\"okefal

• Fibonacci数列性质的组合证明

数列 1, 1, 2, 3, 5, 8, 13, 21, 34, … 叫做 Fibonacci 数列。这个数列有很多神奇的性质，其中一个性质是，每一个 Fibonacci 数的平方与它前后两个 Fibonacci 数的乘积相比一定正好相差 1 。具体地说，如果把第 n 个 Fibonacci 数记做 Fn ，那么有： Fn+1 · Fn+1 - Fn · Fn+2 = (-1)n 今天看到了这个定理的一个组合数学证明，觉得非常有意思，在这里和大家分享。 Fibonacci 数有很多组合数学上的意义。比如说，用 1 × 1 和 1 × 2 的积木覆盖一个 1 × n 的棋盘，总

• 游戏数值策划

这篇很淡疼的文章来源于我在微博上的争论。需要列数据，字数限制不合适，所以单列一篇了。昨天翻出了元帅同学的一篇旧文，游戏数值设计(1)：定义与目标 , 转发到微博上。我一向是喜欢看他吐槽的，这篇吐国内的 MMORPG 游戏策划分工的文章，深得我心。我一直对国内 MMORPG 制作把设计人员分为文案策划、系统策划、数值策划不以为然。文案拆分出去做倒还说得过去，这所谓系统策划和数值策划的拆分简直就是莫名其妙了。现代电子游戏从桌面游戏一路发展过来，怎样让玩家享受规则，一直是一个整体。如果一个人来设计一个游戏，那么脑子里必然要逐步形成这个游戏做出来是什么样子的，然后细化里面的细节，玩家在他设计的规则下怎么进行游戏。所谓数值设计，是这些细节里重要的一部分。很难想像，一个设计人员来想游戏的玩法，然后说细节我不管了，有另一个人来负责就好了。然后再有一个人专心于填写 excel 表格，用加加减

• Protocol Buffers for C

我一直不太满意 google protocol buffers 的默认设计。为每个 message type 生成一大坨 C++ 代码让我很难受。而且官方没有提供 C 版本，第三方的 C 版本也不让我满意。这种设计很难让人做动态语言的 binding ，而大多数动态语言往往又没有强类型检查，采用生成代码的方式并没有特别的好处，反而有很大的性能损失(和通常做一个 bingding 库的方式比较)。比如官方的 Python 库，完全可以在运行时，根据协议，把那些函数生成出来，而不必用离线的工具生成代码。去年的时候我曾经写过一个 lua 版本的库。为了独立于官方版本，我甚至还用 lpeg 写了一个 .proto 文件的解析器。用了大约不到 100 行 lua 代码就可以解析出 .proto 文件内的协议内容。可以让 lua 库直接加载文本的协议描述文件。(这个东西这次帮了我大忙)

• 2011年度最变态的迷宫难题

下面大家将会看到的是一个极其简单而又极其复杂的“迷宫”，这无疑是我在本年度见到的最变态的谜题：从左边入口处的 2011 进去，在迷宫里转悠，最后变成 2012 从右边出来。你可以在迷宫里转圈，可以重复之前走过的路，但不能往回退着走。你能成功走出来吗？

• 基于主特征空间相似度计算的切分算法及切分框架

摘要: 本文从切分的需求、作用、难点等方面谈起，介绍分析了目前主流的各种切分方法以及其优缺点，并介绍了一个新型的无监督切分方法，并在此基础上对切分在工程需求上进行了相应的分析和讨论，在最后在此算法基础上给出一个融合各种优点的切分框架。关键词: 中文分词， Query Segmentation，无监督技术领域: 自然语言处理我们为什么要切分？说到切分(segmentation)，大多数人最容易想到的就是中文分词。作为没有天然空格区分的语言，切词可以帮助计算机去索引文章，从而便于信息检索等方面。该部分主要用到了分词的一个方面：降低搜索引擎的性能消耗。我们常用的汉字有5000多个，常用词组是几十万个。在倒排索引中，如果用每个字做索引的话，那么会造成每个字对应的拉链非常长。所以我们一般会用词组来代替单个汉字建立索引。除此，切词更重要的一个功能是帮助计算机理解文字，在这个层次上，切词是不分

• 搜索引擎中的粒度问题

一.前言传统的搜索引擎的定义，是指一种对于指定的查询（Query），能够返回与之相关的文档集合（Documents）的系统。而百度将这个定义更加丰富化，即搜索引擎能够帮助人们更方便的找到所求。这里的“所求”，比“文档”更加宽泛和丰富，比如一个关于天气的查询，直接返回一个天气预报的窗口，而非一篇关于天气的文档；再如一个关于小游戏的查询，直接返回这个小游戏的Flash页面而非简单的介绍性的文字。百度对Query深刻的理解，源于自然语言处理技术在其中发挥的巨大作用。对搜索引擎而言，文本切分是最基础也是最重要的自然语言问题之一。今天，我们就来谈谈文本切分粒度与搜索引擎的关系。本文后续章节组织如下：第二节介绍什么是文本的粒度，第三节讲述搜索引擎的基本原理与文本切分粒度的关系，第四节深入探讨粒度的属性与检索相关性计算，第五节小结。二.文本粒度什么是文本的粒度？我们用什么来衡量文本粒度？在回

• 趣题：舞台里的狮子

有一个半径为 10 米的圆形舞台，初始时舞台上的某个地方有一头狮子。这头狮子在舞台上以折线段的方式跑了 30 千米。求证：在整个过程中，这头狮子至少转了 2998 个弧度。有时候，换一个角度思考，问题就会迎刃而解。现在，让我们站在狮子的角度，用狮子的眼光来看周围的世界。这样的话，狮子本身就是静止不动的，运动的其实是整个舞台；再假设狮子的头也是始终朝北的，狮子原地旋转实际上就是整个舞台绕着它做圆周运动。这样一来，舞台中心的运动就只有两种形式：竖直向下的直线运动，以及以狮子为中心的圆弧运动。如下图，左图就是在我们看来，狮子的移动轨迹，其

• gen_tcp接受链接时enfile的问题分析及解决

最近我们为了安全方面的原因，在RDS服务器上做了个代理程序把普通的MYSQL TCP连接变成了SSL链接，在测试的时候，皓庭同学发现Tsung发起了几千个TCP链接后Erlang做的SSL PROXY老是报告gen_tcp:accept返回{error, enfile}错误。针对这个问题，我展开了如下的调查：首先man accept手册，确定enfile的原因，因为gen_tcp肯定是调用accept系统调用的: EMFILE The per-process limit of open file descriptors has been reached. ENFILE The system limit on the total number of open file

• 基站轨迹定位算法

前言我在哪？是LBS领域首先要解决的问题。因为技术限制，传统的GPS卫星定位只有室外的空旷地区才能够准确定位，对于室内环境来说，GPS定位往往会因“搜星”失败而无法定位。正因为GPS定位的天然缺陷，基于手机基站的定位技术正在蓬勃发展。然而因为基站的覆盖范围大，很难以取得高精度的效果，本文利用基站轨迹，提出了一个提高基站定位精度的方法。关键字：基站定位，轨迹定位，Viterbi算法绪论对于单基站定位，如果仅根据用户当前的基站ID进行定位，精度必定有限。用户可能出现在基站覆盖范围内的任意一个地方，基站的覆盖范围越大，推测出来的用户位置就越不准。如果我们还知道用户之前一段时间内经过的基站ID序列（称为基站轨迹），此时即可大致判定用户行动轨迹，可借此提高精度。例举一个简单例子: 如上图所示，假设用户在一瞬间，基站ID从A切换到了B，此时用户属于B基站，单单从B这一个基站考虑的话，很

• 受禁锢的异步编程思维

最近一直在努力推广Jscex，补充了很多中文文档和示例，因此博客上都已经有两篇文章有了“上”而没有“下”，即使最复杂的图示也已经绘制完毕。在推广Jscex的过程中，我发现有个比较明显的问题是，许多使用JavaScript的程序员已经习惯旧有的编程方式，甚至推崇一些据他们说很“漂亮”的模式。但在我看来，这其实跟许多GoF模式是在修补OO语言的不足有些类似，很多异步模式都只是因为JavaScript语言特性不足而设计出来的“权宜之计”。我们在传统JavaScript编程环境下并没有其他选择，单纯地认为这是“美”，说实话只不过是一种安慰罢了。 Jscex的重头戏便是处理异步操作，但异步操作并不只是如Node.js中通过回调函数传回结果的那些方法，或者是网页上的AJAX请求等等。异步操作的定义其实可以概括成“会在未来某个时刻完成的操作”，就只是这么简单。什么事情会在未来发生，那么它对你来说就是个

• 累积发送模式

Droplet写过一些Network应用实现的模式，鉴于网络设备的复杂性，还有不少D还没有囊括进去，我这里补充一种累积下发模式：其实很简单，如果发送方有很多小的消息需要发送，延迟一会儿累积一些消息一并发送。这里一般有两个条件会触发发送： 1.在消息积累到一定数量的时候，超过Threshold的时候发送累积消息。 2.在消息没有达到threshold，但是经过一定超时时间的时候，也发送。这个模式很常用，其实熟悉TCP协议的人会想到Nagle算...