Chr*_*ble 5 c# algorithm math statistics prng
我正在尝试为随机数生成器编写停车场测试的实现.以下是我获取测试信息的来源:英特尔数学库文档和本文第4页以及此处列出的概率密度的phi函数.
我在C#中编写了一个测试实现.它使用100x100网格,其值最初设置为null.然后我使用随机数生成器为x和y生成随机整数.如果网格及其邻居的索引为空,则该索引设置为1.否则,没有任何反应,因为存在"崩溃".
我使用C#System.Random生成器运行它.我不相信结果是正确的,因为我总是得到非常接近3079点停放,这比我应该得到的平均值短约500.它的p值也为2.21829146215425E-90.
我的代码如下.有没有人有这方面的经验,或者任何人都可以看到我在实施中可能做错的事情？任何帮助将不胜感激.
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和我的z帮助解决这个问题.最终代码发布在下面.
我将对此进行尝试，并且不可否认，我还没有尝试过任何此类测试，所以如果我离得很远，请原谅我。但总的来说，.NETRandom实现非常好，而且我从来没有遇到过问题，所以一开始我不会怀疑这一点，特别是因为您正确地重用了同一个实例而不是创建新实例。
从 parking.pdf 和英特尔文档中读取，似乎他们正在使用光盘，并计算距其中心点的距离。您的实现使用正方形（点之间距离为 1 的数组），从而忽略对角线。
\n\n来自pdf：
\n\n\n\n\n如果使用圆盘，则粒子之间的距离 r =\np(x(i) \xe2\x88\x92 z)2 + (y(i) \xe2\x88\x92 z)2 需要小于或等于一。\n 使用圆盘还是正方形有关系吗？通过将边长为 1.0 的正方形所占的面积与直径为 1.0 的圆盘的面积进行比较，可以得出所停放的几何图形的重要性。圆盘与正方形面积之比为 \xcf\x80/4。\n 因此，预计在相同次数的尝试中，可以将更多的圆盘放入盒子中而不是正方形。
\n
还有英特尔文档：
\n\n\n\n\n测试假设下一个随机点 (x, y) 成功 \xe2\x80\x9dparked\xe2\x80\x9d，如果\n 它距离每个先前成功的 \xe2\x80\x9dparked\xe2\x80\x9d 点足够远。点 (x1, y1) 和 (x2, y2) 之间的足够距离为 min(|x1 - x2|,|y1 - y2|) > 1。
\n
我猜测 \xcf\x80/4 磁盘与正方形的比率以及可以容纳的磁盘数量与正方形之间的差异可能是您看到不同数字的原因。（虽然现在我看不到 3523 和 3070 与 \xcf\x80/4.3523 * \xcf\x80/4 = 2767 之间的直接关系，这是接近的，但我确定是否存在关系它比简单的乘法稍微复杂一些。）
\n\n不是一个很好的答案，但我最好的猜测。
\n\n编辑：有趣的是，我使用 1 单位直径的圆盘进行了快速实现，并获得了大约 4000 个停放的结果。因此，也许这超出了我未经训练的自我所能理解的范围（或者也许 .NET 没有Random通过测试？）无论如何，这是我的光盘实现：
List<Point> parkedCars = new List<Point>();\nRandom random = new Random();\n\nvoid Main()\n{\n int parked = 0;\n\n for (int i = 0; i < 12000; i++)\n {\n double x = random.NextDouble() * 100;\n double y = random.NextDouble() * 100;\n\n Point pointToPark = new Point(x, y);\n\n if (IsSafeToPark(pointToPark))\n {\n parkedCars.Add(pointToPark);\n parked++;\n }\n\n }\n Console.WriteLine("Parked: " + parked);\n}\n\nprivate bool IsSafeToPark(Point pointToPark)\n{\n //make sure it\'s "inside" the box\n if (pointToPark.X < 0.5 || pointToPark.X > 99.5\n || pointToPark.Y < 0.5 || pointToPark.Y > 99.5)\n return false;\n\n if (parkedCars.Any(p => Distance(pointToPark, p) <= 1))\n return false;\n\n return true;\n}\n\nprivate double Distance(Point p1, Point p2)\n{\n return Math.Sqrt((p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y));\n}\n使用我对 \xcf\x80/4 比率的应用可能过于简单，结果约为 3142。更接近一点，但似乎非常不正确。
\n\n编辑：正如@mike z 指出的那样，我使用直接距离的测试是不正确的。根据我忘记的测试参数，仅检查 X 和 Y 距离是否大于 1。将我的Distance检查更改为：
Math.Max(Math.Abs(p1.X - p2.X), Math.Abs(p1.Y - p2.Y))\n在 3450 左右产生更接近的结果，非常接近。如果我去掉“//确保它在框内”复选框，则 10 次尝试的平均结果为 3531！
\n\n所以我最终的“工作”代码是：
\n\npublic struct Point\n{\n public double X,Y;\n\n public Point(double x, double y)\n {\n this.X = x;\n this.Y = y;\n }\n}\n\nList<Point> parkedCars = new List<Point>();\nRandom random = new Random();\n\nvoid Main()\n{\n int parked = 0;\n\n for (int i = 0; i < 12000; i++)\n {\n double x = random.NextDouble() * 100;\n double y = random.NextDouble() * 100;\n\n Point pointToPark = new Point(x, y);\n\n if (IsSafeToPark(pointToPark))\n {\n parkedCars.Add(pointToPark);\n parked++;\n }\n\n }\n\n Console.WriteLine("Parked: " + parked);\n}\n\nprivate bool IsSafeToPark(Point pointToPark)\n{\n if (parkedCars.Any(p => Distance(pointToPark, p) <= 1))\n return false;\n\n return true;\n}\n\nprivate double Distance(Point p1, Point p2)\n{\n return Math.Max(Math.Abs(p1.X - p2.X), Math.Abs(p1.Y - p2.Y));\n}\n编辑：我运行了两次测试 100 次，平均结果分别为 3521.29 和 3526.74。不确定这是否意味着还有更多的东西，但这也许只是表明 .NET 和 Fortran 之间的舍入或浮点精度差异。
\n