爲什麼我對隨機數發生器產生不良結果的停車場測試實施？

Question

我正在嘗試爲隨機數生成器編寫停車場測試的實現。以下是我獲得有關測試信息的來源：Intel math library documentation和Page 4 of this paper以及列出的概率密度的phi函數here。

我在C＃中編寫了一個測試的實現。它使用其值初始設置爲空的100x100網格。然後我使用隨機數生成器爲x和y生成隨機整數。如果該網格的索引和它的鄰居是空的，那麼該索引將被設置爲1.否則，沒有任何反應，因爲發生了「崩潰」。

我使用C＃System.Random生成器運行它。我不相信結果是正確的，因爲我總是得到接近3079點的停車位，這是我應該得到的平均值的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辛克萊和礦山z計算幫助搞清楚了這一點。最終的代碼發佈在下面。

Answer 1

我要對此進行一次刺探，但我承認，我沒有嘗試過任何這樣的測試，所以請原諒我，如果我走了。一般來說，.NET Random的實現非常好，我從來沒有遇到過任何問題，所以我不會懷疑最初特別是因爲您正確地重用相同的實例，而不是創建新的實例。

從parking.pdf中閱讀並從英特爾文檔中，似乎他們正在使用光盤，並計算與其中心點的距離。你的實現是使用正方形（點之間有1個距離的數組），因此忽略對角線。

從PDF：

如果正在使用圓盤時，顆粒之間的距離R = P（X（I） - Z）2 +（Y（I） - Z）2將需要小於或等於1。 是否使用磁盤或方塊有什麼關係？ 可以通過 比較由邊1.0的正方形佔據的面積與直徑爲1.0的 盤的面積來獲得哪個幾何圖形停放的重要性的指示。面積與面積的比值是π/ 4。 因此，可以預料，在相同次數的嘗試中，可以將一個盒子中的更多磁盤置於 中。

和英特爾文檔：

的測試假設下一個隨機點（x，y）的成功「停」，如果 是遠遠不夠的每一個成功之前的「停」點。點（X1，Y1）和（X2，Y2）之間的 足夠的距離是 分鐘（| 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之間四捨五入或浮點精度差異的指示。