SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package bearmaps;
  2.  
  3. import org.junit.Test;
  4. import static org.junit.Assert.assertEquals;
  5. import edu.princeton.cs.algs4.Stopwatch;
  6.  
  7. import java.util.ArrayList;
  8. import java.util.List;
  9. import java.util.Random;
  10.  
  11. public class KDTreeTest {
  12.  
  13.     /* Tests code from nearest slides */
  14.     @Test
  15.     public void testNearestLecture() {
  16.         Point p1 = new Point(2, 3);
  17.         Point p2 = new Point(4, 2);
  18.         Point p3 = new Point(4, 5);
  19.         Point p4 = new Point(3, 3);
  20.         Point p5 = new Point(1, 5);
  21.         Point p6 = new Point(4, 4);
  22.         KDTree kd = new KDTree(List.of(p1, p2, p3, p4, p5, p6));
  23.  
  24.         Point actual = kd.nearest(0, 7);
  25.         Point expected = new Point(1, 5);
  26.         assertEquals(expected, actual);
  27.     }
  28.  
  29.     //Smaller random test
  30.     @Test
  31.     public void testSmallRandom() {
  32.         testNearestRandom(5000, 500);
  33.         testTiming(5000, 500);
  34.     }
  35.  
  36.     //Larger random test
  37.     @Test
  38.     public void testLargeRandom() {
  39.         testNearestRandom(100000, 10000);
  40.         testTiming(100000, 10000);
  41.     }
  42.  
  43.     /* Test Randomly with a large number of points
  44.     <a href="https://www.youtube.com/watch?v=lp80raQvE5c&feature=youtu.be">
  45.     Project 2b Walkthrough </a>
  46.      */
  47.     private void testNearestRandom(int points, int queries) {
  48.         List<Point> testPoints = createNPoints(points);
  49.         NaivePointSet naive = new NaivePointSet(testPoints);
  50.         KDTree kd = new KDTree(testPoints);
  51.  
  52.         List<Point> nearestPoints = createNPoints(queries);
  53.         for (Point p: nearestPoints) {
  54.             Point expected = naive.nearest(p.getX(), p.getY());
  55.             Point actual = kd.nearest(p.getX(), p.getY());
  56.             assertEquals(expected, actual);
  57.         }
  58.     }
  59.  
  60.     /* Test timings of naive vs kd tree
  61.     <a href="https://www.youtube.com/watch?v=3IdQJm9tw6Y&feature=youtu.be">
  62.     Project 2b Walkthrough </a>
  63.      */
  64.     private void testTiming(int points, int queries) {
  65.         List<Point> testPoints = createNPoints(points);
  66.         NaivePointSet naive = new NaivePointSet(testPoints);
  67.         KDTree kd = new KDTree(testPoints);
  68.  
  69.         List<Point> nearestPoints = createNPoints(queries);
  70.  
  71.         //Naive timing
  72.         Stopwatch sw = new Stopwatch();
  73.         for (Point p: nearestPoints) {
  74.             naive.nearest(p.getX(), p.getY());
  75.         }
  76.         double naiveTime = sw.elapsedTime();
  77.         System.out.println("Naive implementation for " + points
  78.                 + " points and " + queries + " queries."
  79.                + "\nTotal time elapsed: " + naiveTime);
  80.  
  81.         //KD tree timing
  82.         sw = new Stopwatch();
  83.         for (Point p: nearestPoints) {
  84.             kd.nearest(p.getX(), p.getY());
  85.         }
  86.         double kdTime = sw.elapsedTime();
  87.         System.out.println("KDTree implementation for " + points
  88.                +  " points and " + queries + " queries."
  89.               +  "\nTotal time elapsed: " + kdTime);
  90.     }
  91.  
  92.     //Creates random list of points of size n
  93.     private List<Point> createNPoints(int n) {
  94.         List<Point> points = new ArrayList<>();
  95.         Random r = new Random(500);
  96.         for (int i = 0; i < 5000; i++) {
  97.             Point temp = new Point(r.nextDouble(), r.nextDouble());
  98.             points.add(temp);
  99.         }
  100.         return points;
  101.     }
  102. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top