Posts

工作2年 2011年的5月份，在杭州研究院的闪电邮项目已上线并作为稳定版本告一段落，组里人员开始被调配到其它项目，考虑到PC客户端产品的市场日渐式微，而且在网易这种游戏公司PC客户端只会作为战略产品或者辅助工具，很难有直接营收（那会闪电邮已经有百万用户量，网易邮箱用户的粘性非常高，超越Foxmail成为用户首选客户端）。在这种情况下，我开始考虑转型。那时方向有二，朋友推荐可以去支付宝数据基础平台部门，部门老大建议去公司新成立的雷电游戏工作室。考虑到留在网易，同事朋友和离家近，游戏项目是公司主业等因素下开始了又一段的苦逼之旅。 回头看那时的选择，我并不后悔选择游戏行业，只是叹息当时只关注了方向，而没仔细考察工作室的人员组成和产品经理资历。而当年在支付宝的那朋友升到了系统架构师，前年去了鹅厂。 ...

这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 我毫不犹豫的把这个算法称为“超酷”，虽然我自己发明了它，但我还是觉得它相当的酷，而且它很适合我算法系列的主题，所以无论如何要把它写下来。 ...

这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 作为开始，我假设你知道什么是排列，简单说就是按特定的顺序对序列进行洗牌。比如，值域1-10的排列为{5,2,1,6,8,4,3,9,7,10} 。一个安全的排列是攻击者即使有该排列的任意子集，都无法确定其它任何一个元素的顺序。这里有个简单的例子是使用一个安全加密的伪随机数生成器，用一个密钥作为种子，并用它来打乱你的序列。 如果你想生成一个非常非常大的排列，一个如此大的预计算和存储是不是不太现实？此外，你是否希望它是个安全序列？这里有个非常巧妙的方法，我们可以使用分组密码，使我们能够产生超过数值范围内的任何一个安全排列，而不必对它们进行预计算。 分组密码，没人不熟悉，它是密码学中一种常见的基础元素。它是由多块一定长度的密文组成，密文一般为64或128位的加密串。相同的密钥和相同的明文，它只可能生成相同的密文。超过一个块大小的信息使用一系列操作模式中的某一种方式加密，继而可以针对比单个块大许多的消息进行安全的加密和解密。使用分组密码加密，选择操作模式是至关重要的。为了能生成一个安全排列，无论如何，我们只打算每次加密单个块，所以我们不必担心操作模式。 如果你知道分组密码是如何运作的，你肯定能获得一个安全的排列。将给定长度的任意块（考虑下块的数量非常大的情况）用唯一的方式转换为另外一个块，且能将它再次转换回来。如果我们逐步加密更大的数字（1,2,3等等），我们保证能得到看上去随机的序列，只要不重复输入。这点很容易证明：假如它是重复的，那你会有两个输入数字被解码为同一个输出数字，这样就不可能有独一无二的解码。分组密码所持有的这些特性也正是对我们有用的特性。 你说，一切都挺好，但如果我想要一个不是2的幂次值域内的排列该如何？这里有个聪明的小技巧，就是取一个块长度略大于你想要的长度的分组密码，使用上面描述的方法，逐步加密序列中的更大数值，以产生排列中的元素。当加密后的值超出你想要的排列值域之外，只需再次加密。重复这样的方式直到你给到你想要的值域内的数值。同样，我们能保证分组密码的唯一性，并且我们也能保证（穷举方式）最终获得了一个理想值域内的数值。 很显然，在追寻这条路之前我们需要考虑一些因素。你要选择一个分组密码，是不是比你想生成的序列的值域要大，最好是2的幂次。密码值域和排列值域的比率确定了你运行的平均时间， 因此，如果密码是你排列的值域的四倍时，你就对每个值平均需要四次加密。这可能产生问题，因为大多数密码是64，128或者更多位。为了这个目的，我们找到适应性比较强的TEA加密算法，它很容易构造32,64,128或者更长位的变体，并且位操作在main主循环那很容易调整，也可产生4的幂次长度的密码，而无需将密码缩短至容易被暴力破解的长度。 另外值得一提的是，虽然这个技术的目的是生成非常大的安全排列，但对那些并不注重安全的排列同样有用 - 你的密钥可作为生成排列的随机种子。在许多情况下这种方法同样有帮助，基本上它是个映射函数可以用来索引排列的数值，这样你可以计算出该排列的任意子集的值。 最后，请记住，由于可能的排列数呈阶乘级增长，你的密钥空间肯定大大小于排列的数量。这个对于大多数应用可能并不重要，因为如此庞大的排列不可能一个个枚举过去。但是，如果你的密钥过短，它就有可能被攻击者利用枚举密钥的方式来找出可能生成的排列。 更新：Yossi Oren在评论里留了分优秀的论文连接。它涵盖了我的描述（当然更全面）。

这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 这是『超酷算法』系列的第一篇文章。基本上，任何一种算法我觉得都很酷，尤其是那些不那么明显简单的算法。 BK树或者称为Burkhard-Keller树，是一种基于树的数据结构，被设计于快速查找近似字符串匹配，比方说拼写检查器，或模糊查找，当搜索"aeek"时能返回"seek"和"peek"。为何BK-Trees这么酷，因为除了穷举搜索，没有其他显而易见的解决方法，并且它能以简单和优雅的方法大幅度提升搜索速度。 BK树在1973年由Burkhard和Keller第一次提出，论文在这《Some approaches to best match file searching》。这是网上唯一的ACM存档，需要订阅。更细节的内容，可以阅读这篇论文《Fast Approximate String Matching in a Dictionary》。 在定义BK树之前，我们需要预先定义一些操作。为了索引和搜索字典，我们需要一种比较字符串的方法。编辑距离（ Levenshtein Distance）是一种标准的方法，它用来表示经过插入、删除和替换操作从一个字符串转换到另外一个字符串的最小操作步数。其它字符串函数也同样可接受（比如将调换作为原子操作），只要能满足以下一些条件。 现在我们观察下编辑距离：构造一个度量空间（Metric Space），该空间内任何关系满足以下三条基本条件： d(x,y) = 0 <-> x = y (假如x与y的距离为0，则x=y) d(x,y) = d(y,x) (x到y的距离等同于y到x的距离) d(x,y) + d(y,z) >= d(x,z) 上述条件中的最后一条被叫做三角不等式（Triangle Inequality）。三角不等式表明x到z的路径不可能长于另一个中间点的任何路径（从x到y再到z）。看下三角形，你不可能从一点到另外一点的两侧再画出一条比它更短的边来。 编辑距离符合基于以上三条所构造的度量空间。请注意，有其它更为普遍的空间，比如欧几里得空间（Euclidian Space），编辑距离不是欧几里得的。既然我们了解了编辑距离（或者其它类似的字符串距离函数）所表达的度量的空间，再来看下Burkhard和Keller所观察到的关键结论。 假设现在我们有两个参数，query表示我们搜索的字符串，n表示字符串最大距离，我们可以拿任意字符串test来跟query进行比较。调用距离函数得到距离d，因为我们知道三角不等式是成立的，所以所有结果与test的距离最大为d+n，最小为d-n。 由此，BK树的构造就相当简单：每个节点有任意个子节点，每条边有个值表示编辑距离。所有子节点到父节点的边上标注n表示编辑距离恰好为n。比如，我们有棵树父节点是"book"和两个子节点"rook"和"nooks"，“book"到"rook"的边标号1，“book"到"nooks"的边上标号2。 从字典里构造好树后，取任意单词作为树的根节点。无论何时你想插入新单词时，计算该单词与根节点的编辑距离，并且查找数值为d(neweord, root)的边。递归得与各子节点进行比较，直到没有子节点，你就可以创建新的子节点并将新单词保存在那。比如，插入"boon"到刚才上述例子的树中，我们先检查根节点，查找d(“book”, “boon”) = 1的边，然后检查标号为1的边的子节点，得到单词"rook”。我们再计算距离d(“rook”, “boon”)=2，则将新单词插在"rook"之后，边标号为2。 在树中做查询，计算单词与根节点的编辑距离d，然后递归查找每个子节点标号为d-n到d+n（包含）的边。假如被检查的节点与搜索单词的距离d小于n，则返回该节点并继续查询。 BK树是多路查找树，并且是不规则的（但通常是平衡的）。试验表明，1个查询的搜索距离不会超过树的5-8%，并且2个错误查询的搜索距离不会超过树的17-25%，这可比检查每个节点改进了一大步啊！需要注意的是，如果要进行精确查找，也可以非常有效地通过简单地将n设置为0进行。 回顾这篇文章，写的有点长哈，似乎比我预期中的要复杂。希望你在阅读之后，也能感受到BK树的优雅和简单。

这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 假如你在网上搜最好的C++源代码。「毁灭战士3 | Doom 3」的源代码肯定会被提到好多次，这篇就来证明此事。 我花了一些时间通读了 DOOM3 的源代码。这可能是我见过的最干净最漂亮的代码了。DOOM3是id Software公司开发 Activision发行的视频游戏。该游戏为id Software赢得了商业上的成功，已售出350万多份拷贝。 在2011年11月23日，id Software维持开源传统，发布了他们上一个引擎的源代码。这份源代码已经被很多开发者审查，这里就有个fabien反馈的例子（链接）： DOOM3 BFG是用C++写的，一种庞大的语言，它既能写出优秀的代码，但也让人憎恶到眼睛流血。幸运的是，id Software退而求其次，使用C++子集，接近于“带类的C”，如以下几条约束： 没有异常 没有引用（使用指针） 少用模板 使用常量（Const everywhere） 类 多态 继承 很多C++专家不建议使用“带类的C”这样的方法。然而，DOOM3从2000开发至2004，没有使用任何现代C++机制。 让我们使用 CppDepend 来看看源代码，探索它得特别之处。 DOOM3有少量的几个工程组成，这儿有它的工程列表和一些类型统计。 这里还有他们之间的依赖关系图： DOOM3定义了很多全局函数。但是，大部分内容实现是在类中。 数据模型使用结构体定义。为了在源代码中对结构体的使用有个更具体的理解，在下图中将它们以蓝色分块显示出来。 在图表中，代码被表示为树形图，树形图表示法能使用嵌套的矩形来表示树状结构。而树结构用来表示代码分层结构。 工程包含命名空间。 命名空间包含类型。 类型包含函数和域（field）。 我们可以观察到它定义了许多的结构体，比如DoomDLL 40%的类型都是结构体。它们被有条理地用来定义数据模型。该实践已经被很多工程所接受，这种方法有个最大的缺点是多线程应用，结构体的public变量并非不可改变的。 为何支持不可变对象，有个重要原因：能显著地简化并发编程。考虑下，写个合格的多线程程序是个艰巨的任务吗？因为很难同步线程访问资源（对象或者其他OS资源）。为什么同步这些操作很困难呢？因为很难保证在资源竞争状态下多线程对多个对象进行正确的读写操作。假如没有写操作呢？换句话说，线程只访问这些对象，而不做任何变动？这样就不再需要同步操作了！ 让我搜索下只有一个基类的类： 几乎40%的结构体和类都只有一个基类。通常，OOP（面对对象编程）使用继承的好处之一是多态，下面蓝色标明了源代码中的虚函数： 超过30%的函数是虚函数。少数是纯虚函数，下面是所有虚基类列表： 只有52个类被定义为虚基类，其中35个类只是纯接口，也就是这些接口都是纯虚函数。 我们来搜搜使用了RTTI的函数 只有非常少的函数使用了RTTI。 为保证只使用OOP最基础的概念，不使用高级设计模式，不过度使用接口和虚基类，限制了RTTI的使用并且数据都定义为结构体。 至此这份代码跟很多C++开发者所批评的“带类的C”没太大区别。 其开发者的一些有趣的选择，帮助我们理解它的奥秘： 1-为有用的服务提供公用的基础类。 许多类是从idClass继承下来的： idClass提供如下服务： 创建实例化 类型管理 事件管理 2-方便的字符串操作 一般来说，字符串是一个项目里用的最多的对象，许多地方需要使用它，并且需要函数来对其进行操作。 DOOM3定义了idstr类，几乎包含了所有用的字符串操作函数，无需再自己定义函数来接受其它框架所提供的字符串类。 3-源代码与GUI框架（MFC）高度解耦 很多工程用了MFC后，它的代码就会与MFC类型高度耦合，并且在代码的任何一处都能发现MFC类型。 在DOOM3里，代码和MFC是高度解耦的，只有GUI类才会直接依赖它。下面的CQLinq查询可以展示这点： 这样的选择对生产力有很大的影响。事实上，只有GUI开发者才会关心MFC框架，其它开发者不应该被强制在MFC上浪费时间。 4-提供了非常好的公共函数库（idlib） 几乎在所有项目中都会用到公共工具类，就如以下查询的结果： 正如我们所看到经常使用的就是公共工具类。假如C++开发者不使用一个良好的公共工具框架，那就会为解决技术层面问题花费大部分的开发时间。...

这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 假如你对数独解法感兴趣，你可能听说过精确覆盖问题。给定全集 X 和 X 的子集的集合 Y ，存在一个 Y 的子集 Y*，使得 Y* 构成 X 的一种分割。 这儿有个Python写的例子。 X = {1, 2, 3, 4, 5, 6, 7} Y = { 'A': [1, 4, 7], 'B': [1, 4], 'C': [4, 5, 7], 'D': [3, 5, 6], 'E': [2, 3, 6, 7], 'F': [2, 7]} 这个例子的唯一解是['B', 'D', 'F']。 精确覆盖问题是NP完备（译注：指没有任何一个够快的方法可以在合理的时间内，意即多项式时间 找到答案）。X算法是由大牛高德纳发明并实现。他提出了一种高效的实现技术叫舞蹈链，使用双向链表来表示该问题的矩阵。 然而，舞蹈链实现起来可能相当繁琐，并且不易写地正确。接下来就是展示Python奇迹的时刻了！有天我决定用Python来编写X 算法，并且我想出了一个有趣的舞蹈链变种。 算法 主要的思路是使用字典来代替双向链表来表示矩阵。我们已经有了 Y。从它那我们能快速的访问每行的列元素。现在我们还需要生成行的反向表，换句话说就是能从列中快速访问行元素。为实现这个目的，我们把X转换为字典。在上述的例子中，它应该写为 X = { 1: {'A', 'B'}, 2: {'E', 'F'}, 3: {'D', 'E'}, 4: {'A', 'B', 'C'}, 5: {'C', 'D'}, 6: {'D', 'E'}, 7: {'A', 'C', 'E', 'F'}} 眼尖的读者能注意到这跟Y的表示有轻微的不同。事实上，我们需要能快速删除和添加行到每列，这就是为什么我们使用集合。另一方面，高德纳没有提到这点，实际上整个算法中所有行是保持不变的。...