c# - 为什么我对随机数生成器进行的 parking 场测试会产生不好的结果？

Question

我正在尝试为随机数生成器编写 parking 场测试的实现。以下是我从中获取有关测试的信息的来源:Intel math library documentation和 Page 4 of this paper连同列出概率密度的 phi 函数 here .

我用 C# 编写了测试的实现。它使用 100x100 网格，其值最初设置为空。然后我使用随机数生成器为 x 和 y 生成随机整数。如果网格的那个索引和它的邻居是空的，那个索引被设置为 1。否则，什么也不会发生，因为有一个“崩溃”。

我使用 C# System.Random 生成器运行它。我不相信结果是正确的，因为我总是得到非常接近 3079 的 parking 点，这比我应该得到的平均水平低大约 500。它还产生 2.21829146215425E-90 的 p 值。

我的代码如下。有没有人对此有任何经验，或者有谁能看到我在实现过程中可能做错了什么？任何帮助将不胜感激。

  private void RunParkingLotTest()
    {
        points = new int?[100,100];
        int parked = 0;

        for (int i = 0; i < 12000; i++)
        {
            int x = random.Next(100);
            int y = random.Next(100);

            if (IsSafeToPark(x, y))
            {
                points[x, y] = 1;
                parked++;
            }

        }
        Console.WriteLine("Parked: " + parked + "\nP value: " + PhiFunction((parked-3523)/21.9));
    }

    private bool IsSafeToPark(int x, int y)
    {
        return PointIsEmpty(x, y) 
            && LeftOfPointIsEmpty(x, y) 
            && RightOfPointIsEmpty(x, y) 
            && BelowPointIsEmpty(x, y) 
            && AbovePointIsEmpty(x, y);
    }

    private bool AbovePointIsEmpty(int x, int y)
    {
        if (y == 99)
        {
            return true;
        }
        else
            return points[x, y + 1] == null;
    }

    private bool BelowPointIsEmpty(int x, int y)
    {
        if (y == 0)
        {
            return true;
        }
        else
            return points[x, y - 1] == null;
    }

    private bool RightOfPointIsEmpty(int x, int y)
    {
        if (x == 99)
        {
            return true;
        }
        else
            return points[x + 1, y] == null;
    }

    private bool LeftOfPointIsEmpty(int x, int y)
    {
        if (x == 0)
        {
            return true;
        }
        else
            return points[x - 1, y] == null;
    }

    private bool PointIsEmpty(int x, int y)
    {
        return points[x, y] == null;
    }

    private double PhiFunction(double x)
    {
        //ϕ(x) = (2π)−½e−x2/2

        return ((1 / Math.Sqrt(2 * Math.PI)) * Math.Exp(-(Math.Pow(x, 2)) / 2));
    }

编辑 - 我最初实现的问题是

• 我画的是正方形而不是圆盘
• 我只绘制了整数值的点。我应该改用十进制值。
• 由于上述两个原因，我需要更改距离检查

感谢 Chris Sinclair 和 mine z 帮助解决这个问题。最终代码贴在下面。

Answer 1

我要尝试一下，诚然，我还没有尝试过任何此类测试，所以请原谅我离题太远。不过，总的来说，.NET Random 实现非常好，我从来没有遇到过问题，所以一开始我不会怀疑，特别是因为你正确地重用了同一个实例而不是创建新的。

从 parking.pdf 和 Intel 文档中读取，他们似乎正在使用圆盘，并计算距其中心点的距离。您的实现使用正方形(点之间距离为 1 的数组)，因此忽略了对角线。

来自pdf:

If disks were being used, the distance between the particles r = p(x(i) − z)2 + (y(i) − z)2 would need to be less than or equal to one. Does it matter whether one uses disks or squares? An indication of the importance of which geometric figure is parked can be obtained by comparing the area occupied by a square of side 1.0 to the area of a disk of diameter 1.0. The ratio of the areas, disk to square, is π/4. Therefore, it would be anticipated that more disks could be placed in a box than squares in the same number of tries.

还有英特尔文档:

The test assumes a next random point (x, y) successfully ”parked”, if it is far enough from every previous successfully ”parked” point. The sufficient distance between the points (x1, y1) and (x2, y2) is min(|x1 - x2|,|y1 - y2|) > 1.

我猜测 π/4 圆盘与正方形的比率以及多少圆盘与正方形之间的差异可能是您看到不同数字的原因。 (虽然现在我看不出 3523 和 3070 与 π/4 之间有直接关系。3523 * π/4 = 2767 很接近，但我敢肯定如果有关系，它比简单的乘法稍微复杂一些。 )

不是一个很好的答案，但我最好的猜测。

编辑:有趣的是，我使用 1 个单位直径的圆盘进行了快速实现，并获得了大约 4000 个停放的结果。所以也许我未经训练的自己无法理解(或者 .NET 的 Random 没有通过测试？)无论如何，这是我的光盘实现:

List<Point> parkedCars = new List<Point>();
Random random = new Random();

void Main()
{
    int parked = 0;

    for (int i = 0; i < 12000; i++)
    {
        double x = random.NextDouble() * 100;
        double y = random.NextDouble() * 100;

        Point pointToPark = new Point(x, y);

        if (IsSafeToPark(pointToPark))
        {
            parkedCars.Add(pointToPark);
            parked++;
        }

    }
    Console.WriteLine("Parked: " + parked);
}

private bool IsSafeToPark(Point pointToPark)
{
    //make sure it's "inside" the box
    if (pointToPark.X < 0.5 || pointToPark.X > 99.5
        || pointToPark.Y < 0.5 || pointToPark.Y > 99.5)
        return false;

    if (parkedCars.Any(p => Distance(pointToPark, p) <= 1))
        return false;

    return true;
}

private double Distance(Point p1, Point p2)
{
    return Math.Sqrt((p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y));
}

使用我可能过于简单的 π/4 比率应用得到大约 3142。更接近一点，但它似乎非常不正确。

编辑:正如@mike z 所指出的，我直接使用距离的测试是不正确的。根据我忘记的测试参数，只检查 X 和 Y 距离是否大于 1。将我的 Distance 检查更改为:

Math.Max(Math.Abs(p1.X - p2.X), Math.Abs(p1.Y - p2.Y))

在 3450 附近产生更接近的结果，非常接近。如果我取出我的“//确保它在框内”检查，平均超过 10 次尝试得到 3531!

所以我最后的“工作”代码是:

public struct Point
{
    public double X,Y;

    public Point(double x, double y)
    {
        this.X = x;
        this.Y = y;
    }
}

List<Point> parkedCars = new List<Point>();
Random random = new Random();

void Main()
{
    int parked = 0;

    for (int i = 0; i < 12000; i++)
    {
        double x = random.NextDouble() * 100;
        double y = random.NextDouble() * 100;

        Point pointToPark = new Point(x, y);

        if (IsSafeToPark(pointToPark))
        {
            parkedCars.Add(pointToPark);
            parked++;
        }

    }

    Console.WriteLine("Parked: " + parked);
}

private bool IsSafeToPark(Point pointToPark)
{
    if (parkedCars.Any(p => Distance(pointToPark, p) <= 1))
        return false;

    return true;
}

private double Distance(Point p1, Point p2)
{
    return Math.Max(Math.Abs(p1.X - p2.X), Math.Abs(p1.Y - p2.Y));
}

编辑:我两次运行测试 100 次，并将结果平均分别为 3521.29 和 3526.74。不确定这是否意味着这仍然稍微多一点，但这也许只是表示 .NET 和 Fortran 之间的舍入或浮点精度差异。