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

• 一个链接 lua 引起的 bug , 事不过三

今天花了将近 3 个小时帮同事看一个崩在 lua VM 中的 bug 结果打乱了进度，没有在年前把预想的东西做完。其实说起来这不是个大问题，以前也碰到过。我检讨自己没有在看到出错时的调用栈时去看一眼 lua 相关的代码。如果是那样，因为以前遇到过同样的问题，所以就可以条件反射出问题原因，而不用荒废宝贵了数小时时间了。唉，这下整合的进度没接上，过年不能自己一个人接着做下面的活了。下面记录一下这个 bug ，提醒自己第三次...

• Amazon DynamoDB详解

今早Amazon发布了DynamoDB，作为AWS服务的新成员，提升了AWS管理结构化数据的能力。总体来说，DynamoDB是基于Amazon Dynamo技术实现的可伸缩性和可用性优异的NoSQL数据库托管服务。我们知道，Amazon搞了一个很牛的KV数据库Dynamo，可伸缩性、可用性和性能稳定性非常好。但Dynamo推出后并没有在Amazon内部被广泛接纳，主要原因是Dynamo是作为软件系统提供给开发者，要用得部署各自的Dynamo集群，安装管理成本很高。后来Amazon推出了...

• 12个经典的行程问题

无论是小学奥数，还是公务员考试，还是公司的笔试面试题，似乎都少不了行程问题――题目门槛低，人人都能看懂；但思路奇巧，的确会难住不少人。平时看书上网与人聊天和最近与小学奥数打交道的过程中，我收集到很多简单有趣而又颇具启发性的行程问题，在这里整理成一篇文章，和大家一同分享。这些题目都已经非常经典了，绝大多数可能大家都见过；希望这里能有至少一个你没见过的题目，也欢迎大家来信提供更...

• Linux服务器时间相关结构体和函数整理

一、时间类型 Linux下常用的时间类型有4个：time_t，struct timeb, struct timeval，struct timespec，clock_t, struct tm. (1) time_t是一个长整型，一般用来表示用1970年以来的秒数

• libuv 初窥

过年了，人都走光了，结果一个人活也干不了。所以我便想找点东西玩玩。今天想试一下 libev 写点代码。原本在我那台 ubuntu 机器上一点问题都没有，可在 windows 机上用 mingw 编译出来的库一个 backend 都没有，基本不可用。然后网上就有同学推荐我试一下 libuv 。 libuv 是 node.js 作者做的一个封装库，在 unix 环境整合的 libev ，而在 windows 下用 IOCP 另实现了一套。看起来挺满足我的玩儿的需求的。所以就试了一下。这...

• python+OpenCV进行人脸检测

OpenCV的人脸检测功能在一般场合还是不错的。而ubuntu正好提供了python-opencv这个包，用它可以方便地实现人脸检测的代码。

• 费马检查

去年看到这段的时候就想扒到网上，却一直懒得动手。一直读到注解的时候，还是有点震撼的。我知道费马等一些人都热衷于“纯数学”，那些被看起来毫无实用价值的“纯理论”，可这费马检查，却是全世界的服务器每秒中都要运行无数次的 RSA 算法的理论基石。就我自己而言，每天使用 SSH 的时候都要用到。而几位科学家把这这一切联系起来的过程，实在称得上是“玄妙”了。《计算机程序的构造和解释》第二版中文版 P34-35费马小定理：如...

• 趣题：这些词有什么共同点？

据说，爱出题也是 Geek 的一种特征。这几天在做语言工程课的期末大作业时，再一次见识了汉语里各种诡异的语法规则，然后突然想到了这样一种好玩的题型，于是竟然暂时放下手中的作业，花时间编了几个这样的题目来（感谢 Geek 小美女 localhost_8080 的帮助）。下面的每一组词中，前五个词都具有某种共同的性质，这种性质是后面五个词都不具有的。你能猜出每组词所对应的那个性质...

• 大文件重定向和管道的效率对比

微博上的@拉风_zhang提出了个问题： @淘宝褚霸请教个问题，#1. cat huge_dump.sql | mysql -uroot ；#2. mysql -uroot < huge_dump.sql ；#1效率要高，在linux中通过管道传输和 < 这种方式有什么差别呢？谢谢！#AskBaye# 这个问题挺有意思的，我的第一反应是：没比较过，应该是一样的，一个是cat负责打开文件，一个是bash 这种...

• Buddy memory allocation (伙伴内存分配器)

今天吃晚饭的时候想到，我需要一个定制的内存分配器。主要是为了解决共享内存中的字符串池的管理。这个内存分配器需要是非入侵式的，即不在要分配的内存块中写 cookie 。而我的需求中，需要被管理的内存块都是很规则的，成 2 的整数次幂的长度。buddy memory allocation 刚好适用。算法很简单，就是每次把一个正内存块对半切分，一直切到需要的大小分配出去。回收的时候，如果跟它配对的块也是未被使用的，就合并成一个大...

• 关于Freelists和Freelist Groups的研究

如果为了避免freelists争用，而增加freelist group，确实可以减少Buffer Busy Waits事件，也会减少所有类别的block上的等待（从V$WAITSTAT视图中可以得知），但是却会增加HW Enqueu的等待事件。因为一个进程使用了一个freelist group之后，即使其它的freelist group中有大量的空闲空间（比如一个进程刚刚删除了大量的数据，从而在自己的TFL上腾出了很多空闲块），这个进程也不会去检索。所以如果这个进程正好需要insert大量数据，...

• 深入浅出jcr之16 该死的RMI,我们需要HTTP+简单RPC协议

从这篇文章开始,不再详细描述jackrabbit中的实现原理，而是把注意力放在jackrabbit中做的不好的地方，不敢说是批判，但是有些技术上的决策错误还是值得拿出来讨论讨论的。其中一个就是jackrabbit的客户端和jackrabbit server的通信方式－－RMI。围绕这个问题我们可以展开一系列的讨论。本文分为几个部分 1 为什么要抛弃RMI 2 为什么要选择基于HTTP的RPC协议 3 展望未来 RMI这个...

• Hadoop++：Hadoop的局部性能改良

Hadoop++是对Hadoop Map Reduce的非入侵式优化，通过自定义Hadoop框架中的split等函数来提升，提升查询和联接性能。项目由德国Saarland大学Jens Dittrich教授主持。项目主页是 http://infosys.uni-saarland.de/hadoop++.php。Hadoop++对Hadoop的优化主要是Trojan Index、Trojan Join和Trojan Layout三方面。1、Trojan Index Trojan index的核心是将数据组织成依次由数据、索引、Header和Footer这四部分构成的split，其中Foot...

• 蒙特霍尔问题与我那餐盒饭

前几天写的盒饭的问题有很大争议。我并不认为我的结论一定正确，但我想讨论这个问题的人忽略了许多现实的复杂性。我想说，这是个真实事件，并不是因为我想说明什么问题编的故事。我依然相信，我最后如果做一个交换，会更好一些。不过不想为这个事情争论下去 :) 我觉得这个问题和蒙特霍尔问题有相似之处，但并不相同。我也没想仔细去计算概率，直想快速判断，换或不换哪种得到正确结果的可能性更大。下面我想向有兴趣讨论说说...

• 趣题：用最少的点挡住所有可能的反射路径

有一个正方形的房间，房间的四壁都是镜子。房间里有一个天使和一个恶魔。假设房间是一个单位正方形 [0, 1] × [0, 1] ，那么天使和恶魔便是这个正方形内的两个点 (a, b) 和 (c, d) 。恶魔想要在原地发射致命激光杀死天使（激光可以无限地在镜子间反射）。天使可以根据恶魔的位置，预先在房间里放置一些守卫为他挡住激光（守卫实际上也是一些点）。当然，天使可以在自己周围密密麻麻地放一圈守卫，围成一个...

• 对角线方法之后的故事

同样是无穷集合，如果集合里的元素能够与全体正整数构成一一对应的关系，我们就说它是可数的，否则就说它是不可数的。 1874 年， Cantor 发表了一篇重要的论文，论文中证明了全体有理数甚至是全体代数数都是可数的，但全体实数却是不可数的。换句话说，同样是无穷多，实数的数量比有理数、代数数的数量都高出了一个级别。不过，当时 Cantor 证明实数集不可数的方法并不容易理解。 1891 年， Cantor 发表了...

• 通过Sonar来提高类的内聚性

在我们学习面向对象语言时，两个概念相当难理解：类必须高内聚，低耦合。今天的博文我们将解释这两个概念的重要性，同时展示Sonar如何帮助大家来评估类的内聚性。几周前，我开始讨论如何《Fight Back Design Erosion by Breaking Cycles with Sonar》，我提到好的设计应该能够通过很小的努力编写的新代码块就可以替换系统中的相关部分代码。第一个层面需要从“宏观水平”来看，例如：确保...

• 如此保证选举公正性能成吗？

一个小镇上即将进行大选，候选人有 m ≥ 3 个，选民一共有 n 人。选举时，每个选民在选票上写下一个候选人的名字，然后由计算机根据某种选举机制算出大选的获胜者来。如果把 n 个选民的选票依次记为 x1, x2, ..., xn 的话，那么选举机制的算法其实就是一个映射到 {1, 2, ..., m} 的函数 f(x1, x2, ..., xn) 。为了保证选举程序的公平性，让每个人手中的选票都能发挥作用，政府提...

• Paxos小议

问题最近我们在做一个项目的时候有这样一个需求：我们有多台服务器资源，希望彼此协作完成一项工作。这项工作可以被划分为N个小的模块，但由于这项工作会依赖于持续不断的输入(在线业务)，因此我们无法使用人工指定的方式将此工作分发到不同服务器进行。目前我们想到一个方法，将这项工作划分出的小模块放到一个稳定可靠的地方，例如mola存储系统，然后每台服务器去存储系统上取得一定数量的模块进行工作，完成后再将处理的结果输...

• 趣题：只允许加倍操作的水桶倒水问题

今天的题目来自这里。有三个水桶，它们里面分别装了 a 升的水、 b 升的水和 c 升的水（其中 a 、 b 、 c 都是正整数，桶本身没有容量限制）。你可以把水从一个桶倒进另一个桶，但必须保证让后者的水量刚好变成原来的两倍。证明，不管 a 、 b 、 c 是多少，你总能让其中某一个水桶变空。例如，假设初始时 (a, b, c) = (3, 2, 1) ，那么你可以先把 (3, 2, 1) 变成 (1, 4, 1) ，再...