趣味问题 | 酷壳

Cuckoo Filter：设计与实现

2015年09月02日 Leo 评论 37 条评论 74,680 人阅读

对于海量数据处理业务，我们通常需要一个索引数据结构，用来帮助查询，快速判断数据记录是否存在，这种数据结构通常又叫过滤器(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 )

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

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

我于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 条评论 51,032 人阅读

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

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

http://fun.coolshell.cn/

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

…

阅读全文 Read More

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

如何用最有创造力的方式输出42

2014年03月06日陈皓评论 29 条评论 45,276 人阅读

酷壳似乎好长时间没有像《编程真难啊》或是《老手是这样教新手编程的》或是像《如何写出无法维护的代码》这样“严肃正经”的文章了，所以，赶在大家还没有向我扔臭鸡蛋前奉献一篇。这篇文章来自CodeGolf.StackExchange上的《Most creative way to display 42》—— 请以最有创造力的方式输出42。于是出现了下面的这些答案（注：精彩的总是留在最后面）

人生和宇宙终级问题的答案：42

这里，需要介绍一下为什么要输出42。这时因为42是我们人生，世界乃至整个宇宙的终级答案。这要从《银河系漫游指南》（英文名：The Hitchhiker’s Guide to the Galaxy）说起。这本书是著名英国科幻小说作家Douglas Adams所著5本银河系漫游指南系列科幻喜剧系列小说中的第一本，改编自他本人为英国广播公司第四电台（BBC Radio 4）所写的广播剧剧本。该书1979年10月12日首次由麦克米伦出版公司（Pan Books）出版，次周成为英国图书销量榜冠军，前3个月内销售超过25万本。截至2005年，这本小说已被翻译成超过30种语言在全世界发行，并且被改编为电视剧、电影、舞台剧等多种艺术形式的作品。

这本小说中小说中充满尖锐的讽刺和隐喻，被西方科幻爱好者奉为“科幻圣经”。其中有两个关键词，一个是Don’t Panic，一个是42影响力很大，而其中关于42的故事简介是这样的：

百万年前，老鼠其实是一种超智慧生物，它们建造了一部超级电脑深思Deep Thought，它们问超级电脑，生命、宇宙以及任何事情的终极答案（Answer to Life, the Universe, and Everything）什么，经过了750万年的计算，深思告诉老鼠的后人答案是42，深思解释它只能计算出答案是什么，但答案的原因必须由另一部更高智能的电脑才能解释，而该部电脑就是地球。经过了800万年，就在结果要出来的五分钟前，地球却因为挡在预定兴建的星际间高速公路的路线，被Vogons给毁灭，电脑没有给出最后的结果。

…

阅读全文 Read More

(32 人打了分，平均分： 3.94 )

一个“蝇量级” C 语言协程库

2014年01月28日 Leo 评论 54 条评论 117,035 人阅读

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

协程(coroutine)顾名思义就是“协作的例程”（co-operative routines）。跟具有操作系统概念的线程不一样，协程是在用户空间利用程序语言的语法语义就能实现逻辑上类似多任务的编程技巧。实际上协程的概念比线程还要早，按照 Knuth 的说法“子例程是协程的特例”，一个子例程就是一次子函数调用，那么实际上协程就是类函数一样的程序组件，你可以在一个线程里面轻松创建数十万个协程，就像数十万次函数调用一样。只不过子例程只有一个调用入口起始点，返回之后就结束了，而协程入口既可以是起始点，又可以从上一个返回点继续执行，也就是说协程之间可以通过 yield 方式转移执行权，对称（symmetric）、平级地调用对方，而不是像例程那样上下级调用关系。当然 Knuth 的“特例”指的是协程也可以模拟例程那样实现上下级调用关系，这就叫非对称协程（asymmetric coroutines）。

基于事件驱动模型

我们举一个例子来看看一种对称协程调用场景，大家最熟悉的“生产者-消费者”事件驱动模型，一个协程负责生产产品并将它们加入队列，另一个负责从队列中取出产品并使用它。为了提高效率，你想一次增加或删除多个产品。伪代码可以是这样的：

# producer coroutine
loop
while queue is not full
  create some new items
  add the items to queue
yield to consumer

# consumer coroutine
loop
while queue is not empty
  remove some items from queue
  use the items
yield to producer

…

阅读全文 Read More

(40 人打了分，平均分： 4.18 )

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

2013年10月09日 Leo 评论 55 条评论 72,029 人阅读

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

提起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

(32 人打了分，平均分： 3.78 )

一个fork的面试题

2012年08月01日陈皓评论 223 条评论 180,790 人阅读

前两天有人问了个关于Unix的fork()系统调用的面试题，这个题正好是我大约十年前找工作时某公司问我的一个题，我觉得比较有趣，写篇文章与大家分享一下。这个题是这样的：

题目：请问下面的程序一共输出多少个“-”？

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

int main(void)
{
   int i;
   for(i=0; i<2; i++){
      fork();
      printf("-");
   }

   wait(NULL);
   wait(NULL);

   return 0;
}

如果你对fork()的机制比较熟悉的话，这个题并不难，输出应该是6个“-”，但是，实际上这个程序会很tricky地输出8个“-”。

要讲清这个题，我们首先需要知道fork()系统调用的特性，

…

阅读全文 Read More

(72 人打了分，平均分： 4.67 )

神奇的CSS形状

2012年03月24日 Neo 评论 21 条评论 29,794 人阅读

【感谢 Neo 投递本文 – 微博帐号：@_锟_ 】

在StackOverflow上有这么一个问题，有位同学在http://css-tricks.com/examples/ShapesOfCSS/ 找到一些使用CSS做的形状，其中一位同学对下面的这个形状充满了疑问。

形状是：

代码是：

#triangle-up {
width: 0;
height: 0;
border-left: 50px solid transparent;
border-right: 50px solid transparent;
border-bottom: 100px solid red;
}

这位同学就提问啦，为啥这么这么几句就能画出一个三角形呢？
于是呢，有高人出现，这个高人图文并茂的解释了这个三角的成因

…

阅读全文 Read More

(26 人打了分，平均分： 3.31 )

软件真的好难做啊

2011年06月10日陈皓评论 79 条评论 61,754 人阅读

还记得以前本站的那一篇“编程好难啊”吗，那是一篇众程序员调侃程序新手的文章，有恶搞的成分在里面。今天要和大家说的这个事没有一些恶搞和调侃的意思，是比较严肃的话题，你一定可以从中收获一些东西。这个话题来自StackOverflow上的一个问题——Cycle in Family Tree Software，这个程序员问了下面这个问题：

我是一个写家族族谱软件的程序员（我用的是C++和Qt），这个软件基本上没有什么问题，直到有一天有个用户报告了一个bug。这个问题是这样的——我这个用户和他女儿生了两个孩子。

于是，我程序员的一些断言和硬性条件导致程序报错，因为我的程序在处理这个关系的时候，其发现X即是Y的爸爸，又是Y的爷爷，所以只能报错。

请问，在不需要移除我的断言和数据验证的情况下，我怎么才能解决这个问题？

看到这里，请重点阅读一下下面的两点：

如果你看到这里开始兴奋了，请你为你阴暗的心理去面壁反省10分钟，因为这是一个很技术的问题。
如果你开始陷入了深深的思考如何解决这个问题，那么你绝对是一个合格的程序员，因为你已陷入技术已经很深了，有点呆了。

我在前面说过，“这个是一个严肃的话题，你可以从中收获一些东西”，当然，我并不希望你来收获乱伦的知识和心得，酷壳是一个技术博客，应该是收获技术方面的东西。

…

阅读全文 Read More

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

面试题：火车运煤问题

2011年04月11日陈皓评论 336 条评论 176,309 人阅读

这个可能是一个比较经典的智力题了，和以前的那个《赛马问题》很相似，其题目如下：

你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？

这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨煤，而到目的地有1000公里，而火车最多只能装1000吨媒。如果你的火车可以全部装下，到目的地也会被全部烧光，一丁点也不剩。所以，很多人的第一反应都是觉得这个不太可能。

如果你一开始就觉得不太可能的话，这是很正常的。不过我不知道你还会不会继续思考下去，如果你不想思考下去了，那么我很为你担忧，因为你可能并不是一个不善于思考的人，而是一个畏难的人，还有可能是一个容易放弃的人。这对于你做好一个需要大量思考的工作的程序员来说可能并不适合。

我一开始也觉得不可能，后来想了一想，想到一个解法可以最多运送500吨煤到市场，方法如下：（希望你先自己想一想再查看这个答案）
…

阅读全文 Read More

(51 人打了分，平均分： 4.45 )

酷壳 – CoolShell

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

Browsed by
分类：趣味问题

Cuckoo Filter：设计与实现

2015年09月02日 Leo 评论 37 条评论 74,680 人阅读

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

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

谜题的答案和花絮

【活动】解迷题送礼物

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

如何用最有创造力的方式输出42

2014年03月06日陈皓评论 29 条评论 45,276 人阅读

人生和宇宙终级问题的答案：42

一个“蝇量级” C 语言协程库

2014年01月28日 Leo 评论 54 条评论 117,035 人阅读

基于事件驱动模型

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

2013年10月09日 Leo 评论 55 条评论 72,029 人阅读

一个fork的面试题

2012年08月01日陈皓评论 223 条评论 180,790 人阅读

神奇的CSS形状

2012年03月24日 Neo 评论 21 条评论 29,794 人阅读

软件真的好难做啊

2011年06月10日陈皓评论 79 条评论 61,754 人阅读

面试题：火车运煤问题

2011年04月11日陈皓评论 336 条评论 176,309 人阅读