001package algs32.kdtree;
002import algs12.Point2D;
003import algs13.Queue;
004import stdlib.*;
005
006/*
007 * Example output:
008 *
009 * 500: kd=0.041000 brute=0.035000
010 * 1000: kd=0.021000 brute=0.022000
011 * 2000: kd=0.007000 brute=0.050000
012 * 4000: kd=0.008000 brute=0.073000
013 * 8000: kd=0.018000 brute=0.156000
014 * 16000: kd=0.018000 brute=0.304000
015 * 32000: kd=0.052000 brute=0.730000
016 * 64000: kd=0.095000 brute=2.359000
017 * 128000: kd=0.163000 brute=4.735000
018 * 256000: kd=0.260000 brute=11.390000
019 * 512000: kd=1.499000 brute=27.822000
020 */
021public class RangeSearchPerformanceTest {
022
023        static int NUM_SIZES = 12;
024        public static void main(String[] args) {
025                Queue<RectHV> queue = new Queue<> ();
026                while (queue.size () < 1000) {
027                        double x1 = Math.random ();
028                        double x2 = Math.random ();
029                        double y1 = Math.random ();
030                        double y2 = Math.random ();
031                        double xmin = Math.min (x1, x2);
032                        double xmax = Math.max (x1, x2);
033                        double ymin = Math.min (y1, y2);
034                        double ymax = Math.max (y1, y2);
035                        RectHV rect = new RectHV (xmin, ymin, xmax, ymax);
036                        if (rect.width () * rect.height () > 0.01)
037                                continue;  // rectangle is too large
038                        queue.enqueue(rect);
039                }
040                int N = 250;
041                for (int count=1; count<NUM_SIZES; count++) {
042                        N += N;
043                        PointSET brute = new PointSET();
044                        KdTree kdtree = new KdTree();
045
046                        for (int i=0; i<N; i++) {
047                                Point2D p = new Point2D(Math.random(), Math.random());
048                                RangeSearchCorrectnessTest.insert (kdtree, p);
049                                brute.insert(p);
050                        }
051                        Stopwatch sw1 = new Stopwatch ();
052                        for (RectHV r : queue)
053                                RangeSearchCorrectnessTest.range (kdtree, r);
054                        double d1 = sw1.elapsedTime ();
055
056                        Stopwatch sw2 = new Stopwatch ();
057                        for (RectHV r : queue)
058                                brute.range (r);
059                        double d2 = sw2.elapsedTime ();
060
061                        StdOut.format ("%d: kd=%f brute=%f\n", N, d1, d2);
062                }
063        }
064}