.NET如何写正确的“抽奖”——数组乱序算法

.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;
}

可以在 LINQPad6中,使用如下代码,测试随机打乱 0-10的数列,进行 50万条次模拟统计:

int[] Measure(int n, int maxTime)
{
    var data = Enumerable.Range(1, 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万条数据统计结果如下:

可见,排在两端的数字几乎没多大变化,如果用于公司年会抽奖,那么排在前面的人将有巨大的优势

对比一下,如果在公司年会抽奖现场,大家 CodeReview时在这时“揭竿而起”,是不是很正常?

为什么会这样?

因为排序算法的本质是不停地比较两个值,每个值都会比较不止一次。因此要求比较的值必须是稳定的,在此例中明显不是。要获得稳定的结果,需要将随机数固定下来,像这样:

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程序园(dotnetblog)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏lhyt前端之路

内功修炼之lodash——By、With系列

本文实现方法都是看效果倒推实现方法,并进行一些拓展和思考,和源码无关。lodash这个库在这里更像一个题库,给我们刷题的

9410
来自专栏机器学习养成记

图片相似度识别:aHash算法

aHash、pHash、dHash是常用的图像相似度识别算法,原理简单,实现方便,个人把这三个算法作为学习图片相似度识别的入门算法。本次起,从aHash开始,对...

18120
来自专栏SAS程序分享号号号

SAS-给公众号做一个秩和检验

嗯,于是小编从公众号上下载了自2017年11月11日-2018年03月25日的公众号每日增粉相关的数据...接着小编就开始分组了,以500人为区间,分成3个组进...

8320
来自专栏ACM算法日常

最短路专题2 | CodeForces 449B - SPFA算法

Jzzhu is the president of country A. There are n cities numbered from 1 to n in ...

10220
来自专栏Java学习笔记

Spring Boot 概述

Spring Boot可以以jar包的形式独立运行,运行一个Spring Boot项目只需要通过java -jar xx.jar来运行 。

13040
来自专栏SAS程序分享号号号

SAS-这几个小语法真的很鸡肋吗?

我们在写程序对大量数据集批量操作的时候,如果有的数据集有某变量,有的数据集没有某变量,而这个变量也作为程序处理的关键变量...这个时候我们就需要来判断某数据集中...

14820
来自专栏搜狗测试

不写代码实现条件循环?只用Jmeter就能实现

Jmeter是常用的接口测试工具,可以方便地对各种接口进行测试。有时,我们可能需要在一次测试流程中对某个接口进行若干次请求,以达成一定目的。这时,我们无需在脚本...

13730
来自专栏泰斗贤若如

我们一起学Python之——认识Python"规则"

开学后,跟预想的一样,开学第一天我们就开了Python,虽然之前早就预料到了,但对于一直学Java的我来说,内心还是有一些涟漪的。总归还是要接受的,还不如振作...

5510
来自专栏SAS程序分享号号号

SAS-之前学了俩招,最近用了一下~

首先要说的一招是SAS编程中的横线的用法,最常见的是一道横线,当然今天要说的这一招并不是一道横线,那么也不妨先来看看一道横线的作用~

10320
来自专栏SAS程序分享号号号

SAS-爬取帖子下的邮箱,给他们发一封邮件...

SAS中获取网页上信息的原理其实很简单,就是将网页上的html代码给导入进数据集中,然后利用一定规律来获取自己想要的提取的信息...(目前个人浅显的理解),那么...

8330

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励