Java program compares the execution time to ArrayList and LinkedList
Mission
//Sample output (text version & graphic version)
ADD:
ArrayList: 0.048 Sec
LinkedList: 1.803 Sec
ArrayList is 37.6 times faster than LinkedList
Search:
ArrayList: 8.156 Sec
LinkedList: 11.508 Sec
ArrayList is 1.4 times faster than LinkedList
Remove:
ArrayList: 3.791 Sec
LinkedList: 4.292 Sec
ArrayList is 1.1 times faster than LinkedList
Write a Java program that compares the execution(processing) time of “add”, “search”, and “remove” to ArrayList and LinkedList.
This assignment is to test which data structure is faster.
The test is divided into three parts: add, search and remove, and measures the time required for add, search, and remove.
First, create a large amount of data and indexes to store the data.
Next, with the data created, three tests (add, search, remove) are performed on ArrayList and LinkedList, and the execution time for each action is summed up to see which structure took how much time.
The processing time should be displayed in both text version and GUI version at the same time. (a graphic class for this assignment is provided)
The text version should include a comparison of each data structure. (see previous slide)
eg) ArrayList is 37.6 times faster than LinkedList
Overview
Overall Structure
Bar211
Graphic class
Your program
ADD:
ArrayList: 0.048 Sec
LinkedList: 1.803 Sec
ArrayList is 37.6 times faster than LinkedList
Search:
ArrayList: 8.156 Sec
LinkedList: 11.508 Sec
ArrayList is 1.4 times faster than LinkedList
Remove:
ArrayList: 3.791 Sec
LinkedList: 4.292 Sec
ArrayList is 1.1 times faster than LinkedList
static void add(){
for (int i=0; i<howManyTests; i++){
// arrayList
startTime = System.currentTimeMillis();
// add value
endTime = System.currentTimeMillis();
TimeAdd_ArrayList += endTime - startTime;
bar.setTimeAddAL(TimeAdd_ArrayList);
// LinkedList
. . .
}
}
static void search(){
for (int i=0; i<howManyTests; i++){
value = nextWord(10);
// arrayList
. . .
// LinkedList
. . .
}
...
}
. . . .
public static void main(String[] args) {
bar = new Bar211("your name", howManyTests);
add();
search();
remove();
}
graphic output
text output
call method
See Assignment4OUTLINE for details
Submission (1 java file + 1 pdf file)
Your program (Assignment4.java)
Screen capture of your text output
Screen capture of your graphic output
Copy and paste them into one file.
** No need to upload Bar211.
You MUST include your first and last name, your student ID, the date, a short description of the program’s function, and comments necessary to explain the operation of your program
0. Preparation
Download bar211.java from the canvas -> Assignments -> Assignment -> Assignment 4 and save it to your project folder.
This is the same way we did in Assignment 2 (Burger 211). See slide # 10~11 (Week 3-1 Assignment 2 Discussion)
static ArrayList<String> AL = new ArrayList<>();
static LinkedList<String> LL = new LinkedList<>();
static double TimeAdd_ArrayList; // Accumulated processing time when adding to ArrayList.
static double TimeAdd_LinkedList; // Accumulated processing time when adding to LinkedList.
static double TimeSearch_ArrayList; // Accumulated processing time when searching from ArrayList.
static double TimeSearch_LinkedList; // Accumulated processing time when searching from LinkedList.
static double TimeRemove_ArrayList; // Accumulated processing time when removing from ArrayList.
static double TimeRemove_LinkedList; // Accumulated processing time when removing from LinkedList.
static int howMany=18000; // total test time
static double startTime, endTime, totalTime;
//add more if you would like to upgrade your program.
1. Possible Data structures and variables
2. How to generate index and value
index
Generate a random integer number within the size of the ArrayList/LinkedList
eg) int index = rand(ArrayList.size());
value (String of length 10)
Create a method to generate random string of length 10.
You may upgrade and use your newRandom class (Assignment 1) or use mine.
3. How to test ADD
generate index
(integer)
generate a value
(String of length 10)
ArrayList
LinkedList
AL.add(index, value);
LL.add(index, value);
Repeat 18,000+ times (You may change the number)
accumulate ‘add’ processing time
accumulate ‘add’ processing time
int index = rand(ArrayList.size());
FYI:
AL.add(3, “A”);
LL.add(3, “A”);
Actual meaning of ‘index’ in ArrayList and LinkedList
AL.add(index, value);
LL.add(index, value);
front
| A |
| - | - | - | A | - | - | - | - |
A[0]
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
ArrayList
LinkedList
0
1
2
3
real index
logical index
(number of times you need to iterate)
After “add” 10,000 strings to the ArrayList and LinkedList, the data structures might look like this.
(18,000 strings)
csqahduskr
jjskeufhdk
hoemxzjfut
ojotsamzgq
.
.
.
(18,000 strings)
csqahduskr
jjskeufhdk
hoemxzjfut
ojotsamzgq
.
.
.
ArrayList
LinkedList
Use these data for “search” and “remove”.
4. How to test SEARCH
search index of the value
generate a value
(String of length 10)
ArrayList
LinkedList
Repeat 18,000+ times (You may change the number)
csqahduskr
jjskeufhdk
hoemxzjfut
ojotsamzgq
.
.
csqahduskr
jjskeufhdk
hoemxzjfut
ojotsamzgq
.
.
accumulate processing time
accumulate processing time
* In this assignment, “search” means finding the index of a value.
4. How to test REMOVE
Remove the value
generate a value
(String of length 10)
ArrayList
LinkedList
Repeat 18,000+ times (You may change the number)
csqahduskr
jjskeufhdk
hoemxzjfut
ojotsamzgq
.
.
csqahduskr
jjskeufhdk
hoemxzjfut
ojotsamzgq
.
.
accumulate processing time
accumulate processing time
import java.util. * ; public class timeChecker { static double startTime, endTime, totalTime; public static void main(String[] args) { startTime = System.currentTimeMillis();
// // some statements //
endTime = System.currentTimeMillis();
totalTime = (endTime - startTime)/1000.0; // in second } }
5. How to check processing time
// processing time for these statements