.NET如何写准确的“抽奖”——打乱数组算法
2019-11-18杂谈搜奇网39°c
A+ A-.NET怎样写准确的“抽奖”——数组乱序算法
数组乱序算法常用于抽奖等生成暂时数据操纵。就拿年会抽奖来讲,假如你的算法有任何瑕疵,造成了任何不公平,在年会现场code review
时,搞不好不能在世走出去。
这个算法听起来很简朴,简朴到有时会拿它做面试题去考候选人,但它现实又很不随便马虎,由于细节很主要,稍不留神就错了。
起首来看准确的做法:
T[] ShuffleCopy<T>(IEnumerable<T> data, Random r)
{
var arr = data.ToArray();
for (var i = arr.Length - 1; i > 0; --i)
{
int randomIndex = r.Next(i + 1);
T temp = arr[i];
arr[i] = arr[randomIndex];
arr[randomIndex] = temp;
}
return arr;
}
能够在LINQPad 6
中,运用以下代码,测试随机打乱0-10
的数列,举行50万
条次模仿统计:
int[] Measure(int n, int maxTime)
{
var data = Enumerable.Range(0, n);
var sum = new int[n];
var r = new Random();
for (var times = 0; times < maxTime; ++times)
{
var result = ShuffleCopy(data, r);
for (var i = 0; i < n; ++i)
{
sum[i] += result[i] != i ? 1 : 0;
}
}
return sum;
}
然后能够运用LINQPad
特有的报表函数,将数据展现为图表:
Util.Chart(
Measure(10, 50_0000).Select((v, i) => new { X = i, Y = v}),
x => x.X, y => y.Y, Util.SeriesType.Bar
).Dump();
运转效果以下(记着这是准确的示例):
可见50万
次测试中,曲线基础安稳,0-10
的散布基础一致,相符统计学上的几率相称。
再来看看假如未做任何排序的代码:
T[] ShuffleCopy<T>(IEnumerable<T> data, Random r) => data.ToArray();
曲线:
记着这两条曲线,它们将作为我们的参考曲线。
不然呢?
实在准确的代码每一个标点符号都不能错,下面我将演示一些毛病的示例
毛病示例1
多年前我看到某些年会抽奖中运用了代码(运用JavaScript
、毛病示例):
[0,1,2,3,4,5,6,7,8,9].sort((a, b) => Math.random() - 0.5)
// 或许
[0,1,2,3,4,5,6,7,8,9].sort((a, b) => Math.random() - Math.random())
返回效果以下:
(10) [8, 4, 3, 6, 2, 1, 7, 9, 5, 0]
看起来“挺”一般的,数据确切被打乱了,这些代码在C#
中也能随便马虎写出来:
T[] ShuffleCopy<T>(IEnumerable<T> data, Random r) =>
data.OrderBy(v => r.NextDouble() < 0.5).ToArray();
50万
条数据统计效果以下:
可见,排在两头的数字险些没多大变化,假如用于公司年会抽奖,那末排在前面的人将有庞大的上风。
对照一下,假如在公司年会抽奖现场,人人Code Review
时在这时候“逼上梁山”,是否是很一般?
为何会如许?
由于排序算法的实质是不停地比较两个值,每一个值都邑比较不止一次。因而请求比较的值必需是稳固的,在此例中显著不是。要取得稳固的效果,需要将随机数牢固下来,像如许:
T[] ShuffleCopy<T>(IEnumerable<T> data, Random r) => data
.Select(v => new { Random = r.NextDouble(), Value = v})
.OrderBy(v => v.Random)
.Select(x => x.Value)
.ToArray();
此时效果以下(准确):
这类算法虽然准确,但它斲丧了过量的内存,时候复杂度为悉数排序的复杂度,即O(N logN)
。
乱个序罢了,肯定有更好的算法。
毛病示例2
假如将一切值遍历一次,将当前位置的值与随机位置的值举行交流,是否是也一样能够精准打乱一个数组呢?
尝尝吧,根据这个主意,代码可写出以下:
T[] ShuffleCopy<T>(IEnumerable<T> data, Random r)
{
var arr = data.ToArray();
for (var i = 0; i < arr.Length; ++i)
{
int randomIndex = r.Next(arr.Length);
T temp = arr[i];
arr[i] = arr[randomIndex];
arr[randomIndex] = temp;
}
return arr;
}
运转效果以下:
有一点点不均匀,我能够保证这不是偏差,由于屡次测试效果完整一样,我们拿数据措辞,经由过程以下代码,能够算出一切值的变化比例:
Measure(10, 50_0000).Select(x => (x / 50_0000.0).ToString("P2")).Dump();
效果以下:
0 90.00%
1 90.54%
2 90.97%
3 91.29%
4 91.41%
5 91.38%
6 91.31%
7 90.97%
8 90.60%
9 90.01%
按原理每一个数字偏离本值比例应该是90.00%
的模样,本代码中最高偏离值高了1.41%
,作为对照,能够看看准确示例的偏离比例数据:
0 90.02%
1 90.05%
2 90.04%
3 89.98%
4 90.05%
5 90.04%
6 90.07%
7 90.03%
8 89.97%
9 90.02%
可见最大偏差不凌驾0.05%
,比拟高达1%
的偏差,这肯定是有题目的。
实在题目在于随机数许可挪动屡次,假如涌现屡次随机,能够终究的值就不随机了,能够见这个示例,假如一个窗口运用如许的体式格局随机画点:坐标x两个随机数相加、坐标y仅一个随机数,示例代码以下:
// 装置NuGet包:FlysEngine.Desktop
using var form = new RenderWindow();
var r = new Random();
var points = Enumerable.Range(0, 10000)
.Select(x => (x: r.NextDouble() + r.NextDouble(), y: r.NextDouble()))
.ToArray();
form.Draw += (o, ctx) =>
{
ctx.Clear(Color.CornflowerBlue);
foreach (var p in points)
{
ctx.FillRectangle(new RectangleF(
(float)p.x / 2 * ctx.Size.Width,
(float)p.y * ctx.Size.Width,
ctx.Size.Width / 100, ctx.Size.Height / 100), form.XResource.GetColor(Color.Black));
}
};
RenderLoop.Run(form, () => form.Render(0, PresentFlags.None));
那末画出来的点多是这个模样:
可见,1万
条数据,x
坐标两个随机数相加以后,纵然下方代码中除以2
了,效果已悉数倾向中心值了(和本例代码效果一样),而只运用一次的y
坐标,随机水平一般。想一想也能晓得,就像扔色子一样,两次扔色子平均是6
的机率远比平均是3
的机率低。
因而能够得出一个结论:随机函数不能随便叠加。
毛病示例3
怎样每一个位置的点只交流一次呢?没错,我们能够倒着写这个函数,起首来看如许的代码:
T[] ShuffleCopy<T>(IEnumerable<T> data, Random r)
{
var arr = data.ToArray();
for (var i = arr.Length - 1; i > 0; --i)
{
int randomIndex = r.Next(i);
T temp = arr[i];
arr[i] = arr[randomIndex];
arr[randomIndex] = temp;
}
return arr;
}
注重轮回停止前提是i > 0
,而不是直接遍历的i >= 0
,由于r.Next(i)
的返回值肯定是小于i
的,用>=0
没有意义,起首来看看效果:
用这个算法,每一个数字出来都肯定不是它本身自身,这合理吗?听起来觉得也合理,但真的云云吗?
假定某公司年会运用该算法抽奖,那结论就是第一个人不能够中奖,假如正好你正好是抽奖名单列表的第一个人,你能接收吗?
听说昔时二战时期德国的通信加密算法,就是由于加密之前肯定和本来的数据不一样,致使安全性大大下降,被英国破解的。
这个题目在于算法没许可和数字和本身举行交流,只需将r.Next(i)
改成r.Next(i + 1)
,题目即可处理。
总结
所以先回忆一下文章最初算法:
T[] ShuffleCopy<T>(IEnumerable<T> data, Random r)
{
var arr = data.ToArray();
for (var i = arr.Length - 1; i > 0; --i)
{
int randomIndex = r.Next(i + 1);
T temp = arr[i];
arr[i] = arr[randomIndex];
arr[randomIndex] = temp;
}
return arr;
}
然后从新体味一下它性感的测试数据(10
条数据,规范的90%
):
只要写完很多个不准确的版本,才体味出写出准确的代码,每一个标点符号都很主要的觉得。
喜好的朋侪 请关注我的微信民众号:【DotNet骚操纵】