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

• 使用Jscex实现排序算法动画

用动画来观察排序算法是一件很酷的事情，例如有人便为各种排序算法提供了动画效果。只可惜这些效果都是实现准备好的gif图片，并非由代码写成。在大部分平台上编写这样的程序并没有太大困难，只要在绘制出图形之后短暂地阻塞线程就行了。可惜，在JavaScript中我们只能“一蹴而就”，要暂停的话，只能使用setTimeout进行回调了。不过，这也正是Jscex的用武之地，用Jscex编写的代码需要“暂停”，只需要简单地调用sleep异步方法，一切...

• 又一个有趣的面试题

大家还记得前些天的那个火柴棍式的面试题吗？很有趣吧。下面是我今天在StackExchange上看到的一个有趣的面试题。大家不妨一起来思考一下。问题如下―― 有两个相同功能代码如下，请在在A，B，C是什么的情况下，请给出三个原因case 1比case 2快，还有三个原因case 2会比case 1要执行的快。

• Lua GC 的源码剖析 (4)

今天来看一下 mark 过程是怎样实现的。所有的 GC 流程，都从 singlestep 函数开始。singlestep 就是一个最简单的状态机。GC 状态简单的从一个状态切换到下一个状态，循环不止。状态标识放在 global state 的 gcstate 域中。这一点前面以前谈过。开始的两个状态和 mark 过程有关。初始的 GCSpause 状态下，执行 markroot 函数。我们来看一下 markroot 的代码。

• Lua GC 的源码剖析 (2)

早期的 Lua GC 采用的是 stop the world 的实现。一旦发生 gc 就需要等待整个 gc 流程走完。如果你用 lua 处理较少量数据，或是数据增删不频繁，这样做不是问题。但当处理的数据量变大时，对于实时性要求较高的应用，比如网络游戏服务器，这个代价则是不可忽略的。lua 本身是个很精简的系统，但不代表处理的数据量也一定很小。从 Lua 5.1 开始，GC 的实现改为分步的。虽然依旧是 stop the world ，但是，每个步骤都可以分阶段执...

• 理解Heap Profling名词-Shallow和Retained Sizes

所有包含Heap Profling功能的工具（MAT, Yourkit, JProfiler, TPTP等）都会使用到两个名词，一个是Shallow Size，另一个是 Retained Size. 这是两个在平时不太常见的名词，本文会对这两个名词做一个详细的解释。 Shallow Size 对象自身占用的内存大小，不包括它引用的对象。针对非数组类型的对象，它的大小就是对象与它所有的成员变量大小的总和。当然这里面还会包括一些java语言特性的数据存储单元。

• 趣题：能否把三维空间分成无穷个圆？

这是一个非常经典的问题：是否存在无穷个互不相交的圆，它们并在一起就是整个三维空间？换句话说，能否用圆形既无重复又无遗漏地填满整个三维空间？我很早就见过这个问题。我第一次看到这个问题时，显然没能理解到这个问题的精妙之处。当时我在想，这不是显然可以吗？把三维空间想像成无穷个平行平面的并集，而每个平面又可以看作是由无穷多个同心圆组成的，这样一来整个空间不...

• Amazon S3 & Simpledb内部实现分析

Amazon S3申请了一篇专利，名称为”Keymap Service Architecture for A Distributed Storage System“，而Amazon Simpledb的实现细节暂时没有公开。本文根据Dynamo论文，S3专利以及S3&Simpledb的对外API尝试推测这两个系统的内部实现。

• 漫话折纸几何学

前几天，一篇叫做用正方形纸片折出等边三角形的日志引起大家的讨论，折出正七边形和折出角三等分线的方案更是让大家争论不休。提得最多的问题就是，折纸为什么要比尺规作图更强？这是一个好问题。我查了不少资料，了解到不少折纸几何的历史，收获颇大，不赶紧记下来就亏大了。于是有了这篇文章。要解答为何折纸如此强大，首先我们得解决一个问题：什么叫折纸。折纸的游戏规则...

• HFile存储格式

HFile， HBase中KeyValue数据的存储格式，HFile是Hadoop的二进制格式文件，实际上StoreFile就是对HFile做了轻量级包装，即StoreFile底层就是HFile。

• 另类称球趣题：验证砝码所标克数的正确性

有六个砝码，它们的重量分别是 1 克、 2 克、 3 克、 4 克、 5 克、 6 克。每个砝码上都标有这个砝码的重量，但由于生产过程中的疏忽，重量有可能被标错了。请你用天平称两次，来检验这些砝码所标克数是否完全正确。答案：先把标有 1 、 2 、 3 的砝码放在天平左边，把 6 放在天平右边。

• 打印质数的各种算法

打印质数的算法应该是学习计算机编程的一个经典的问题，在这里想给大家展示一些方法，相信这些方法会对你的编程有一定的启发作用。请你注意几点，实际应用和教学应用有很大的差别。最后的那个使用编译时而不是运行时的方法大家可以重点看看。

• 人脸识别算法综述-(LPP,PCA,K-L,SVM)

[摘要] 本文通过工业界世界级人脸测试，说明人脸识别发展现状，分别从二维、三维角度，阐述了人脸识别算法现状，并对人脸识别算法发展趋势予以说明。 [关键词] 人脸识别二维识别算法三维识别算法一、引言 1.人脸识别概述。人脸识别由于可接受性好，在生物识别领域得到较快的发展。人脸识别的研究范围广义上来讲大致包括以下五个方面的内容：人脸定位和检测、人脸表征(人脸特征抽取)、人脸鉴别、表情/姿态分析、生理分...

• m进制转换为n进制-任意进制转换算法

这种题也是一道经典的面试题，主要考察进制转换细想，Coding质量等。当我们把十进制转成二进制的时候，我们通过辗转相除，取余，逆置余数序列的过程得到新的进制的数。因此我们可以借助这种思想把M进制转成N进制的数。

• 一个Sqrt函数引发的血案

我们平时经常会有一些数据运算的操作，需要调用sqrt，exp，abs等函数，那么时候你有没有想过：这个些函数系统是如何实现的？就拿最常用的sqrt函数来说吧，系统怎么来实现这个经常调用的函数呢？虽然有可能你平时没有想过这个问题，不过正所谓是“临阵磨枪，不快也光”，你“眉头一皱，计上心来”，这个不是太简单了嘛，用二分的方法，在一个区间中，每...

• Objective-C Coding Style

一直一来我都没有找到详细明确的Objective-C Coding Style，这让我很苦恼，因为我很关心一些小细节，比如 “{” 的位置，到底应该把 { 和关键字/方法名放在一行： 1 2 3 if(condition){ }else{ } 还是应该把 { 另起一行： 1 2 3 4 5 6 if(condition) { } else { } 关于这两种写法，其实争议已久，一般来说都认为把 { 直接放在行尾可以节省屏幕空间

• 用正方形纸片折出等边三角形

给定一个正方形纸片，用上面这种方法可以折出一个等边三角形。你能看出这是为什么吗？由对称性，组成等边三角形的前两道折痕显然一样长，我们只需要证明它们之间的夹角是 60 度即可。注意到，如图折叠后将会立即产生直角边是斜边长度一半的直角三角形， 30 度角由此产生。由此可知，前两道折痕和纸片边上的夹角都是 15 度，两折痕之间的夹角自然也就正好是 60 度...

• 64位平台C/C++开发注意事项

例出了28个在64位平台上使用C/C++开发的注意事项，对于进入64位时代的程序员应该去看看这28个事项，这些英文读物对于有C/C++功底的朋友读起来应该并不难，我估计大约20-30分钟可以精读完一篇（或者更快），下面是这28个注意事项的列表。相信对大家一点有帮助。

• 当类型转换表达式遇上自定义转换操作

之前我提到说System.Json是一个十分不好用的类库，其中一点就是在于，我没法将一个JsonValue转化为范型类型――它只为Int32，String等几种特定类型定义了隐式转换，又无法得到以object类型所引用的值。不过这也难不到拥有“在运行时创建自定义表达式树并编译成动态代码”的.NET程序员。例如我们可以写这样一个辅助类进行JsonValue至任意类型的转化操作，.NET类库会负责为我们选择合适的转换方式。

• 情人节特献：有心之函数必然就有分手函数

首先，祝大家情人节快乐。不过，对于单身 Geek 来说，情人节或许并不快乐。情人节可以说是各种 Geek 们永久的伤痛了。即使是热爱数学的你，或许看到已经被转发到烂的“心之函数”今日再度走红，心中也会觉得不爽：我们发明出来的 Geek 玩物，竟然都被你们这些非 Geek 人士拿去装 Geek 泡妞用了，最终情人节宅在家里面向显示器编程度过平凡一天的反而还是我们这群 Geek 。

• DYNAMO平台的独门绝技：利用NWR模型与vector clock解决锁问题

DYNAMO平台的独门绝技：利用NWR模型与vector clock解决锁问题我们知道当系统系统为多用户时，就必须使用文件锁的机制来保护数据的完整性和一致性。举例A用户向数据区D1写了数据1，那么用户B和C都可以看到D1的数据为1，而当A，B同时在向数据区D1做加1的操作，就需要一个锁，让先发起的用户先操作，后发起的用户就需要在队列里面排队等待前面的用户完成操作，再继续进行。