JAVA* At this point you will test how array bag and Linked bag implementations c
ID: 3597370 • Letter: J
Question
JAVA*
At this point you will test how array bag and Linked bag implementations compare with respect to the time it takes some methods to execute. We will test getCurrentSize(); contains(T anEntry); add(T anEntry); GetFrequencyOf(T anEntry); and remove(T anEntry.
a) Create an array-based bag that contains 100,000 random integers between 0 and 100,000
b) Get the bag size (it should match 100,000) (how long did this take in nanoseconds?)
c) Test whether the bag contains the perfect number 8128 (how long did this take in nanoseconds?)
d) Remove the last number from the bag, even if it is 8128 (how long did this take in nanoseconds?)
e) Add the number 8128 (the size of the bag should not have changed at this point. (how long did thid take in nanoseconds?)
f) Determine the frequency with which 8128 occurs (this could be 1). (how long did this take in nanoseconds?)
g) Double the size of the bag to 200,000 and fill the the bag with 100.000 more random integers while maintaining the same 100,000 integers that are already there. Clearly a call to the add method will return false if a fixed size array is used to to implement the ADT bag. Therefore we need to re-size the array, but maintain the name of the old array.
Explanation / Answer
Code :
package com.leather.ville.service;
import java.util.LinkedList;
import java.util.List;
/**
* Created by Ankush on 18-10-2017.
*/
public class ArrayTest {
public static void main(String[] args) {
// Array Based
System.out.println(" Array Based Implementation");
int[] ar = new int[100000];
for (int i = 0; i < ar.length; i++) {
ar[i] = (int) (Math.random() * 100000);
}
long startTime = System.nanoTime();
getCurrentSize(ar);
System.out.println("(a)Length method time: " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
contains(ar,8128);
System.out.println("(b)Searching 8128, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
ar=remove(ar);
System.out.println("(c)Deleting last element, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
add(ar);
System.out.println(ar.length);
System.out.println("(d)Adding an element, time : " + (System.nanoTime() - startTime));
int count = 0;
startTime = System.nanoTime();
count = getFrequencyOf(ar, count);
System.out.println("(e)8128 frequency : " + count);
System.out.println("(f)Searching 8128, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
ar=newArrayOfLength200000(ar);
System.out.println("New Array 200000, time : "+(System.nanoTime() - startTime));
startTime = System.nanoTime();
getCurrentSize(ar);
System.out.println("(h)(a)Length method time: " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
contains(ar,8128);
System.out.println("(h)(b)Searching 8128, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
ar=remove(ar);
System.out.println("(h)(c)Deleting last element, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
add(ar);
System.out.println(ar.length);
System.out.println("(h)(d)Adding an element, time : " + (System.nanoTime() - startTime));
count = 0;
startTime = System.nanoTime();
count = getFrequencyOf(ar, count);
System.out.println("(h)(e)8128 frequency : " + count);
System.out.println("(h)(f)Searching 8128, time : " + (System.nanoTime() - startTime));
System.out.println("Linked List Based Implementation");
List<Integer> list=new LinkedList<>();
for (int i = 0; i < list.size(); i++) {
list.add((int)(Math.random() * 100000));
}
startTime = System.nanoTime();
int length=list.size();
System.out.println("(a)Length method time: " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
if(list.contains(8125)) {
boolean b=true;
}
System.out.println("(b)Searching 8128, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
for(Integer li:list){
if(li==8128){
list.remove(li);
}
}
System.out.println("(c)Deleting last element, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
list.add(8128);
System.out.println(ar.length);
System.out.println("(d)Adding an element, time : " + (System.nanoTime() - startTime));
count = 0;
startTime = System.nanoTime();
for(Integer li:list){
if(li==8128){
count++;
}
}
System.out.println("(e)8128 frequency : " + count);
System.out.println("(f)Searching 8128, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
for(int i=99999;i< list.size();i++){
list.add((int) (Math.random() * 100000));
}
System.out.println("New Array 200000, time : "+(System.nanoTime() - startTime));
startTime = System.nanoTime();
list.size();
System.out.println("(h)(a)Length method time: " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
list.contains(8128);
System.out.println("(h)(b)Searching 8128, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
for(Integer li:list){
if(li==8128){
list.remove(li);
}
}
System.out.println("(h)(c)Deleting last element, time : " + (System.nanoTime() - startTime));
startTime = System.nanoTime();
list.add(8128);
System.out.println(ar.length);
System.out.println("(h)(d)Adding an element, time : " + (System.nanoTime() - startTime));
count = 0;
startTime = System.nanoTime();
for(Integer li:list){
if(li==8128){
count++;
}
}
System.out.println("(h)(e)8128 frequency : " + count);
System.out.println("(h)(f)Searching 8128, time : " + (System.nanoTime() - startTime));
}
private static int[] newArrayOfLength200000(int[] ar) {
int[] newArray = new int[200000];
for(int i = 0; i < ar.length; i++) {
newArray[i] = ar[i];
}
for(int i=99999;i< newArray.length;i++){
newArray[i] = (int) (Math.random() * 100000);
}
return newArray;
}
private static void add(int[] ar) {
ar[99999] = 8128;
}
private static int[] remove(int[] ar) {
int[] temp=new int[ar.length];
for (int i = 0; i < ar.length - 1; i++) {
temp[i] = ar[i];
}
return temp;
}
private static int getFrequencyOf(int[] ar, int count) {
for (int i = 0; i < ar.length; i++) {
if (ar[i] == 8128) {
count++;
}
}
return count;
}
private static void contains(int[] ar, int value) {
for (int i = 0; i < ar.length; i++) {
if (ar[i] == value) {
break;
}
}
}
private static void getCurrentSize(int[] ar) {
int length = ar.length;
}
}
Output :
Array Based Implementation Linked List Based Implementation
(a)Length method time: 1307584 9793
(b)Searching 8128, time : 15467636 63420
(c)Deleting last element, time : 12836613 7885608
(d)Adding an element, time : 191194 124510
(e)8128 frequency : 1 1
(f)Searching 8128, time : 7270055 203319
New Array 200000, time : 24522329 29379
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.