基本算法连载（2）－摔xbox

• 题目

You have been given 2 special, extremely rugged Xboxes. You are in an office building that is 100 stories high. Using the fewest possible number of drops from windows in your office building, determine the highest floor you can drop an Xbox from and have it survive: for example, they might be able to take the drop from the 30th floor, but not the 31st. You can break both Xboxes in your search. State the worst case number of drops needed and explain how you arrived at that answer.
你在一幢100层的办公楼里上班，现在给你两台xbox（已经特意捆绑包扎好），要求你用尽可能少的试摔次数来判断xbox摔不坏的最高楼层层数。比方说，从30层丢下来没问题，但从31层丢下来就不保了。在摸索过程中，允许把两台xbox都砸烂。在最坏情况下，使得试摔次数尽可能小。

• 分析

1. 问题答案必须是在最坏情况下，时间复杂度最小。
2. 最容易想到的就是二分法，三分法，多分法，但它们并不符合要求。比如：在50层丢一个，被砸烂。然后在25层丢另外一个，同样被砸烂。此时根本无从找到问题答案。
3. 第二个想到的方法就是分段。（1）用第一个xbox寻找损坏区间；（2）用第二个xbox遍历该区间寻找损坏层。假定最优区间长度是x，则第一步最多要摔100/x（大于等于此值的最小整数）次，第二步最多摔x-1次，问题转换为求100/x+(x-1)的最小值。具体描述：以10层楼为一个区间，先摔第一个，以确定摔坏的区间，然后再用另一个在这个区间内从最低的楼层摔，从而找到所要求层数，这种方法最多要摔19次。
4. 在“分段”方法中，段区间都是相等的。如果段区间不等，是不是可以找到最优的方法呢？假设最终答案至少要摔n次，那第一次顶多从n层楼摔。如果坏了，第二 个从1至n-1层最多摔n-1次就可以判断了；如果没坏，那么搜索范围改为[n+1,100]，相当于搜索空间减少了n层。如果第一次没坏，第二次顶多再 减少n-1的搜索空间。依次类推，当第n次时顶多再减少1的搜索空间。n次之后，顶多排除n+(n-1)+(n-2)+...+1 = n*(n+1)/2个楼层。只要n*(n+1)/2 >= 100就可以了，满足这个条件的最小n为14。具体描述：从14楼丢一个，如果碎了，从1楼开始到13楼为止丢另一个，不碎，在14＋13楼丢；...

• 证明

给一个包含n个元素的数组，{a[1],...,a[n]}，a[1]+a[2]+...+a[n]=100。那么如果第k次摔坏了第1台xbox ，那么此时最坏情况下总共需要的次数是k+a[k]-1我们把这个记为cost[k]。此时，问题可以重新描述为：找到一个满足上述条件的数组，{a[1],...,a[n]} ，使得 max(cost[k])最小。
sigma( cost[k] )
= (1+a[1]-1) + (2+a[2]-1) + (3+a[3]-1) ... + (n+a[n]-1)
= (1+2+3+ ... +n) + (a[1]+a[2]＋a[3]+ ... +a[n]) - n
= n*(n+1)/2 + 100 - n
这个式子是个常量仅与n有关，与{a[1],...,a[n]}的具体数值无关。同时，不难看出 max( cost[k] ) >= sigma( cost[k] ) / n （最大值总是大于平均值），而且仅当 cost[1] =cost[2] = ... cost[n] 的时候，max...可以取到这个最小值。因此，对于任意给定的n，满足 cost[1]= cost[2] = ... cost[n]的解就是最优解。也就是说k+a[k]-1=1+a[1]-1，从而a[k]=a[1]-k+1 。那么a[2]=a[1]-1，a[3]=a[1]-2=a[2]-1...

参考：(1) 摔xbox的题目

找病狗

• 题目

村子中有50个人，每人有一条狗。在这50条狗中有病狗（这种病不会传染）。于是人们就要找出病狗。 每个人可以观察其他的49条狗，以 判断它们是否生病（如果有病一定能看出来），只是自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪 毙自己的狗（发现后必须在一天内枪毙），而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。 第一天大家全看完了，但枪没有响，第二天仍没有枪响。到了第三天传来一阵枪声，问村里共有几条病狗，如何推算得出？

• 答案

3条病狗

• 分析

1. 假设有n条病狗，那么就有50-n个人的狗不是病狗。第一天大家枪都没有响， 那么n必然大于1 。因为如果n = 1.那么必然有一个人(病狗的主人)看到49条好狗,那样他就会枪毙自己的狗。所以这里 n >= 2。
2. 到了第二天。大家都清楚了n >=2 ，但是还是没有开枪。这个时候必然有 n > 2，因为如果n == 2的话 .那两个病狗的主人看到都是一条病狗,他们会明白还有一条病狗就是自己那条，所以就会有人开枪。但是没人开枪，说明n >= 3。
3. 到了第三天，有人开枪了。因为 在前两天只能确定 n >=3 , 因为有人开枪了，那么开枪的那个人肯定能断定自己那条是病狗,并且他知道 n >=3 。 所以他肯定只看到了 2只病狗，才能确定他自己那只肯定是病狗。以此来推，第几天开枪，就有几只病狗。

基本算法连载（1）－顺序搜索与二分搜索

顺序搜索
Programmer每天都碰到顺序搜索，其code snippet：
/*
* 顺序遍历数组，搜索v值是否存在。如果存在，返回相应的位置索引，
* 否则返回-1
*/
int sequentialSearch(int a[],int v,int l,int r){
int i;
for(i = l;i <= r;i++){
if(v == a[i])
return i;
}
return -1;
}

分析：

1. 假设数组拥有N个元素，对于不成功的搜索，总是搜索N个元素；对于成功的搜索，平均搜索次数为N/2。
   
2. 假设每个数组元素被搜索到的概率相等，那么平均搜索次数可以这样计算：(1+2+...+N)/N = (N+1)/2
3. 对于排序数组，相关性质不变。
   

二分搜索
code snippet：
/*
* 二分搜索，非递归实现
* 假设：数组元素已经按序排列
*/
int binarySearch(int a[],int v,int l,int r){
int m;
while(l<=r){
m = (l+r)/2;
if(v == a[m])
return m;

if(v > a[m]){
l = m + 1;
}else{
r = m - 1;
}
}
return -1;
}

/*
* 二分搜索，递归实现
*/
//dataForExperiment数组定义及初始化
int binarySearch(int v,int l,int r){
if(l > r){
return -1;
}
int m = (l + r)/2;
if(v == dataForExperiment[m]){
return m;
}else{
if(v > dataForExperiment[m]){
return binarySearch(v,m+1,r);
}else{
return binarySearch(v,l,m-1);
}
}
}
分析：

1. 假设Tn表示在最坏情况下二分搜索需要比较的次数，那么有Tn＝Tn/2＋1，其中n>=2，T1＝1
2. 求解递归式，可以得到二分搜索检查元素个数永远不超过lgn＋1。
3. 数组必须是已经排好序的。
   

MapReduce:Simplified Data Processing on large Clusters－翻译版（下）

实现
拥有多个不同的MapReduce接口的实现是可能的。具体选择取决于环境。比如，一种实现适合于共享内存的机器，一种适合于NUMA(Non-Uniform Memory Access )多处理器，另外一种适合于大量的网络机器。
这节将描述在Google内部大量使用，适合于大量PC构成的集群系统这种计算环境的实现。在这个环境中：

1. 双CPUx86机器，运行Linux，具有2-4G内存。
2. 网络采用的是100M/s或1G/s的配置硬件，然实际的平均使用值大概为它们的一半。
3. 采用由成百上千PC构成的集群系统，机器故障很经常。
4. 存储采用的是直连每个机器的IDE硬盘。通过我们自己开发的GFS来管理磁盘上的数据。此文件系统使用复制策略使得自己在不可靠的硬件上具有很好的可用性和可靠性。
5. 用户提交作业到调度系统。每个作业由一系列任务构成，这些任务被映射到集群范围内可用的机器上。

• 执行概貌

通过把输入文件分割成M等份，Map调用能够在多台机器上分布执行。这M等分数据在不同机器上可以并行处理。通过使用分割函数（比如 hash(key) mod R）把中间形式的key空间分成R份，Reduce调用能够分布执行。分区数目和分割函数是由用户指定。
图1展示了整个MapReduce的操作流程。当用户程序调用MapReduce函数，将执行如下步骤（图上的数字号码与如下列表中的数字号码是一一对应的）：

1. MapReduce库首先把输入文件分成大小为16-64M之间块大小的M份（通过一个可选的用户参数控制），然后它在多台机器上启动程序副本。
2. 其中存在于master上的一个副本是特殊的，其余的worker都将由master分配工作。
3. 被分配map任务的worker将读取输入份中的内容。它从输入数据中解析key/value对，然后把这些对传给用户定义的Map函数。产生的中间key/value对将由内存缓存。
4. 处在缓存中的对将被间隔性的写入磁盘，这些对将散步在由分割函数指定的R个区域中。这些缓存对在局部磁盘的具体位置被传回给master，然后master负责把这些信息转发给reduce worker。
5. 当reduce worker从master得到位置信息，它将使用远程过程调用从map worker的局部磁盘中读取数据。读取完所有数据之后，reduce worker按照中间key进行排序，以使得相同值的key被分在一起。因为许多不同的key有可能映射到相同的reduce任务，所以排序是必须的。当 数据太大而不能将它们全部放入内存时，一种外部排序方法将被使用。
6. reduce worker遍历排好序的中间数据，当它遇到一个唯一的中间形式key，它将把key和与它对应的中间value传给用户提供的Reduce函数。Reduce函数的输出将被附加到与这个reduce对应的最终输出文件中。
7. 当所有的map和reduce任务被完成之后，master唤醒用户程序。于是MapReduce调用返回到用户代码。

当成功完成之后，输出结果将存在于R个输出文件中，每一个reduce任务对应一个。一般来说，用户没有必要合并这R个文件为一个。这些文件将被传给另一个MapReduce调用当作输入，或者能够处理输入被分割的其余形式的分布式程序。

• master数据结构

master保存有多种数据结构。对于每个map和reduce任务，它存储有它们的状态（空闲，正在处理或者完成）和非空闲worker所在机器的标志。
关于中间文件的位置信息是通过master从map任务传递给reduce任务的。因此，对于每个完成的map任务，master存储有它所产生的R文件 的位置和大小信息。一旦map任务完成，master就更新这些信息，然后把这些信息传给正在处理中的reduce任务。

• 容错

因为MapReduce库是用来在成百上千台机器上处理大量数据，所以库必须很好的进行容错处理。

1. worker故障

master间隔性的ping worker。当尝试多次之后没有响应，master将认为worker已经出现故障。任何已经在wokrer上完成的任务将被设置为空闲状态，以使得它 可以重新被调度。同样，正在处理的map或reduce任务也将被设置为空闲状态，以便重新调度。
完成的map任务需要重新执行，那是因为它们的输出是存储在出现故障机器上的本地磁盘，而导致不可访问。完成的reduce任务输出结果是存储在全局文件系统而不存在这个问题。
当一个map任务首先在woker A上执行，然后在worker B上（因为A出现故障），所有执行reduce任务的worker将得到重新执行的通知。对于还没有从worker A上读取数据的reduce任务将从woker B上读取。
MapReduce对worker故障具有很强的适应能力。比如在一次MapReduce操作中，网络维护一次性造成80台机器变得不可抵达。此时MapReduce重新执行这些出现问题机器上的任务，以至最终完成任务。

参考：(1) 什么是MapReduce? Google的分布运算开发工具!

MapReduce:Simplified Data Processing on large Clusters－翻译版（上）

• 概括

MapReduce既是一种编程模型，也是用来处理和生成大数据集的一种实现。用户指定的map函数操作key/value对以生成中间形式的key/value对；指定的reduce函数把具有相同中间形式key的value合并在一起。许多现实中的任务都可以用这种模型进行表述，在这篇文章中，将看到这方面的任务。
以MapReduce方式进行编写的程序可以自动并行化，运行在大规模集群系统上。运行系统替用户处理输入数据的分割，程序在一系列机器上的调度执行，故障处理，机器间的通讯。这样使得无并行和分布式经验的程序员利用此系统很容易的采用系统资源。
我们的MapReduce实现系统运行在用商用PC搭建的大规模集群系统上。它具有很好的可扩展性，比如可以对数TB的数据在成千上万机器上进行计算。程序员发现系统的可用性很好。在Google，已经有成百上千的基于MapReduce的应用程序。每一天，将有超过1千左右的MapReduce作业运行在Google的集群上。

• 简单介绍

在过去的5年中，本文作者和其余在Google的开发者实现了用来处理大量原始数据（比如被抓取的文档，Web请求日志，等等）的各种特殊目的计算。比如反向索引，web文档图形结构的表示，基于每台主机被抓取页面数量的统计，在指定一天中最经常使用的查询，等等。大部分计算从原理上讲是很简单的。但是随着输入数据的加大，这些计算不得不分发在成百上千台计算机上进行计算，以便计算任务在一个可接受的时间限度内完成。这时本来很简单的应用程序不得不处理并行计算，分发数据，处理故障等问题而导致其变得晦涩难懂。
为了应付这种复杂性，我们设计了一种新的抽象。它可以使得用户表达自己的简单计算，而把并行化，容错，数据分发和负载平衡的细节全部隐藏在库中。此抽象的 灵感来自于Lisp和其它函数语言中的map和reduce操作。我们意识到大部分的计算都包括：对输入中的逻辑“记录”进行map操作，以获得一系列的 中间形式的key/value对；对共享同一key的中间值进行reduce操作，以并其合并。用户提供map和reduce操作，然后运用此函数模型， 可以使得我们非常容易进行大规模的并行计算，通过重新执行的方式来达到容错的目的。
这项工作最主要的贡献是提供了一个简单且强大的接口，通过这个接口实现，使得大规模计算得到自动并行与分布，在大规模集群系统上达到高性能。
第2节描述了基本的编程模型，另外给出了Google内部的一些实例；第3节描述了为集群系统量身定制的MapReduce接口实现；第4节阐述了一些对 现存编程接口模型十分有用的改进；第5节提供了基于各种任务，现有实现的性能测试；第6节说明了MapReduce在Google内部的使用，阐述了利用 它对现有索引系统进行重写所获得的一些经验；第7节讨论了相关及将来工作。

• 编程模型

计算是把一系列key/value对当作输入，产生一系列key/value对。使用MapReduce库的用户用Map和Reduce表示计算过程。
用户提供的Map获得输入对，产生一系列的中间形式的key/value对。MapReduce库把中间形式key值为I的所有value集中在一起，然后把它们传给Reduce函数。
用户提供的Reduce函数，接受中间形式key值I和与它关联的一系列value，然后把这些值合并产生一个可能相对较小的value集合。一般来说，每个调用产生0个或1个输出值。中间形式的value是通过迭代器的形式提供给reduce函数。这样使得我们可以处理那些太大而不能一次性载入内存的value。

1. 样例

考虑一个在大量文档中统计每个单词出现次数的问题。用户将会用如下类似的伪代码进行描述。
map(String key,String value):
//key: document name
//value:document contents
for each word w in value:
EmitIntermediate(w,"1");

reduce(String eky,Iterator values):
//key: a word
//values: a list of counts
int result = 0;
for each v in values:
result += ParseInt(v);
Emit(AsString(result));

map函数产生一个单词和它出现次数的值（在这个样例中是1）。reduce函数对每个特定单词累加其出现次数。
此外，用户代码提供输入与输出文件名，各种可选的可调整的参数以满足mapreduce specification对象需要。接着把对象传递给MapReduce函数，进行调用。此时，用户代码链接用C++实现的MapReduce库。附录A包含这个样例的完整程序。


2. 类型

尽管前面的伪代码输入输出类型都是字符串，但从理论上说，map和reduce函数在类型处理上具有一定关联性。
map (k1,v1) -> list(k2,v2)
reduce (k2,list(v2)) ->list(v2)
如：输入key/value与输出key/value是处在不同的域，中间的key/value与输出key/value是处在同一域。
我们的C++实现都是把字符串作为函数的输入输出。这就需要用户代码在字符串与其它类型之间进行正确的转换。


3. 更多实例

具体包括：分布grep，URL访问频率统计，web连接图反转，每台机器的词矢量，反向索引，分布排序。

参考：(1) 什么是MapReduce? Google的分布运算开发工具!

反向索引（Inverted Index）

反向索引是一种索引结构，它存储了单词与单词自身在一个或多个文档中所在位置之间的映射。反向索引通常利用关联数组实现。它拥有两种表现形式：

1. inverted file index，其表现形式为 {单词，单词所在文档的ID}
2. full inverted index，其表现形式为{单词，（单词所在文档的ID，在具体文档中的位置）}

具体实例，假设有三个文档：

• T₀ = "it is what it is"
• T₁ = "what is it"
• T₂ = "it is a banana"

那么，采用inverted file index方式，结果是：
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
采用full inverted index方式，结果是：

"a":      {(2, 2)}
"banana": {(2, 3)}
"is":     {(0, 1), (0, 4), (1, 1), (2, 1)}
"it":     {(0, 0), (0, 3), (1, 2), (2, 0)}
"what":   {(0, 2), (1, 0)}

用C语言实现函数语言中的Map和Reduce操作

在Google 的论文《MapReduce：Simplified Data Processing on Large Clusters》中提到“Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional lanuages.”。对于大部分不熟悉函数语言的程序员来说，可能并不能够彻底理解Map和Reduce的具体含义。在这篇文章中，将采用C语言实现函数语言中的Map和Reduce操作。
简单来说，Map是对一组数据中的每个元素进行操作，产生一组全新的数据；Reduce是对这组数据进行归约，得到一个相对简单的结果。现在就让我们用C语言来描述它们。
#include <stdio.h>
//函数指针申明
typedef int (*mapFunction)(int);
typedef int (*reduceFunction)(int,int);
#define ERROR -1;

//-----------------Map和Reduce操作-----------------
/*
* 对list数组的数据进行处理，然后存储在list数组中
*/
void map(mapFunction func,int *list,int len){
int i;
for(i=0;i<len;i++){
list[i] = func(list[i]);
}
}

int reduce(reduceFunction func,int *list,int len){
if(len <= 0){
return ERROR;
}
int retVal = 0;
int i;
for(i=0;i<len;i++){
retVal = func(retVal,list[i]);
}
return retVal;
}

//-----------------------测试-------------------------
int square(int i){
return i*i;
}

int add(int i,int j){
return i+j;
}

int main(int argc,char*argv[]){
int array[5];
int i;
for(i=0;i<5;i++){
array[i] = i;
}

mapFunction mapFuncPointer = (mapFunction)&square;
reduceFunction reduceFuncPointer = (reduceFunction)&add;
map(mapFuncPointer,array,5);
int result = reduce(reduceFuncPointer,array,5);
printf("The result is %d\n",result);
return 0;
}

参考：(1) 从Map和Reduce说起

我是一只小小鸟

看完“鲁豫有约”之《任贤齐－四十不惑》之后，我就爱上了《我是一只 小小鸟》这首歌。blog的地址就用a small bird啦！