云计算考试复习-参考资料

经典算法

蒙特卡洛算法求PI

蒙特卡罗方法是一种计算方法。原理是通过大量随机样本,去了解一个系统,进而得到所要计算的值。
它非常强大和灵活,又相当简单易懂,很容易实现。对于许多问题来说,它往往是最简单的计算方法,有时甚至是唯一可行的方法。

蒙特卡洛方法入门

蒙特卡洛方法代码实例(包含面积法和cesaro算法,用到了函数指针和结构体)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

//------声明bool类型,定义其常量true false------
typedef int bool;
enum { false, true };
//------定义结构体,包含测试次数和测试的函数指针------
struct MonteCarlo{
int trials;
bool (*experiment)(void);
};
//------递归调用,通过检查测试函数的返回值来判断当前测试是否通过并记录------
double monteCarloIter(struct MonteCarlo monteCarlo, int trialsRemaining, int trialsPassed)
{
if(trialsRemaining == 0) return (double)trialsPassed/monteCarlo.trials;
else if((*monteCarlo.experiment)() == true)
return monteCarloIter(monteCarlo, trialsRemaining-1, trialsPassed+1);
else
return monteCarloIter(monteCarlo, trialsRemaining-1, trialsPassed);
}
//------初始化MonteCarlo结构体,调用iter函数以启用递归调用------
double monteCarloWith(int trials, bool (*experiment)(void))
{
struct MonteCarlo monteCarlo;
monteCarlo.trials = trials;
monteCarlo.experiment = experiment;
return monteCarloIter(monteCarlo, trials, 0);
}
//------面积测试函数,RAND_MAX是随机数的最大值,那么rand()/RAND_MAX产生的值
//--------的范围就出在0-1之间,也就是判断一个1*1正方形上的点是否处于同一中心
//--------点的单位圆上------
bool areaTest()
{
//1*1的正方形
double x = (double)rand()/RAND_MAX;
double y = (double)rand()/RAND_MAX;
double z = x*x + y*y;
if(z <= 1) return true;
else return false;
}

//------接口------
double estimatePi(int trials)
{
return 4*monteCarloWith(trials, &areaTest);
}

int main(void)
{
srand(time(NULL)); //以当前时间为参数初始化随机数种子

for(;;)
{
int method, trials;
printf("------ MonteCarlo PI ------ \n");
printf("参数示例: 10000 即是尝试10000次 \n");
printf("请输入参数: \n");
scanf("%d", &trials);
printf("本轮计算结果为 %f\n", estimatePi(trials));
}

return 0;
}

//------ Usage ------
//Linux:
// gcc -Wall monte_carlo.c -o MonteCarlo -lm
// ./MonteCarlo

卡布列克数猜想

黑洞数也称为卡布列克常数,是指一种专指四位数的特定函数关系,在某排列顺序后,七演算式之后都会对应到6174。

卡布列克常数验证代码实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <stdlib.h>

//------定义bool类型及其常量true false------
typedef int bool;
enum { false, true };
//------定义一个表示四位数字的结构体------
typedef struct {
int thousand;
int hundred;
int ten;
int one;
} Number;
//------通过指针交换两个数字的值------
void exchange(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
//------将数组转换为Number结构体------
void fill(Number *num, int *arr) {
num->thousand = arr[0];
num->hundred = arr[1];
num->ten = arr[2];
num->one = arr[3];
}
//------冒泡排序,其中predicate是一个函数指针,用于决定两个数的“大小”------
void bubbleSort(int *arr, int size, bool (*predicate)(int, int)) {
for(int i=0; i<size; i++) {
int *prev = arr+i;
for(int j=i+1; j<size; j++) {
int *current = arr+j;
if((*predicate)(*prev, *current) == true) exchange(prev, current);
}
}
}
//------a小于b返回true,否则返回false------
bool less(int a, int b) {
if(a<b) return true;
else return false;
}
//------a大于等于b返回true,否则返回false------
bool greaterEqual(int a, int b) {
if(less(a,b)==true) return false;
else return true;
}
//------返回两个Number相减的结果------
int diff(Number *arr) {
int bigger = arr->thousand*1000 + arr->hundred*100 + arr->ten*10 + arr->one;
int smaller = (arr+1)->thousand*1000 + (arr+1)->hundred*100 + (arr+1)->ten*10 + (arr+1)->one;
int result = bigger-smaller;

printf("%d - %d = %d\n", bigger, smaller, result);
return result;
}
//------将一个四位数重新排序得到最大数和最小数,并返回大数减小数的结果------
//------ and then return the result of substraction------
int get(Number ori) {
int num[4] = {ori.thousand, ori.hundred, ori.ten, ori.one};

Number ret[2];
bubbleSort(num, 4, less);
fill(ret, num);
bubbleSort(num, 4, greaterEqual);
fill(ret+1, num);
return diff(ret);
}
//------给定一个数字,检查其能否在给定的测试次数里运算为6174------
bool compute(int num, int cnt) {
if(cnt==0) return false;
//通过除法和求余数来分割四位数
Number n;
int rem = 0;
n.thousand = num/1000;
rem = num%1000;
n.hundred = rem/100;
rem = rem%100;
n.ten = rem/10;
rem = rem%10;
n.one = rem;
//忽略四位数字全部相同的四位数
if(n.thousand==n.hundred && n.hundred==n.ten && n.ten==n.one) return 0;
int newNum = get(n);
if(newNum == 6174) return true;
else return compute(newNum, cnt-1);
}
//------默认计算多少次------
int DEFAULT_CNT = 7;
//------入口函数------
int main(int argc, char **argv) {
if(argc<2) {
printf("No input\n");
return 0;
}

for(int i=1; i<argc; i++) {
printf("Result: %d\n", compute(atoi(argv[i]), DEFAULT_CNT));
}

return 0;
}
//------Usage------
//gcc -Wall 6174.c -o 6174
//./6174 2000 1234 #To compute 2000 and 1234

大数据云计算的原理(一致性哈希于服务器负载均衡在多节点和少节点的应用)

我们上节介绍了普通Hash算法的劣势,即当node数发生变化(增加、移除)后,数据项会被重新“打散”,导致大部分数据项不能落到原来的节点上,从而导致大量数据需要迁移。

那么,一个亟待解决的问题就变成了:当node数发生变化时,如何保证尽量少引起迁移呢?即当增加或者删除节点时,对于大多数item,保证原来分配到的某个node,现在仍然应该分配到那个node,将数据迁移量的降到最低。

一致性Hash算法的原理是这样的:

img

MapReduce原理

课本 195页

Google MapReduce原始论文

img

伪代码示例:

map(String key, String value): 
   // key: document name 
   // value: document contents 
   for each word w in value: 
     EmitIntermediate(w, "1"); 

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

实例描述:
1)分布式Grep:
如果一行文本匹配了提供的模式,map函数将释放这一行到中间值集合中;
reduce函数直接拷贝原值到输出
2)URL访问频率统计:
map函数处理网页请求日志并输出URL;
reduce函数统计所有URL相同的次数,生成(URL, count)序对。

GFS系统架构

课本 185页

RAID 5和RAID 6的技术特点和区别

RAID5

RAID Level 5是一种储存性能、数据安全和存储成本兼顾的存储解决方案。它使用的是Disk Striping(硬盘分区)技术。RAID 5至少需要三块硬盘,RAID 5不是对存储的数据进行备份,而是把数据和相对应的奇偶校验信息存储到组成RAID5的各个磁盘上,并且奇偶校验信息和相对应的数据分别存储于不同的磁盘上。当RAID5的一个磁盘数据发生损坏后,可以利用剩下的数据和相应的奇偶校验信息去恢复被损坏的数据。RAID 5可以理解为是RAID 0和RAID 1的折衷方案。RAID 5可以为系统提供数据安全保障,但保障程度要比镜像低而磁盘空间利用率要比镜像高。RAID 5具有和RAID 0相近似的数据读取速度,只是因为多了一个奇偶校验信息,写入数据的速度相对单独写入一块硬盘的速度略慢,若使用“回写缓存”可以让性能改善不少。同时由于多个数据对应一个奇偶校验信息,RAID 5的磁盘空间利用率要比RAID 1高,存储成本相对较便宜.

RAID6

与RAID 5相比,RAID 6增加第二个独立的奇偶校验信息块。两个独立的奇偶系统使用不同的算法,数据的可靠性非常高,任意两块磁盘同时失效时不会影响数据完整性。RAID 6需要分配给奇偶校验信息更大的磁盘空间和额外的校验计算,相对于RAID 5有更大的IO操作量和计算量,其“写性能”强烈取决于具体的实现方案,因此RAID6通常不会通过软件方式来实现,而更可能通过硬件/固件方式实现。

同一数组中最多容许两个磁盘损坏。更换新磁盘后,数据将会重新算出并写入新的磁盘中。依照设计理论,RAID 6必须具备四个以上的磁盘才能生效。

区别

  • 与RAID 5相比,RAID 6增加第二个独立的奇偶校验信息块
  • 与RAID 5相比,RAID 6有更大的IO操作量和计算量
  • RAID5至少需要三块硬盘,RAID6至少需要四个以上的硬盘