001package algs32.kdtree;
002import algs12.Point2D;
003import algs13.Queue;
004import stdlib.*;
005
006/*
007 * If the output looks like this, then you have a bug!
008 *
009 * 500: kd=0.146000 brute=0.021000
010 * 1000: kd=0.034000 brute=0.015000
011 * 2000: kd=0.052000 brute=0.032000
012 * 4000: kd=0.082000 brute=0.053000
013 * 8000: kd=0.175000 brute=0.108000
014 * 16000: kd=0.308000 brute=0.224000
015 * 32000: kd=0.649000 brute=0.508000
016 * 64000: kd=1.329000 brute=2.123000
017 * 128000: kd=3.375000 brute=4.144000
018 * 256000: kd=7.147000 brute=10.214000
019 * 512000: kd=18.383000 brute=26.161000
020 *
021 * Output should look like this:
022 *
023 * 500: kd=0.054000 brute=0.026000
024 * 1000: kd=0.036000 brute=0.018000
025 * 2000: kd=0.008000 brute=0.038000
026 * 4000: kd=0.011000 brute=0.063000
027 * 8000: kd=0.013000 brute=0.178000
028 * 16000: kd=0.019000 brute=0.274000
029 * 32000: kd=0.037000 brute=0.895000
030 * 64000: kd=0.050000 brute=2.099000
031 * 128000: kd=0.089000 brute=4.416000
032 * 256000: kd=0.082000 brute=10.716000
033 * 512000: kd=3.682000 brute=27.141000
034 *
035 * This is also okay:
036 *
037 * 500: kd=0.002000 brute=0.033000
038 * 1000: kd=0.001000 brute=0.014000
039 * 2000: kd=0.000000 brute=0.034000
040 * 4000: kd=0.000000 brute=0.098000
041 * 8000: kd=0.000000 brute=0.197000
042 * 16000: kd=0.001000 brute=0.407000
043 * 32000: kd=0.000000 brute=1.654000
044 * 64000: kd=0.000000 brute=3.241000
045 * 128000: kd=0.000000 brute=6.194000
046 * 256000: kd=0.000000 brute=13.980000
047
048 */
049public class NearestNeighborPerformanceTest {
050
051        static int NUM_SIZES = 11;
052        public static void main(String[] args) {
053
054                Queue<Point2D> queue = new Queue<> ();
055                for (int i=0; i<1000; i++)
056                        queue.enqueue(new Point2D(Math.random(), Math.random()));
057
058                int N = 250;
059                for (int count=1; count<NUM_SIZES; count++) {
060                        N += N;
061                        PointSET brute = new PointSET();
062                        KdTree kdtree = new KdTree();
063
064                        for (int i=0; i<N; i++) {
065                                Point2D p = new Point2D(Math.random(), Math.random());
066                                NearestNeighborCorrectnessTest.insert (kdtree, p);
067                                brute.insert(p);
068                        }
069                        Stopwatch sw1 = new Stopwatch ();
070                        for (Point2D p : queue)
071                                NearestNeighborCorrectnessTest.nearest (kdtree, p);
072                        double d1 = sw1.elapsedTime ();
073
074                        Stopwatch sw2 = new Stopwatch ();
075                        for (Point2D p : queue)
076                                brute.nearest (p);
077                        double d2 = sw2.elapsedTime ();
078
079                        StdOut.format ("%d: kd=%f brute=%f\n", N, d1, d2);
080                }
081        }
082}