.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骚操纵】