HashMaps and BigO
Hacks
- Analyze the Big O complexity on Sorts.
- Establish analytics including:time to sort, number of comparisons and number of swaps.
- Average the results for each each Sort, run each at least 12 times and 5000 elements.
- You should throw out High and Low when doing analysis.
- Make your final/judgement on best sort: Number of Comparisons, Number of Swaps, Big O complexity, and Total Time.
- Build your own Hashmap. Make a HashMap to correspond to a Data Structure using a Collection.
- Be sure to have 5000 records
- Perform analysis on Binary Search vs HashMap Lookup, try using random to search and find 100 keys in 5000 records. Perform 12 times and throw out high and low.
- Extra, Practical learning
- Performing Iteration, Delete, and Add operations are another way to analyze Collection vs HashMap data structure.
- A HashMap and a Collection can be used in a Class, POJO and API.
- Make a Diagram on the Pros and Cons of Collection vs HashMap
import java.util.Random;
/**
* BigOSorting.java
*
* Description
*
* @author Natalie Beckwith
* @version 1
*/
/**
* Main class for BigOSorting.java
*
*/
public class BigOSorting
{
private static int[] arrayExample = new int[5000];
final private static int NUM_ARRAY = arrayExample.length;
/**
* getArray
*
* @param array
* @return
*/
public int[] getArray(int[] array)
{
// creates 5000 elements
Random random = new Random();
// for every element in the array
for (int i = 0; i < array.length; i++)
{
// randomly assigns an int to the current element
array[i] = random.nextInt(0, 5000);
}
return array;
}
/**
* bubble from geeksforgeeks
*
* @param arr
* @param n
* @return
*/
public void bubble(int arr[], int n)
{
for (int current = 0; current < n - 1; current++)
for (int previous = 0; previous < n - current - 1; previous++)
if (arr[previous] > arr[previous + 1])
{
// swap arr[j+1] and arr[j]
int temp = arr[previous];
arr[previous] = arr[previous + 1];
arr[previous + 1] = temp;
}
}
/**
* swap elements from geeksforgeeks
*
* @param num1
* @param num2
*/
public static void swap(int num1, int num2)
{
int temp = num1;
num1 = num2;
num2 = temp;
}
/**
* merge from geeksforgeeks
*
* @param arr
* @param l
* @param m
* @param r
*/
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/* Copy data to temp arrays */
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = l + (r - l) / 2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
/**
* selection from geeksforgeeks
*
* @param arr
*/
void selection(int arr[])
{
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n - 1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
/**
* insertion from geeksforgeeks
*
* @param arr
*/
void insertion(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
/**
* printArray
*
* @param arr
*/
static void printArray(int arr[])
{
for (int i = 0; i < arr.length; i++)
{
System.out.printf("%d ", arr[i]);
}
System.out.printf("\n\n");
}
/**
* main
*
* @param args
*/
public static void main(String[] args)
{
BigOSorting bigOSorting = new BigOSorting();
arrayExample = bigOSorting.getArray(arrayExample);
int[] binarySorted = arrayExample;
int[] mergeSorted = arrayExample;
int[] selectionSorted = arrayExample;
int[] insertionSorted = arrayExample;
System.out.printf("NUM:\t\tBUBBLE:\t\tMERGE:\t\tSELECTION:\tINSERT:\n");
System.out.printf("----\t\t----------\t--------\t----------\t-------\n");
double averageB = 0.0;
double averageM = 0.0;
double averageS = 0.0;
double averageI = 0.0;
int numIterations = 12;
for(int i = 0; i < numIterations; i++)
{
// times binary
long binaryStartTime = System.nanoTime();
bigOSorting.bubble(binarySorted, NUM_ARRAY);
long binaryEndTime = System.nanoTime();
long binaryDuration = (binaryEndTime - binaryStartTime);
// times merge
long mergeStartTime = System.nanoTime();
bigOSorting.merge(mergeSorted, 0, (NUM_ARRAY / 2) - 1, NUM_ARRAY);
long mergeEndTime = System.nanoTime();
long mergeDuration = (mergeEndTime - mergeStartTime);
long selectionStartTime = System.nanoTime();
bigOSorting.selection(selectionSorted);
long selectionEndTime = System.nanoTime();
long selectionDuration = (selectionEndTime - selectionStartTime);
long insertStartTime = System.nanoTime();
bigOSorting.insertion(insertionSorted);
long insertEndTime = System.nanoTime();
long insertDuration = (insertEndTime - insertStartTime);
// print
System.out.printf("%d \t\t%dns \t%dns \t%dns \t%dns\n",
i, binaryDuration, mergeDuration, selectionDuration, insertDuration);
averageB += binaryDuration;
averageM += mergeDuration;
averageS += selectionDuration;
averageI += insertDuration;
}
averageB /= numIterations;
averageM /= numIterations;
averageS /= numIterations;
averageI /= numIterations;
System.out.printf("\nAVERAGE TIMES:"
+ "\t\n---------------------------------------------------------------------------\n");
System.out.printf("\t\t%.2fns\t%.2fns\t%.2fns\t%.2fns\t\n", averageB, averageM, averageS, averageI);
//printArray(binarySorted);
//printArray(mergeSorted);
//printArray(selectionSorted);
}
}
BigOSorting.main(null);
/**
* test.java
*
* Description
*
* @author Natalie Beckwith
* @version 1
*/
import java.util.HashMap;
import java.util.Random;
import java.lang.Integer;
import java.util.Scanner;
public class HashMapPactice
{
public static void main(String[] args)
{
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
int[] arrayExample = new int[5000];
final int NUM_ARRAY = arrayExample.length;
// creates 5000 elements
Random random = new Random();
// for every element in the array
for (int i = 0; i < NUM_ARRAY; i++)
{
// randomly assigns an int to the current element
arrayExample[i] = random.nextInt(0, 5000);
}
System.out.printf("LookUp\t\tBinarySearch\n");
System.out.println("------------------------------------");
double total_lut = 0;
double total_bst = 0;
// get num to search for from scanner
Scanner sc = new Scanner(System.in);
System.out.println("Search a number: ");
Integer num = sc.nextInt();
for (int i = 0; i < 12; i++)
{
// check look up time for hash map
String str = "Time: ";
long lut = (lookUp(hashMap, num));
total_lut += lut;
str += (lut + "ns\t");
// copy array, check binary search time
int[] arrCopy = new int[NUM_ARRAY];
System.arraycopy(arrayExample, 0, arrCopy, 0, NUM_ARRAY);
long bst = (binarySearchTime(arrCopy, num));
total_bst += bst;
str += (bst + "ns\t");
System.out.println(str);
}
System.out.println("-----------------------------------");
System.out.println("Average time:\n" + (total_lut / 12) + "ns\t" + (total_bst / 12) + "ns");
}
/**
* lookUp
*
* @param map
* @param value
* @return
*/
public static long lookUp(HashMap<Integer, Integer> map, Integer value)
{
long start = System.nanoTime();
map.containsKey(value);
long end = System.nanoTime();
return (end - start);
}
/**
* binarySearchTime
*
* @param arr
* @param value
* @return
*/
public static long binarySearchTime(int[] arr, Integer value)
{
long start = System.nanoTime();
// binary search
int low = 0;
int high = arr.length - 1;
int mid = (low + high) / 2;
while (low <= high)
{
if (arr[mid] < value)
{
low = mid + 1;
}
else
if (arr[mid] == value)
{
break;
}
else
{
high = mid - 1;
}
mid = (low + high) / 2;
}
long end = System.nanoTime();
return (end - start);
}
}
HashMapPactice.main(null);