Assignment 8 - Data Structures 1¶
Assignment¶
For each program below:
- Tell me what the program does. Show what it prints.
- Explain the results of the program. What is it doing and printing?
- Try to explain WHY the results are what they are. If you don’t know for certain, create a hypothesis.
- This has a lot to do with data structures. Make sure your explanation does dive into the particulars of the data structures and what is happening. Don’t give a “surface” explanation, make sure you understand. Ask me questions if needed or check to make sure your are in the right ballpark. This assignment is the easiest to get a bad grade on if you don’t check to make sure.
Part 1¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | import java.util.LinkedList;
public class Test01 {
private static int n = 10000000;
private static void link_list_add_test() {
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i=0; i < n; i++) {
// Look up the documentation for the following command
list.add(0, 0);
}
}
public static void main(String [] args) {
System.out.println("Starting test...");
double total_duration = 0.0;
for(int test=0; test < 20; test++) {
long startTime = System.nanoTime();
link_list_add_test();
long endTime = System.nanoTime();
double duration = (endTime - startTime) / 1000000000.;
total_duration += duration;
System.out.println(String.format("Test took %f seconds.", duration));
}
System.out.println(String.format("Total test took %f seconds.", total_duration));
}
}
|
Part 2¶
1 2 3 4 5 6 7 8 9 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 | import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
public class Test02 {
private static int n = 10000000;
private static void link_list_add_test() {
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i=0; i < n; i++) {
// Note, this command is different than the one in
// the prior example!
list.add(0);
}
}
private static void array_add_test() {
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0; i < n; i++) {
list.add(0);
}
}
private static void stack_add_test() {
Stack<Integer> stack = new Stack<Integer>();
for(int i=0; i < n; i++) {
stack.add(0);
}
}
public static void main(String [] args) {
System.out.println("Warming up...");
for(int test=0; test < 20; test++) {
array_add_test();
}
double total_duration = 0.0;
System.out.println("Starting array_add_test test...");
for(int test=0; test < 20; test++) {
long startTime = System.nanoTime();
array_add_test();
long endTime = System.nanoTime();
double duration = (endTime - startTime) / 1000000000.;
total_duration += duration;
System.out.println(String.format("array_add_test test took %f seconds.", duration));
}
System.out.println(String.format("Total array_add_test took %f seconds.", total_duration));
total_duration = 0.0;
System.out.println("Starting link_list_add_test test...");
for(int test=0; test < 20; test++) {
long startTime = System.nanoTime();
link_list_add_test();
long endTime = System.nanoTime();
double duration = (endTime - startTime) / 1000000000.;
total_duration += duration;
System.out.println(String.format("link_list_add_test test took %f seconds.", duration));
}
System.out.println(String.format("Total link_list_add_test took %f seconds.", total_duration));
total_duration = 0.0;
System.out.println("Starting stack_add_test test...");
for(int test=0; test < 20; test++) {
long startTime = System.nanoTime();
stack_add_test();
long endTime = System.nanoTime();
double duration = (endTime - startTime) / 1000000000.;
total_duration += duration;
System.out.println(String.format("stack_add_test test took %f seconds.", duration));
}
System.out.println(String.format("Total stack_add_test took %f seconds.", total_duration));
}
}
|
Part 3¶
1 2 3 4 5 6 7 8 9 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 | import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
public class Test04 {
public static int n = 100000;
public static void link_list_access_test() {
LinkedList<Integer> list = new LinkedList<Integer>();
for(int i=0; i < n; i++) {
list.add(0, 0);
}
long startTime = System.nanoTime();
for(int i = 0; i < n; i++) {
int x = list.get(i);
}
long endTime = System.nanoTime();
double duration = (endTime - startTime) / 1000000000.;
System.out.println(String.format("link_list_access_test test took %f seconds.", duration));
}
public static void array_access_test() {
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0; i < n; i++) {
list.add(0,0);
}
long startTime = System.nanoTime();
for(int i = 0; i < n; i++) {
int x = list.get(i);
}
long endTime = System.nanoTime();
double duration = (endTime - startTime) / 1000000000.;
System.out.println(String.format("array_add_test test took %f seconds.", duration));
}
public static void stack_access_test() {
Stack<Integer> stack = new Stack<Integer>();
for(int i=0; i < n; i++) {
stack.add(0, 0);
}
long startTime = System.nanoTime();
for(int i = 0; i < n; i++) {
int x = stack.get(i);
}
long endTime = System.nanoTime();
double duration = (endTime - startTime) / 1000000000.;
System.out.println(String.format("stack_access_test test took %f seconds.", duration));
}
public static void main(String [] args) {
link_list_access_test();
link_list_access_test();
array_access_test();
stack_access_test();
}
}
|