Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I'm going to take a stab at this, and admittedly, I have not attempted any such test, so forgive me if I'm way off. In general though, the .NET <code>Random</code> implementation is pretty good and I've never had issues with it, so I wouldn't suspect that initially especially since you're properly reusing the same instance instead of creating new ones.</p> <p>Reading from the parking.pdf, and from the Intel documentation, it seems that they're using discs, and compute the distance from their centre points. Your implementation is using squares (array of 1 distance between spots) and thus ignoring diagonals.</p> <p>From the pdf:</p> <blockquote> <p>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.</p> </blockquote> <p>And the Intel doc:</p> <blockquote> <p>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.</p> </blockquote> <p>I'm guessing that the π/4 disk to square ratio and the differences between how many discs can fit vs squares might be why you're seeing a different number. (although right now I fail to see a directly relationship between 3523 and 3070 and π/4. 3523 * π/4 = 2767, which is close, but I'm sure if there's a relationship it's slightly more complex than just simple multiplication.)</p> <p>Not a great answer, but my best guess.</p> <p>EDIT: Interestingly enough, I did a quick implementation using discs with 1 unit diameter and getting results around 4000 parked. So maybe there's a bit more to this than my untrained self can grasp (or maybe .NET's <code>Random</code> doesn't pass the test?) Anyway, here's my disc implementation:</p> <pre><code>List&lt;Point&gt; parkedCars = new List&lt;Point&gt;(); Random random = new Random(); void Main() { int parked = 0; for (int i = 0; i &lt; 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 &lt; 0.5 || pointToPark.X &gt; 99.5 || pointToPark.Y &lt; 0.5 || pointToPark.Y &gt; 99.5) return false; if (parkedCars.Any(p =&gt; Distance(pointToPark, p) &lt;= 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)); } </code></pre> <p>Using my likely too simple application of the π/4 ratio yields about 3142. A bit closer, but it seems very incorrect.</p> <p>EDIT: As @mike z pointed out, my test using directly distance is incorrect. According to the parameters of the test, which I forgot about, just checks that the X and Y distance are greater than 1. Changing my <code>Distance</code> check to:</p> <pre><code>Math.Max(Math.Abs(p1.X - p2.X), Math.Abs(p1.Y - p2.Y)) </code></pre> <p>Yields a much closer result around 3450, which is pretty close. If I take out my "//make sure it's "inside" the box" check, averaged over 10 tries gets 3531!</p> <p>So my final, "working" code is:</p> <pre><code>public struct Point { public double X,Y; public Point(double x, double y) { this.X = x; this.Y = y; } } List&lt;Point&gt; parkedCars = new List&lt;Point&gt;(); Random random = new Random(); void Main() { int parked = 0; for (int i = 0; i &lt; 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 =&gt; Distance(pointToPark, p) &lt;= 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)); } </code></pre> <p>EDIT: I ran the test 100 times twice, and averaged the results to 3521.29 and 3526.74 respectively. Not sure if this means there <em>still</em> something slightly more to this, but perhaps this is just indicative of rounding or floating point precision differences between .NET and Fortran.</p>
    singulars
    1. This table or related slice is empty.
    1. POWhy is my implementation of the parking lot test for random number generators producing bad results?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USChris Sinclair
    1. USChris Sinclair
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWhy is my implementation of the parking lot test for random number generators producing bad results?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou're close. The test does use squares, but the key is using doubles for possible positions rather than ints. If you change your check for distance to `return Math.Max(Math.Abs(p1.X - p2.X), Math.Abs(p1.Y - p2.Y));` then you've got it.
      singulars
      1. PO
      1. USmike z
    2. COAhh, yeah you're right. I was taking a second look at the Intel page and noticed they're just testing for a single axis. (which I'm not 100% sure is correct). However, my test _is_ using doubles (`Point` is double X/Y. `Math.Max(Math.Abs(p1.X - p2.X), Math.Abs(p1.Y - p2.Y))` yield a collision _if_ the disc is `0.70711, 0.70711` along the diagonal (which would still physically fit), but I suppose is outside the constraints of the test.
      singulars
      1. PO
      1. USChris Sinclair
    3. COI noticed the same thing on the intel page for checking only one axis. If I read it correctly, the intel doc said that the two points (600,3) and (0, 3) would fail for being too close since 3-3 = 0 < 1. Chris, I made some changes to align with your code and I'm having the same results of about 4000. I'm looking at it more now.
      singulars
      1. PO
      1. USChris Dibble
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload