001package algs14; 002import java.util.Arrays; 003import stdlib.*; 004 005public class PlaygroundSearch { 006 /* Return true if val is in the list */ 007 public static boolean contains (double val, double[] list) { 008 return StdRandom.bernoulli(); // TODO 009 } 010 011 public static void main (String[] args) { 012 //printTest(1023); 013 correctnessTest(); 014 performanceTest(); 015 } 016 private static void correctnessTest () { 017 correctnessHelper (true, 11, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 018 correctnessHelper (true, 21, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 019 correctnessHelper (true, 31, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 020 correctnessHelper (true, 41, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 021 correctnessHelper (true, 51, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 022 correctnessHelper (true, 61, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 023 correctnessHelper (true, 71, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 024 correctnessHelper (false, 10, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 025 correctnessHelper (false, 20, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 026 correctnessHelper (false, 30, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 027 correctnessHelper (false, 40, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 028 correctnessHelper (false, 50, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 029 correctnessHelper (false, 60, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 030 correctnessHelper (false, 70, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 031 correctnessHelper (false, 80, new double[] { 11, 21, 31, 41, 51, 61, 71 }); 032 correctnessHelper (true, 11, new double[] { 11, 21, 31, 41, 51, 61 }); 033 correctnessHelper (true, 21, new double[] { 11, 21, 31, 41, 51, 61 }); 034 correctnessHelper (true, 31, new double[] { 11, 21, 31, 41, 51, 61 }); 035 correctnessHelper (true, 41, new double[] { 11, 21, 31, 41, 51, 61 }); 036 correctnessHelper (true, 51, new double[] { 11, 21, 31, 41, 51, 61 }); 037 correctnessHelper (true, 61, new double[] { 11, 21, 31, 41, 51, 61 }); 038 correctnessHelper (false, 10, new double[] { 11, 21, 31, 41, 51, 61 }); 039 correctnessHelper (false, 20, new double[] { 11, 21, 31, 41, 51, 61 }); 040 correctnessHelper (false, 30, new double[] { 11, 21, 31, 41, 51, 61 }); 041 correctnessHelper (false, 40, new double[] { 11, 21, 31, 41, 51, 61 }); 042 correctnessHelper (false, 50, new double[] { 11, 21, 31, 41, 51, 61 }); 043 correctnessHelper (false, 60, new double[] { 11, 21, 31, 41, 51, 61 }); 044 correctnessHelper (false, 70, new double[] { 11, 21, 31, 41, 51, 61 }); 045 correctnessHelper (false, 0, new double[] { }); 046 correctnessHelper (true, 11, new double[] { 11 }); 047 correctnessHelper (false, 10, new double[] { 11 }); 048 correctnessHelper (false, 20, new double[] { 11 }); 049 correctnessHelper (true, 11, new double[] { 11, 21 }); 050 correctnessHelper (true, 21, new double[] { 11, 21 }); 051 correctnessHelper (false, 10, new double[] { 11, 21 }); 052 correctnessHelper (false, 20, new double[] { 11, 21 }); 053 correctnessHelper (false, 30, new double[] { 11, 21 }); 054 StdOut.println ("Finished tests"); 055 } 056 private static void correctnessHelper (boolean expected, double val, double[] list) { 057 boolean actual = contains (val, list); 058 if (expected != actual) { 059 StdOut.format ("Failed: Expecting [%b] Actual [%b] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list)); 060 } 061 } 062 private static void performanceTest () { 063 int MIN = 256; // for powers of ten, start with 500L 064 int MAX = 320000000; 065 double prevTime = performanceHelper(MIN); 066 for (int N = MIN*2; N <= MAX; N=N*2) { 067 double time = performanceHelper(N); 068 StdOut.format ("Elapsed count N=%,13d [%10.3f : %10.3f]\n", N, time, time/prevTime); 069 prevTime = time; 070 } 071 } 072 private static double performanceHelper (int N) { 073 double[] list = ArrayGenerator.doubleRandomUnique(N); 074 //double val = StdRandom.uniform (N); // gauranteed to succeed 075 double val = N; // gauranteed to fail 076 Stopwatch sw = new Stopwatch (); 077 contains (val, list); 078 return sw.elapsedTime (); 079 } 080 081 // To print values, paste these in the code: 082 // StdOut.format("%4d/%4d \n", lo, hi); 083 // StdOut.format("%4d ", hi-lo+1); 084 private static void printTest (int N) { 085 double[] list = ArrayGenerator.doubleSortedUnique(N); 086 StdOut.println (Arrays.toString(list).substring(0, 50) + "..."); 087 int found = 0; 088 int count = 10; 089 for (int i=1; i<=count; i++) { 090 double val = StdRandom.uniform (N+1); 091 if (StdRandom.bernoulli()) 092 val = val - 0.5; 093 if (contains (val, list)) 094 found = found + 1; 095 StdOut.println(); 096 } 097 StdOut.format("found %4d/%4d", found, count); 098 } 099}