可视化分钱的概率模拟算法

介绍

之前在一篇文章上看到一个问题,说:“一个房间里有100个人,没人有100块钱,每分 钟每人随机给另外的人一块钱,那么过一段时间后,这100个人的财富分布是什么情 况?”。如果按照个人的常规直觉,无论过多久,他们的财富应该相差不会太多。可经 过计算机模拟,他们的财富会出现两级分差,有钱的很有钱,没钱的很没钱。然后作者将 他映射到现实社会中的财富分配,得出有钱人会越有钱,没钱的越没钱的道理。其实在我 看来从这个模拟实验的结果来看,并不能得出这样的结论。本篇文章我来进行这项实验的 可视化模拟。

HTML5的canvas

我会使用HTML5canvas画布,来做可视化的工具。当然使用别的工具当然也是可以 的,实现的方法是一样的。

对于canvas的用法,本篇文章不做详细的介绍,如果想要了解canvas的使用方法,参 考这里

首先设置画布:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Demo</title>
    <style>
        canvas#test {
            border: 1px solid #999;
            margin: 30px auto;
            display: block;
        }
    </style>
    <script>
        window.onload = function() {
            var canvas = document.getElementById('test');
            var ctx = canvas.getContext('2d');

        }
</head>
<body>
    <canvas id="test" width="500" height="500"></canvas>
</body>
</html>

在画布上画出 100 个人的初始金钱数状况:

var canvas = document.getElementById('test');
var ctx = canvas.getContext('2d');
var beginX = 0;
var arr = new Array(100);
for (var a=0; a<100; a++) {
    arr[a] = 100;
}
ctx.clearRect(0, 0, canvas.width, canvas.height);
ctx.fillStyle = '#157ac1c9';

for (var i=0; i<100; i++) {
    beginX = (canvas.width/100)*i;
    ctx.fillRect(beginX, canvas.height-arr[i], canvas.width/arr.length, arr[i]);
}

image

如图,x轴表示100个人,y轴表示每个人的金钱数100

算法实现

每个人的初始财富都是 100 元,如果要让他们每轮每个人随机给另一个人一元,那么就相 当于数组arr中的每一项,在每次循环后减去 1,然后每一次循环都有一个人增加 1。逻 辑理好了,实现起来也很简单:

for (var i=0; i<arr.length; i++) {    
    if (arr[i] > 0) {
        arr[i] -= 1;
        n = parseInt(Math.random()*100);
        arr[n] += 1;
    }
}

if (arr[i] > 0) {}保证没钱的人不能失去一元钱。n = parseInt(Math.random()*100)这一句是JavaScript随机取 0-100 前闭后开区间的随机 整数,这就表达出问题中的随机一人获得一元的语句。

通过循环,问题的模拟算法已经写好了,接下来就是画布中展示了。canvas的动画实现 的原理就是显示图片,然后清空画布,在更新画布。

// 画图函数
function draw(array) {
    // 清空画布
    ctx.clearRect(0,0, canvas.width, canvas.height);
    for (var k=0; k<arr.length; k++) {
        beginX = (canvas.width/arr.length)*k;
        ctx.fillRect(beginX, canvas.height-arr[k], canvas.width/arr.length, arr[k]);
    }
}
// 算法实现
function algoImitate() {
    // 调用画图函数
    draw();
    for (var i=0; i<arr.length; i++) {    
        if (arr[i] > 0) {
            arr[i] -= 1;
            n = parseInt(Math.random()*100);
            arr[n] += 1;
        }
    }
    // 定时刷新画布
    setTimeout(algoImitate, 200);
}

algoImitate();

运行函数就可以看到画布上模拟出来的动画了。

image

但是运行的动画实在太慢了,需要等很长时间才能看到结果,为了加快速度,可以更改刷 新画布的时间。但是如果不更改刷新时间,只是更改算法,该如何加快了。其实这就是如 何加快模拟算法的问题,其实很简单,只需要在算法循环的外层在加一层循环就好了:

// 算法实现
function algoImitate() {
    // 调用画图函数
    draw();
    for (var b=0; b<50; b++) {
        for (var i=0; i<arr.length; i++) {    
            if (arr[i] > 0) {
                arr[i] -= 1;
                n = parseInt(Math.random()*100);
                arr[n] += 1;
            }
        }
    }
    // 定时刷新画布
    setTimeout(algoImitate, 200);
}

这里的b<50中的 50 可以自由定义,这样在加一层循环,实际上就相当于之前模拟的 50 倍速度。现在再运行函数,显然动画更新的更快了。

image

但是如图,我们还是不能清晰的看出财富的大致分布。为了更清晰,需要在每次刷新循环 的时候给我们的数组排个序。我们整理一下代码,如下:

window.onload = function() {
    var canvas = document.getElementById('test');
    var ctx = canvas.getContext('2d');
    var beginX = 0;
    var arr = new Array(100);
    for (var a=0; a<100; a++) {
        arr[a] = 100;
    }
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    ctx.fillStyle = '#157ac1c9';

    function draw() {
        ctx.clearRect(0,0, canvas.width, canvas.height);
        for (var k=0; k<arr.length; k++) {
            beginX = (canvas.width/arr.length)*k;
            ctx.fillRect(beginX, canvas.height-arr[k], canvas.width/arr.length, arr[k]);
        }
    }
    function algoImitate() {
        draw();
        // 排序
        arr.sort(function(a,b){return a>b ? 1 : -1});
        for (var b=0; b<50; b++) {
            for (var i=0; i<arr.length; i++) {    
                if (arr[i] > 0) {
                    arr[i] -= 1;
                    n = parseInt(Math.random()*100);
                    arr[n] += 1;
                }
            }
        }
        setTimeout(algoImitate, 200);
    }

    algoImitate();
}

注意,JavaScript整数数组排序,如果使用Array.sort()直接排序的话,那么结果 就是[1,11,12,...,20,21,...,30,...]

动画运行一段时间就可以看出大致结果了。

image

不难发现财富的分布大致是呈一个幂指数的分布,有钱的和没钱的差距会很大。但是这是 经过我们排序后的分布,也就是说有钱人和没钱的人不一定一直是一个人。如果按照看 过的那篇文章说的“残酷的现实”结论,有钱的会更有钱,没钱的会更没钱的说法,显然 是不对的。至少从这个模拟是看不出的。

本文作者:俞坤

本文链接:http://www.yukunweb.com/2017/12/visualization-money-algorithm-imitate

版权声明:本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0许可协议。转载请注明出处!

什么年龄说什么话
3 条评论
  1. author
    2018-04-04
    柠檬酸

    微信的红包算法是每次取[0.01,剩下钱的平均值*2],测试下来一看很平均呀~

  2. author
    2017-12-31
    俞坤

    评论测试!!!!

    • 2017-12-31

      俞坤回复 俞坤:

      回复测试!!!

已登录,注销 取消