01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 package algs32.kdtree; import algs12.Point2D; import algs13.Queue; import stdlib.*; /* * Example output: * * 500: kd=0.041000 brute=0.035000 * 1000: kd=0.021000 brute=0.022000 * 2000: kd=0.007000 brute=0.050000 * 4000: kd=0.008000 brute=0.073000 * 8000: kd=0.018000 brute=0.156000 * 16000: kd=0.018000 brute=0.304000 * 32000: kd=0.052000 brute=0.730000 * 64000: kd=0.095000 brute=2.359000 * 128000: kd=0.163000 brute=4.735000 * 256000: kd=0.260000 brute=11.390000 * 512000: kd=1.499000 brute=27.822000 */ public class RangeSearchPerformanceTest { static int NUM_SIZES = 12; public static void main(String[] args) { Queue queue = new Queue<> (); while (queue.size () < 1000) { double x1 = Math.random (); double x2 = Math.random (); double y1 = Math.random (); double y2 = Math.random (); double xmin = Math.min (x1, x2); double xmax = Math.max (x1, x2); double ymin = Math.min (y1, y2); double ymax = Math.max (y1, y2); RectHV rect = new RectHV (xmin, ymin, xmax, ymax); if (rect.width () * rect.height () > 0.01) continue; // rectangle is too large queue.enqueue(rect); } int N = 250; for (int count=1; count