Algorithm | 酷壳

Cuckoo Filter：设计与实现

2015年09月02日 Leo 评论 37 条评论 77,434 人阅读

对于海量数据处理业务，我们通常需要一个索引数据结构，用来帮助查询，快速判断数据记录是否存在，这种数据结构通常又叫过滤器(filter)。考虑这样一个场景，上网的时候需要在浏览器上输入URL，这时浏览器需要去判断这是否一个恶意的网站，它将对本地缓存的成千上万的URL索引进行过滤，如果不存在，就放行，如果（可能）存在，则向远程服务端发起验证请求，并回馈客户端给出警告。

索引的存储又分为有序和无序，前者使用关联式容器，比如B树，后者使用哈希算法。这两类算法各有优劣：比如，关联式容器时间复杂度稳定O(logN)，且支持范围查询；又比如哈希算法的查询、增删都比较快O(1)，但这是在理想状态下的情形，遇到碰撞严重的情况，哈希算法的时间复杂度会退化到O(n)。因此，选择一个好的哈希算法是很重要的。

时下一个非常流行的哈希索引结构就是bloom filter，它类似于bitmap这样的hashset，所以空间利用率很高。其独特的地方在于它使用多个哈希函数来避免哈希碰撞，如图所示（来源wikipedia），bit数组初始化为全0，插入x时，x被3个哈希函数分别映射到3个不同的bit位上并置1，查询x时，只有被这3个函数映射到的bit位全部是1才能说明x可能存在，但凡至少出现一个0表示x肯定不存在。

Bloom_filter

…

阅读全文 Read More

(53 人打了分，平均分： 4.15 )

Leetcode 编程训练

2014年10月23日陈皓评论 97 条评论 202,531 人阅读

LeetCodeLogo (1) Leetcode这个网站上的题都是一些经典的公司用来面试应聘者的面试题，很多人通过刷这些题来应聘一些喜欢面试算法的公司，比如：Google、微软、Facebook、Amazon之类的这些公司，基本上是应试教育的功利主义。

我做这些题目的不是为了要去应聘这些公司，而是为了锻炼一下自己的算法和编程能力。因为我开始工作的时候基本没有这样的训练算法和编程的网站，除了大学里的“算法和数据结构”里的好些最基础最基础的知识，基本上没有什么训练。所以，当我看到有人在做这些题的时候，我也蠢蠢欲动地想去刷一下。

于是，我花了3-4个月的业余时间，我把Leetcode的154道题全部做完了。（这也是最近我没有太多的时间来写博客的原因，你可以看到我之前做的那个活动中有几个算法题来自于Leetcode）有人说我时间太多了，这里声明一下，我基本上都是利用了晚上10点以后的时间来做这些题的。

LeetCode的题大致分成两类：

1）基础算法的知识。这些题里面有大量的算法题，解这些题都是有套路的，不是用递归（深度优先DFS，广度优先BFS），就是要用动态规划（Dynamic Programming），或是拆半查找（Binary Search），或是回溯（Back tracing），或是分治法（Divide and Conquer），还有大量的对树，数组、链表、字符串和hash表的操作。通过做这些题能让你对这些最基础的算法的思路有非常扎实的了解和训练。对我而言，Dynamic Programming 是我的短板，尤其是一些比较复杂的问题，在推导递推公式上总是有思维的缺陷（数学是我的硬伤），通过做了这些题后，我能感到我在DP的思路上有了很大的收获。

2）编程题。比如：atoi，strstr，add two num，括号匹配，字符串乘法，通配符匹配，文件路径简化，Text Justification，反转单词等等，这些题的Edge Case, Corner Case有很多。这些题需要你想清楚了再干，只要你稍有疏忽，就会有几个case让你痛不欲生，而且一不小心就会让你的代码会写得又臭又长，无法阅读。通过做这些题，可以非常好的训练你对各种情况的考虑，以及你对程序代码组织的掌控（其实就是其中的状态变量）。还记得我在《函数式编程》中说的，程序中的状态是你程序变得复杂难维护的直接原因。

我觉得每个程序员都应该花时间和精力做这些题，因为你会从这些题中得到很大的收益。做完这些题后你一定会明白下面几个道理：

…

阅读全文 Read More

(111 人打了分，平均分： 4.47 )

谜题的答案和活动的心得体会

2014年08月06日陈皓评论 98 条评论 67,670 人阅读

我于2014年8月3日周六的上午在微博、twitter、CoolShell上发布了一个和程序员有关的解谜题的活动——【活动】解谜题送礼物。我使用了二级域名fun.coolshell.cn做为这次活动的页面。

截止这篇文章发布的时候，fun.coolshell.cn的访问量UV大约有4万左右，通关人数大约有200人，但因为在活动的第二天网上就出了一些答题攻略，通过分析，实际靠自己能力通过的人数在130人左右。通过率大约不到4‰的样子。

在这里我把整个谜题和做这个活动的东西写一下，算是给自己的一个总结。

谜题的答案和花絮

fun.coolshell.cn上一共有十道谜题，要设计这些东西还真是费尽脑汁，这让我对那些设计谜题式游戏的人相当敬佩。

…

阅读全文 Read More

(57 人打了分，平均分： 4.25 )

【活动】解迷题送礼物

2014年08月03日陈皓评论 107 条评论 54,833 人阅读

首先，先跟大家道歉一下最近CoolShell大约长达一个多月没有什么更新，原因主要在于，我去看世界杯去了，这一个月的世界杯熬夜看球使我的精力不佳，导致世界杯结束后的几个星期也没有缓过来，所以没有更新什么文章。好多朋友写邮件或是在微博上at我催我更新，所以有点惭愧了。

精神不佳我就不写文章了。于是，世界杯过后，我每天都会抽出每天晚上和周末的一些碎片时间，我仿照一些前端过关的游戏，做了几个和程序员有关的迷题，也是要通关的，不过和前端知识没什么关系。这个游戏我放到了下面这个二级域名下。

http://fun.coolshell.cn/

有兴趣的朋友可以去玩玩。通关的同学我会送你们《Unix环境高级编程（第三版）》（感谢@出版圈郭志敏赞助）或一个马克杯（感谢@linux命令行精选网赞助）），因为奖品数量有限，所以，我会送给前十个通关的同学（后面通关的我会随机抽几个）。

…

阅读全文 Read More

(47 人打了分，平均分： 4.02 )

二维码的生成细节和原理

2013年10月29日陈皓评论 166 条评论 429,994 人阅读

二维码又称QR Code，QR全称Quick Response，是一个近几年来移动设备上超流行的一种编码方式，它比传统的Bar Code条形码能存更多的信息，也能表示更多的数据类型：比如：字符，数字，日文，中文等等。这两天学习了一下二维码图片生成的相关细节，觉得这个玩意就是一个密码算法，在此写一这篇文章，揭露一下。供好学的人一同学习之。

关于QR Code Specification，可参看这个PDF：http://raidenii.net/files/datasheets/misc/qr_code.pdf

基础知识

首先，我们先说一下二维码一共有40个尺寸。官方叫版本Version。Version 1是21 x 21的矩阵，Version 2是 25 x 25的矩阵，Version 3是29的尺寸，每增加一个version，就会增加4的尺寸，公式是：(V-1)*4 + 21（V是版本号）最高Version 40，(40-1)*4+21 = 177，所以最高是177 x 177 的正方形。

下面我们看看一个二维码的样例：

…

阅读全文 Read More

(105 人打了分，平均分： 4.41 )

伙伴分配器的一个极简实现

2013年10月09日 Leo 评论 55 条评论 76,112 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

提起buddy system相信很多人不会陌生，它是一种经典的内存分配算法，大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现，而仅仅是将该算法抽象提取出来，同时给出一份及其简洁的源码实现，以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”，即将内存按2的幂进行划分，相当于分离出若干个块大小一致的空闲链表，搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并（O(logN)时间复杂度）以及低外部碎片（最佳适配best-fit）；其缺点是内部碎片，因为按2的幂划分块，如果碰上66单位大小，那么必须划分128单位大小的块。但若需求本身就按2的幂分配，比如可以先分配若干个内存池，在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述，大体如是：

分配内存：

1.寻找大小合适的内存块（大于等于所需大小并且最接近2的幂，比如需要27，实际分配32）

1.如果找到了，分配给应用程序。
2.如果没找到，分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度，分配这个大小。
3.回溯到步骤1（寻找合适大小的块）
4.重复该步骤直到一个合适的块

…

阅读全文 Read More

(33 人打了分，平均分： 3.82 )

二叉树迭代器算法

2013年07月14日 Todd 评论 54 条评论 46,806 人阅读

（感谢 @文艺复兴记（todd）投递此文）

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题，基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下：

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法：

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是，仅有遍历算法是不够的，在许多应用中，我们还需要对遍历本身进行抽象。假如有一个求和的函数sum，我们希望它能应用于链表，数组，二叉树等等不同的数据结构。这时，我们可以抽象出迭代器(Iterator)的概念，通过迭代器把算法和数据结构解耦了，使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为：

…

阅读全文 Read More

(25 人打了分，平均分： 3.04 )

程序算法与人生选择

2012年12月28日陈皓评论 220 条评论 195,588 人阅读

每年一到要找工作的时候，我就能收到很多人给我发来的邮件，总是问我怎么选择他们的offer，去腾讯还是去豆瓣，去外企还是去国内的企业，去创业还是去考研，来北京还是回老家，该不该去创新工场？该不该去thoughtworks？……等等，等等。今年从7月份到现在，我收到并回复了60多封这样的邮件。我更多帮他们整理思路，帮他们明白自己最想要的是什么。（注：我以后不再回复类似的邮件了）。

我深深地发现，对于我国这样从小被父母和老师安排各种事情长大的人，当有一天，父母和老师都跟不上的时候，我们几乎完全不知道怎么去做选择。而我最近也离开了亚马逊，换了一个工作。又正值年底，就像去年的那篇《三个故事和三个问题》一样，让我想到写一篇这样的文章。

几个例子

当我们在面对各种对选择的影响因子的时候，如：城市，公司规模，公司性质，薪水，项目，户口，技术，方向，眼界…… 你总会发现，你会在几个公司中纠结一些东西，举几个例子：

某网友和我说，他们去上海腾讯，因为腾讯的规模很大，但却发现薪水待遇没有豆瓣高（低的还不是一点），如果以后要换工作的话，起薪点直接关系到了以后的高工资。我说那就去豆瓣吧，他说豆瓣在北京，污染那么严重，又没有户口，生存环境不好。我说去腾讯吧，他说腾讯最近组织调整，不稳定。我说那就去豆瓣吧，慢公司，发展很稳当。他说，豆瓣的盈利不清楚，而且用Python，自己不喜欢。我说，那就去腾讯吧，……

还有一网友和我说，他想回老家，因为老家的人脉关系比较好，能混得好。但又想留在大城市，因为大城市可以开眼界。

…

阅读全文 Read More

(153 人打了分，平均分： 4.77 )

如何测试洗牌程序

2012年11月20日陈皓评论 142 条评论 104,790 人阅读

我希望本文有助于你了解测试软件是一件很重要也是一件不简单的事。

我们有一个程序，叫ShuffleArray()，是用来洗牌的，我见过N多千变万化的ShuffleArray()，但是似乎从来没人去想过怎么去测试这个算法。所以，我在面试中我经常会问应聘者如何测试ShuffleArray()，没想到这个问题居然难倒了很多有多年编程经验的人。对于这类的问题，其实，测试程序可能比算法更难写，代码更多。而这个问题正好可以加强一下我在《我们需要专职的QA吗？》中我所推崇的——开发人员更适合做测试的观点。

我们先来看几个算法（第一个用递归二分随机抽牌，第二个比较偷机取巧，第三个比较通俗易懂）

递归二分随机抽牌

有一次是有一个朋友做了一个网页版的扑克游戏，他用到的算法就是想模拟平时我们玩牌时用手洗牌的方式，是用递归+二分法，我说这个程序恐怕不对吧。他觉得挺对的，说测试了没有问题。他的程序大致如下（原来的是用Javascript写的，我在这里凭记忆用C复现一下）：

//递归二分方法
const size_t MAXLEN = 10;
const char TestArr[MAXLEN] = {'A','B','C','D','E','F','G','H','I','J'};

static char RecurArr[MAXLEN]={0};
static int cnt = 0;
void ShuffleArray_Recursive_Tmp(char* arr, int len)
{
    if(cnt > MAXLEN || len <=0){
        return;
    }

    int pos = rand() % len;
    RecurArr[cnt++] = arr[pos];
    if (len==1) return;
    ShuffleArray_Recursive_Tmp(arr, pos);
    ShuffleArray_Recursive_Tmp(arr+pos+1, len-pos-1);
}

void ShuffleArray_Recursive(char* arr, int len)
{
    memset(RecurArr, 0, sizeof(RecurArr));
    cnt=0;
    ShuffleArray_Recursive_Tmp(arr, len);
    memcpy(arr, RecurArr, len);
}

void main()
{
    char temp[MAXLEN]={0};
    for(int i=0; i<5; i++) {
        strncpy(temp, TestArr, MAXLEN);
        ShuffleArray_Recursive((char*)temp, MAXLEN);
    }
}

…

阅读全文 Read More

(31 人打了分，平均分： 4.00 )

TF-IDF模型的概率解释

2012年10月24日 Todd 评论 51 条评论 59,052 人阅读

（感谢 @猫叔shiro（以前的todd）投递此文）

信息检索概述

信息检索是当前应用十分广泛的一种技术，论文检索、搜索引擎都属于信息检索的范畴。通常，人们把信息检索问题抽象为：在文档集合D上，对于由关键词w[1] … w[k]组成的查询串q，返回一个按查询q和文档d匹配度relevance(q, d)排序的相关文档列表D’。

对于这一问题，先后出现了布尔模型、向量模型等各种经典的信息检索模型，它们从不同的角度提出了自己的一套解决方案。布尔模型以集合的布尔运算为基础，查询效率高，但模型过于简单，无法有效地对不同文档进行排序，查询效果不佳。向量模型把文档和查询串都视为词所构成的多维向量，而文档与查询的相关性即对应于向量间的夹角。不过，由于通常词的数量巨大，向量维度非常高，而大量的维度都是0，计算向量夹角的效果并不好。另外，庞大的计算量也使得向量模型几乎不具有在互联网搜索引擎这样海量数据集上实施的可行性。

tf-idf模型

目前，真正在搜索引擎等实际应用中广泛使用的是tf-idf模型。tf-idf模型的主要思想是：如果词w在一篇文档d中出现的频率高，并且在其他文档中很少出现，则认为词w具有很好的区分能力，适合用来把文章d和其他文章区分开来。该模型主要包含了两个因素：

…

阅读全文 Read More

(23 人打了分，平均分： 3.65 )

酷壳 – CoolShell

享受编程和技术所带来的快乐 – Coding Your Ambition

Browsed by
标签： Algorithm

Cuckoo Filter：设计与实现

2015年09月02日 Leo 评论 37 条评论 77,434 人阅读

Leetcode 编程训练

2014年10月23日陈皓评论 97 条评论 202,531 人阅读

谜题的答案和活动的心得体会

2014年08月06日陈皓评论 98 条评论 67,670 人阅读

谜题的答案和花絮

【活动】解迷题送礼物

2014年08月03日陈皓评论 107 条评论 54,833 人阅读

二维码的生成细节和原理

2013年10月29日陈皓评论 166 条评论 429,994 人阅读

基础知识

伙伴分配器的一个极简实现

2013年10月09日 Leo 评论 55 条评论 76,112 人阅读

二叉树迭代器算法

2013年07月14日 Todd 评论 54 条评论 46,806 人阅读

程序算法与人生选择

2012年12月28日陈皓评论 220 条评论 195,588 人阅读

几个例子

如何测试洗牌程序

2012年11月20日陈皓评论 142 条评论 104,790 人阅读

递归二分随机抽牌

TF-IDF模型的概率解释

2012年10月24日 Todd 评论 51 条评论 59,052 人阅读

信息检索概述

tf-idf模型