一个有趣的问题

昨天有人在微信上提了一个问题:

觉得挺有意思,似乎涉及到博弈理论,就想着用程序模拟一下看看结果。

思路是写一个依照题目game()函数,每次运行取随机数来控制命中与否。

然后简单粗暴地调用多次。

game()的前几句是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static string game(int strategy)
{
Random ra = new Random();
man m = new man();
man l = new man();
man h = new man();
m.rate = 0.3;
l.rate = 0.5;
h.rate = 1;
m.alive = true;
l.alive = true;
h.alive = true;
……

首先尝试了生成1000万个随机数,没想到运行居然花了70多秒:

感到实在难以理解,想起了知乎上的这个问题遂Profile。

看到90%的时间耗费在了Random实例的ctor()方法上。

后来想到可能是生成实例带来的GC耗费时间,于是将Random实例改为静态并拿到函数体外,时间瞬间缩短10倍降低到了不到6秒:

最后附上完整代码和运行结果:

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
for (int i = 0; i < 3; i++)
{
double m = 0;
double l = 0;
double h = 0;
for (double c = 0; c < 10000000; c++)
{
switch (game(i))
{
case "m": m++; break;
case "l": l++; break;
case "h": h++; break;
}
}
switch (i)
{
case 0: Console.Write("\n策略一:总是向命中率最高的人踢\n"); break;
case 1: Console.Write("\n策略二:随机选择敌人\n"); break;
case 2: Console.Write("\n策略三:总是向命中率最低的人踢\n"); break;
}
Console.Write("穆勒:" + m + "\n");
Console.Write("罗伊斯:" + l + "\n");
Console.Write("胡梅尔斯:" + h + "\n");
}
}
static bool end(man a, man b, man c)
{
return ((!a.alive&&!b.alive&&c.alive)||(!a.alive&&b.alive&&!c.alive)||(a.alive&&!b.alive&&!c.alive))?true:false;
}
static Random ra = new Random();
static man m = new man();
static man l = new man();
static man h = new man();
static string game(int strategy)
{
m.rate = 0.3;
l.rate = 0.5;
h.rate = 1;
m.alive = true;
l.alive = true;
h.alive = true;
while (true)
{
if (m.alive)
{
if (ra.NextDouble() <= m.rate)//m's Hit
{
switch (strategy)
{
case 0:
{
if (h.alive)
h.alive = false;
else
l.alive = false;
break;
}
case 1:
{
if (l.alive && h.alive)//Other 2 people both alive
{
if (ra.NextDouble() <= 0.5)//Choose victim randomly
l.alive = false;
else
h.alive = false;
}
else if (h.alive)
h.alive = false;
else
l.alive = false;
break;
}
case 2:
{
if (l.alive)
l.alive = false;
else
h.alive = false;
break;
}
}
if (end(m, l, h))
break;
}
}
if (l.alive)
{
if (ra.NextDouble() <= l.rate)//m's Hit
{
switch (strategy)
{
case 0:
{
if (h.alive)
h.alive = false;
else
m.alive = false;
break;
}
case 1:
{
if (m.alive && h.alive)//Other 2 people both alive
{
if (ra.NextDouble() <= 0.5)//Choose victim randomly
m.alive = false;
else
h.alive = false;
}
else if (h.alive)
h.alive = false;
else
m.alive = false;
break;
}
case 2:
{
if (m.alive)
m.alive = false;
else
h.alive = false;
break;
}
}
if (end(m, l, h))
break;
}
}
if (h.alive)
{
if (ra.NextDouble() <= h.rate)//h's Hit
{
switch (strategy)
{
case 0:
{
if (l.alive)
l.alive = false;
else
m.alive = false;
break;
}
case 1:
{
if (m.alive && l.alive)//Other 2 people both alive
{
if (ra.NextDouble() <= 0.5)//Choose victim randomly
l.alive = false;
else
m.alive = false;
}
else if (m.alive)
m.alive = false;
else
l.alive = false;
break;
}
case 2:
{
if (m.alive)
m.alive = false;
else
l.alive = false;
break;
}
}
if (end(m, l, h))
break;
}
}
}
return (m.alive ? "m" : (h.alive ? "h" : "l"));
}
}
public class man
{
public double rate;
public bool alive;
}
}