Dlaczego moja implementacja testu parkingu dla generatorów liczb losowych daje złe wyniki?

Question

Próbuję napisać implementację testu parkingu dla generatorów liczb losowych. Oto źródła, z których otrzymuję informacje o teście od: Intel math library documentation i Page 4 of this paper wraz z funkcją phi dla gęstości prawdopodobieństwa wymienionej na here.

Napisałem implementację testu w języku C#. Wykorzystuje siatkę 100x100, której wartości są początkowo ustawione na null. Następnie używam generatora liczb losowych do generowania losowych liczb całkowitych dla x i y. Jeśli ten indeks siatki i jej sąsiadów jest pusty, indeks zostaje ustawiony na 1. W przeciwnym razie nic się nie dzieje, ponieważ wystąpił "awaria".

Uruchomiłem go przy użyciu generatora C# System.Random. Nie wierzę, że wyniki są poprawne, ponieważ zawsze mam bardzo blisko 3079 punktów zaparkowanych, co jest około 500 razy krótsze od średniej, jaką powinienem dostać. Daje także wartość p o wartości 2.21829146215425E-90.

Mój kod znajduje się poniżej. Czy ktokolwiek ma z tym jakieś doświadczenie lub czy ktoś może zobaczyć coś, co robię nieprawidłowo w mojej implementacji? Każda pomoc będzie bardzo ceniona.

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

edycja - Problemy z mojego pierwotnego wdrożenia były

• byłem wykreślenie kwadraty zamiast dysków
• ja tylko na wykresie punktów w wartościach całkowitych. Zamiast tego powinienem był użyć wartości dziesiętnych.
• W wyniku powyższej dwóch, musiałem zmienić czek Odległość

Dzięki Chris Sinclair i kopalni Z pomocy w figurującego to. Ostateczny kod został zamieszczony poniżej.

Answer 1

Zamierzam zabić w tym kierunku, i co prawda, nie próbowałem żadnego takiego testu, więc wybaczcie mi, gdybym był daleko. Ogólnie rzecz biorąc, implementacja .NET Random jest całkiem niezła i nigdy nie miałem z tym problemów, więc nie podejrzewałem, że na początku, zwłaszcza, że ​​poprawnie wykorzystujesz to samo wystąpienie zamiast tworzyć nowe.

Czytanie z parking.pdf, a z dokumentacji Intela, wydaje się, że używają dysków i obliczają odległość od ich punktów centralnych. Twoja implementacja używa kwadratów (tablica 1 odległości między plamami), a tym samym ignorując przekątne.

Z PDF:

Jeśli były używane dyski, odległość pomiędzy cząstkami R = p (x (I) - z) 2 + (y (i) - z) 2 musiałby być mniejszy lub równy jeden. Czy ma znaczenie, czy używa się dysków lub kwadratów? Wskazanie, którego znaczenia figura geometryczna jest zaparkowana, można uzyskać za pomocą , porównując obszar zajmowany przez kwadrat strony 1,0 z obszarem dysku o średnicy 1,0. Stosunek powierzchni dysku do kwadratu wynosi π/4. Dlatego można się spodziewać, że więcej dysków będzie można umieścić w polu niż kwadraty o tej samej liczbie prób.

A doc Intel:

Test zakłada następny punkt losowy (x, y) z powodzeniem „zaparkowane”, jeśli jest na tyle daleko od każdego poprzedniego powodzeniem „zaparkowanej” punktu. wystarczająca odległość pomiędzy punktami (x1, y1) i (x2, y2) jest min (| x1 - x2 |, | y1 - y2 |)> 1.

Zgaduję, że Õ/4 stosunek dysku do kwadratu i różnice między liczbą pasujących płyt a kwadratami mogą być przyczyną, dla której widzisz inny numer. (chociaż w tej chwili nie widzę bezpośredniego związku pomiędzy 3523 a 3070 i π/4. 3523 * π/4 = 2767, który jest blisko, ale jestem pewien, że jeśli istnieje związek, to jest on nieco bardziej złożony niż zwykłe mnożenie.)

Nie jest to świetna odpowiedź, ale moje najlepsze przypuszczenia.

EDYCJA: Interesujące jest to, że zrobiłem szybką implementację używając dysków o średnicy 1 jednostki i uzyskując wyniki około 4000 zaparkowanych. (? Lub może .NET na Random nie przechodzi testu), więc może jest nieco więcej niż do tej mojego niewprawnego siebie może pojąć W każdym razie, oto moja realizacja dysk:

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

Korzystanie mój prawdopodobny zbyt proste stosowanie Wskaźnik π/4 daje około 3142. Nieco bliżej, ale wydaje się bardzo niepoprawny.

EDYCJA: Jak zauważyłem @mike z, mój test wykorzystujący bezpośredni dystans jest niepoprawny. Według parametrów testu, które zapomniałem o, po prostu sprawdza, że ​​X i Y są większe odległości niż 1. Zmiana mojego Distance czek:

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

daje znacznie bliżej wynik około 3450, co jest dość blisko. Jeśli wyjmę zaznaczenie "// upewnij się, że jest" w "pudełku", uśrednione ponad 10 prób dostaje 3531!

więc moja ostateczna, "praca" code jest:

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

EDIT: Pobiegłem test 100 razy dwa, i uśrednione wyniki do 3521.29 i 3526.74 odpowiednio. Nie jestem pewien, czy to oznacza, że ​​jest to jeszcze trochę więcej, ale być może jest to tylko wskazówka na zaokrąglenia lub zmienne różnice precyzji pomiędzy .NET i Fortran.