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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
package algs14;
import java.util.Arrays;
import stdlib.*;
public class PlaygroundSearch {
/* Return true if val is in the list */
public static boolean contains (double val, double[] list) {
return StdRandom.bernoulli(); // TODO
}
public static void main (String[] args) {
//printTest(1023);
correctnessTest();
performanceTest();
}
private static void correctnessTest () {
correctnessHelper (true, 11, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (true, 21, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (true, 31, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (true, 41, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (true, 51, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (true, 61, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (true, 71, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (false, 10, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (false, 20, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (false, 30, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (false, 40, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (false, 50, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (false, 60, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (false, 70, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (false, 80, new double[] { 11, 21, 31, 41, 51, 61, 71 });
correctnessHelper (true, 11, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (true, 21, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (true, 31, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (true, 41, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (true, 51, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (true, 61, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (false, 10, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (false, 20, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (false, 30, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (false, 40, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (false, 50, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (false, 60, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (false, 70, new double[] { 11, 21, 31, 41, 51, 61 });
correctnessHelper (false, 0, new double[] { });
correctnessHelper (true, 11, new double[] { 11 });
correctnessHelper (false, 10, new double[] { 11 });
correctnessHelper (false, 20, new double[] { 11 });
correctnessHelper (true, 11, new double[] { 11, 21 });
correctnessHelper (true, 21, new double[] { 11, 21 });
correctnessHelper (false, 10, new double[] { 11, 21 });
correctnessHelper (false, 20, new double[] { 11, 21 });
correctnessHelper (false, 30, new double[] { 11, 21 });
StdOut.println ("Finished tests");
}
private static void correctnessHelper (boolean expected, double val, double[] list) {
boolean actual = contains (val, list);
if (expected != actual) {
StdOut.format ("Failed: Expecting [%b] Actual [%b] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list));
}
}
private static void performanceTest () {
int MIN = 256; // for powers of ten, start with 500L
int MAX = 320000000;
double prevTime = performanceHelper(MIN);
for (int N = MIN*2; N <= MAX; N=N*2) {
double time = performanceHelper(N);
StdOut.format ("Elapsed count N=%,13d [%10.3f : %10.3f]\n", N, time, time/prevTime);
prevTime = time;
}
}
private static double performanceHelper (int N) {
double[] list = ArrayGenerator.doubleRandomUnique(N);
//double val = StdRandom.uniform (N); // gauranteed to succeed
double val = N; // gauranteed to fail
Stopwatch sw = new Stopwatch ();
contains (val, list);
return sw.elapsedTime ();
}
// To print values, paste these in the code:
// StdOut.format("%4d/%4d \n", lo, hi);
// StdOut.format("%4d ", hi-lo+1);
private static void printTest (int N) {
double[] list = ArrayGenerator.doubleSortedUnique(N);
StdOut.println (Arrays.toString(list).substring(0, 50) + "...");
int found = 0;
int count = 10;
for (int i=1; i<=count; i++) {
double val = StdRandom.uniform (N+1);
if (StdRandom.bernoulli())
val = val - 0.5;
if (contains (val, list))
found = found + 1;
StdOut.println();
}
StdOut.format("found %4d/%4d", found, count);
}
}
|
