खराब परिणाम उत्पन्न करने वाले यादृच्छिक संख्या जेनरेटर के लिए पार्किंग लॉट परीक्षण का मेरा कार्यान्वयन क्यों है?

Question

मैं यादृच्छिक संख्या जेनरेटर के लिए पार्किंग लॉट परीक्षण के कार्यान्वयन को लिखने की कोशिश कर रहा हूं। यहां स्रोत हैं कि मुझे परीक्षण के बारे में मेरी जानकारी मिल रही है: Intel math library documentation और Page 4 of this paper संभाव्यता घनत्व के लिए phi फ़ंक्शन के साथ here सूचीबद्ध है।

मैंने सी # में परीक्षण का कार्यान्वयन लिखा था। यह 100x100 ग्रिड का उपयोग करता है जिसका मूल्य प्रारंभ में शून्य पर सेट होता है। मैं फिर एक्स और वाई के लिए यादृच्छिक पूर्णांक उत्पन्न करने के लिए यादृच्छिक संख्या जेनरेटर का उपयोग करता हूं। यदि ग्रिड और उसके पड़ोसियों का वह सूचकांक खाली है, तो वह सूचकांक 1 पर सेट हो जाता है। अन्यथा, कुछ भी नहीं होता क्योंकि "क्रैश" होता था।

मैंने इसे सी # सिस्टम का उपयोग करके चलाया। यादृच्छिक जनरेटर। मुझे विश्वास नहीं है कि परिणाम सही हैं क्योंकि मुझे हमेशा 3079 अंक पार्क किए जाते हैं, जो मुझे प्राप्त होने वाले औसत से लगभग 500 छोटा है। यह 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)); 
    } 

संपादित करें - अपने मूल कार्यान्वयन से जुड़ी समस्याओं थे

• मैं डिस्क
• मैं केवल पूर्णांक मूल्यों पर अंक साजिश रची साजिश रचने के बजाय चौकोर था। मुझे इसके बजाय दशमलव मानों का उपयोग करना चाहिए था।
• उपरोक्त दो का एक परिणाम के रूप में, मैं अपने दूरी की जांच यह पता लगाना में मदद के लिए क्रिस सिंक्लेयर और मेरा जेड को

धन्यवाद बदलने के लिए की जरूरत है। अंतिम कोड नीचे पोस्ट किया गया है।

Answer 1

मैं इस पर एक स्टैब लेने जा रहा हूं, और स्वीकार्य रूप से, मैंने इस तरह के किसी भी परीक्षण का प्रयास नहीं किया है, इसलिए अगर मैं रास्ता निकाल रहा हूं तो मुझे माफ़ कर दो। सामान्य रूप से, .NET Random कार्यान्वयन बहुत अच्छा है और मुझे इसके साथ कोई समस्या नहीं है, इसलिए मुझे संदेह नहीं होगा कि शुरुआत में विशेष रूप से जब आप नए बनाने के बजाय एक ही उदाहरण का सही उपयोग कर रहे हैं।

पार्किंग.pdf से पढ़ना, और इंटेल दस्तावेज़ से, ऐसा लगता है कि वे डिस्क का उपयोग कर रहे हैं, और उनके केंद्र बिंदुओं से दूरी की गणना करते हैं। आपका कार्यान्वयन वर्गों (धब्बे के बीच 1 दूरी की सरणी) का उपयोग कर रहा है और इस प्रकार विकर्णों को अनदेखा कर रहा है।

पीडीएफ से:

डिस्क इस्तेमाल किए जा रहे हैं, तो कणों के बीच की दूरी r = p (x (i) - जेड) 2 + (y (i) - जेड) 2 की आवश्यकता होगी एक से कम या बराबर होना। क्या इससे कोई फर्क पड़ता है कि कोई डिस्क या वर्ग का उपयोग करता है या नहीं? का संकेत जो कि ज्यामितीय आंकड़ा पार्क किया गया है, द्वारा व्यास 1.0 की डिस्क के क्षेत्र में पक्ष 1.0 के एक वर्ग द्वारा कब्जा कर लिया गया क्षेत्र की तुलना करके प्राप्त किया जा सकता है। क्षेत्रों का अनुपात, वर्ग से डिस्क, π/4 है। इसलिए, यह अनुमान लगाया जाएगा कि अधिक डिस्क को में एक ही संख्या में प्रयासों की तुलना में एक बॉक्स में रखा जा सकता है।

और इंटेल डॉक:

परीक्षण, एक अगले यादृच्छिक बिंदु मान लिया गया है (एक्स, वाई) को सफलतापूर्वक "पार्क किए गए" अगर यह हर पिछले सफलतापूर्वक "पार्क किए गए" बिंदु से काफी दूर तक है। (| - |, | y1 - y2 | x2 x1)> 1.

मुझे लगता है कि π अनुमान लगा रहा हूँ अंक (x1, y1) और (x2, y2) के बीच पर्याप्त दूरी मिनट है/4 डिस्क से वर्ग अनुपात और बनाम वर्गों के बीच कितने डिस्क फिट हो सकते हैं, इसके बीच अंतर हो सकता है कि आप एक अलग संख्या क्यों देख रहे हैं। (हालांकि अभी मैं 3523 और 3070 और π/4 के बीच सीधे संबंध देखने में असफल रहा हूं। 3523 * π/4 = 2767, जो करीब है, लेकिन मुझे यकीन है कि अगर कोई संबंध है तो यह साधारण गुणा से थोड़ा अधिक जटिल है।)

कोई अच्छा जवाब नहीं है, लेकिन मेरा सबसे अच्छा अनुमान है।

संपादित करें: दिलचस्प बात यह है कि मैंने 1 यूनिट व्यास वाले डिस्क का उपयोग करके त्वरित कार्यान्वयन किया और लगभग 4000 पार्क किए गए परिणाम प्राप्त किए। (? या शायद नेट के 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 के आसपास पैदा होता है। थोड़ा करीब है, लेकिन यह बहुत गलत लगता है।

संपादित करें: जैसा कि @ माइक जेड ने इंगित किया है, मेरी परीक्षा सीधे दूरी का उपयोग कर गलत है। परीक्षण के मापदंडों, जो मैं के बारे में भूल के अनुसार, बस की जाँच करता है कि एक्स और वाई की दूरी से भी 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 के बीच गोल या सटीक बिंदु सटीक अंतर का संकेतक है।