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}