FREESTYLE分享1

分享时间：2011年9月23日16:00:00-18:00:00

分享内容

1.关于2的次方判断的解决方案及时间复杂度比较

2.简单2进制运算的处理与计算分析方法

3.格尼斯堡七桥问题的理解与欧拉图（回路）在实例中的应用

4.mysql数据库的同步遇到的问题及解决方案

5.从小猪快跑谈海量数据排序问题（应用场景：搜索top排序）

6.从海量数据浅谈mapreduce

分享主题详情及解决策略

1.关于2的次方判断的解决方案及时间复杂度比较

判断X是否是2的次方？请给出时间复杂度最低的方法

——方案1：道长提供 ——方案2：清妃提供——方法3：标准答案

简单循环的实现if ( x == 1 )if( !x&(x-1) )return log2N;

int count =0; return0;else return 0;

if ( x == 1 )// x =1 int temp = ( x << 1 );

return 0;//跳出 if(temp ==0)

else returnlog2N; //log2为底，N的对数

if ( x == 0 || x%2 != 0 )//x = 0或者奇数else

return -1;//跳出 return -1;

//真正进行循环的过程

while( x%2 == 0 )

{

x=x/2;

count++;

}

if ( x != 1 )

return -1;

else

return count;

各个算法时间复杂度的比较

方法1 方法2方法3

最好 O(1) O(1)O(1)

最差O(Log2N)O(1)O(1)

平均O(Log2N)O(1)O(1)

2．简单2进制运算的处理与计算分析方法

int F(int x,int y)

{

Return (x&y+(x^y)>>1)

}

(729,271)=?

所有整数都可以转换为若干个2的N次求和

将x与y转换成2进制

同时对每一位有【这里把关键位定位在第二位，也就是2的2次，其他位不管】

情景1，X与Y对应位都是1

且操作 异或操作
010 0 10
010 010
------ ------
010000

此时【 x&y+(x^y)>>1 】 = 【 x&y 】=【 （x+y）/2 】

情景2，X与Y对应位都是0

且操作 异或操作
000 0 00
0 00 000
------ ------
000 000

此时【 x&y+(x^y)>>1 】 = 0 =【 （x+y）/2】

情景2，X与Y对应位有1个是0

且操作 异或操作
000 0 00
0 10 010
------ ------
000 010

此时x&y+(x^y)>>1 = (x^y) = （x+y）/2

因此对于2进制每一位都有

x&y+(x^y)>>1 = （x+y）/2

对每一位求和也就是

x&y+(x^y)>>1 = （x+y）/2

所以题目

int F(int x,int y)

{

Return (x&y+(x^y)>>1)

}

(729,271)=（729+271）/2 = 500

3．格尼斯堡七桥问题的理解与欧拉图（回路）及其实例中的应用【图片传不上，这个问题很经典大家可以百度之此题的图片~】

问题环境

十八世纪，东普鲁士的首府哥尼斯堡是一座景色迷人的城市，普莱格尔河横贯城区，使这座城市锦上添花，显得更加风光旖旋。这条河有两条支流，在城中心汇成大河，在河的 中央有一座美丽的小岛。河上有七座各具特色的桥把岛和河岸连接起来。每到傍晚，许多人都来此散步。人们漫步于这七座桥之间，久而久之，就形成了这样一个问题：能不能既不重复又不遗漏地一次相继走遍这七座桥？这就是闻名遐迩的“哥尼斯堡七桥问题。”每一个到此游玩或散心的人都想试一试，可是，对于这一看似简单的问题，没有一个人能符合要求地从七座桥上走一遍。这个问题后来竟变得神乎其神，说是有一支队伍，奉命要炸毁这七座桥，并且命令要他们按照七桥问题的要求去炸。七桥问题也困扰着哥尼斯堡大学的学生们，在屡遭失败之后，他们给当时著名数学家欧 拉写了一封信，请他帮助解决这个问题。

欧拉给出的结论：【我们仅讨论了无向图，3,4两条为有向图的情况，勇乔先贴出来，大家有兴趣可以去看看】

1.无向连通图G是欧拉图，当且仅当G不含奇数度结点(G的所有结点度数为偶数)；

2.无向连通图G含有欧拉通路，当且仅当G有零个或两个奇数度的结点；

3.有向连通图D是欧拉图，当且仅当该图为连通图且D中每个结点的入度=出度

4.有向连通图D含有欧拉通路，当且仅当该图为连通图且D中除两个结点外，其余每个结点的入度=出度，且此两点满足deg－(u)－deg+(v)=±1。（起始点s的入读=出度-1，结束点t的出度=入度-1 或两个点的入读=出度）

扩展阅读

(蚂蚁比赛问题)

甲、乙两只蚂蚁分别位于如下图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？【可以重复】

勇乔补充：若要完成一笔走完的欧拉回路，只有从带有欧拉回路的奇度数点出发，终点为另一个奇度数点。

4. mysql数据库的同步遇到的问题及解决方案

不会传图片。这部分暂时留空

5. 从海量数据浅谈mapreduce

MapReduce能做？

a)日志分析

b)商业智能分析

c)客户营销

d)大规模索引

MapReduce不能：

a)在线应用 —Hbase解决了这个问题

b)复杂依赖逻辑（循环、递归？）

6．从小猪快跑谈海量数据排序问题（应用场景：搜索top排序）

问题原型

25只小猪比赛赛跑，每次最多同时可以让5只比赛，问至少需要几轮比赛才能赛出前三名？

先分5组

五次赛跑后的每组排序如下：

A1 B1 C1 D1 E1

A2 B2 C2 D2 E2

A3 B3 C3 D3 E3

A4 B4 C4 D4 E4

A5 B5 C5 D5 E5

第六轮

再A1B1 C1 D1 E1比赛，选出前三，假设为A1，B1，C1。

对上图可删选出剩余数据

A1 B1 C1

A2 B2

A3

第七轮

再第六轮前三与B2进行比赛，选出最快的三只猪

扩展阅读

当遇到海量数据时，也可以用同样方式进行搜索选择

问题场景：

10亿宝贝取出top10销量

利用宝贝id作为key来进行hash映射，分组到各个机器上，然后在每个机器进行reduce，返回每个机器排序后的top1。

此时就重现了如上的模型。

取出top10的机器，然后重现上图的模型，返回100*100/2的数据到主机，由主机进行剩余操作。【这部分勇乔会在后续给出各种排序策略复杂度分析】