CMP 561 algorithm analysis

Ava’s software is contracted to enhance the CPU efficiency of a system which performs the following operations on several set of data records stored in files:

	Operation	Percentage of Use
	Search data records	30%
	Insert data records	35%
	Update data records	35%

Programs of the current system are written in Java, with 90% of them utilizing java.util.TreeMap.

Ava was told that the Red Black Tree provides the best CPU efficiency for such an application. Before making the final decision, she wishes to develop a testing program to verify such a theory.

You are tasked by Ava to:

(5%) Write a half-page summary to compare java.util.TreeMap and java.util.TreeSet.

(Copying words directly from resources will not give you credits.)

(15%) Develop a Java program to compare the CPU efficiency between util.TreeSet and java.util.TreeMap.

The key operations of this program are:

o Search by the User Name, using the following 5 user names

Amber, Yetta, Allen, Mercedes, Jeanette

o Insert all records from the file “finalUpdat.csv” file.

The time needed to read records into data structures has nothing to do with the requirements. The data file “finalData.csv” will be used to test the program.

Each line in “finalData.csv” and “finalUpdate.csv” contains 4 fields, separated by commas: § User Name

Email Address
Zone Code
PIN

For example,

Amber,elit.pretium.et@Maurisutquam.edu,78740,4600

Zia,dis.parturient@enim.co.uk,3792SZ,6746

Grading:

No more than 5%, if your program does not compile
No more than 8%, if your program compiles, but, produces an incorrect output

Reference:

https://www.java67.com/2012/08/difference-between-treemap-and-treeset-java.html
https://www.youtube.com/watch?v=rcDF8IqTnyI
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

java.util.TreeSet

java.util.TreeSet<E>

Type Parameters:

E - the type of elements maintained by this set

Data records stored in the java.util.TreeSet are sorted in natural order by the data values. No duplicated data records will be stored. The java.util.TreeSet data structure is also known as red-black binary tree which is a balanced binary tree. A red-black binary tree is a binary tree which satisfies the following:

Every node in the tree is red or black
The root is always black
If a node is red, its children must be black
Every path from the root to a leaf must contain the same number of black nodes

The red-black binary tree algorithm ensures that the binary tree is balanced.

java.util.TreeMap

java.util.TreeMap<K,V>

Type Parameters:

K - the type of keys maintained by this map

V - the type of mapped values

Data records stored in java.util.TreeMap are sorted according to the natural order of the key values. The java.util.TreeMap data structure does NOT eliminate duplicated records.

Example shows the use of java.util.TreeMap

{`
import java.util.*; public class UseTreeMap {
public static void main(String[] args) {
String []data = { "Hey", "How", "Hey", "Haha", "Hi", "Haha", "How" }; Map <String, Integer> tm = new TreeMap <String, Integer>();  for (String a : data) { Integer cnt = tm.get(a);
tm.put(a, (cnt == null) ? 1 : cnt + 1); 
}
System.out.println(tm.size() + " distinct words:");
System.out.println(tm);
} // main
} // UseTreeMap
`}

4 distinct words:

{`Haha=2, Hey=2, Hi=1, How=2`}

Data class and data file used in the next program example

Data class: OrderRec

Input file: orderinfo.txt

{`
Import java.util.*;
public class OrderRec implements java.io.Serializable { int ID;
String name; double amount;
public OrderRec() { ID = -999; name = null; amount = 0.0; }
public OrderRec(int i, String n, double a)
{ ID = i; name = n; amount = a; } public OrderRec(String s, String d) {
StringTokenizer st = new StringTokenizer(s, d);
ID = Integer.valueOf(st.nextToken(d)); name = st.nextToken(d);
amount = Double.valueOf(st.nextToken(d));
}
public int getID() { return ID; } public String getName() { return name; } public double getAmount() { return amount; } public void setID(int i) { ID = i; } public void setName(String n) { name = n; } public void setAmount(double a) { amount = a; }
public String toString() { return ID + "; " + name + "; " + amount; } } // OrderRec
`}

10198; Rainy Day Gear; 8976.0

10260; Fresh Air Fun; 1238.0

10334; Seaside Boats; 1156.0

10329; Bradley Boat Supply; 5674.0

10413; Reliable Hardware; 452.0

10180; Backyard Supplies; 7722.0

10247; Mountain Goods; 7456.0

10415; Spots Birdcage; 887.0

10125; Bird Outfitter; 3542.0

10121; Fresh Air Goods; 6785.0

10287; Outdoor Furnishings; 6852.0

Use java.util.TreeMap to sort records: UseTreeMap2

Output

{`
import java.util.*; import java.io.*;
public class UseTreeMap2 
{
public static void main(String []args) {
 TreeMap <Integer, OrderRec> orders = 
 new TreeMap <Integer, OrderRec>(); 
BufferedReader infile;
String line;
OrderRec temp=null;
try
{
infile = new BufferedReader(new FileReader("orderinfo.txt")); while ((line = infile.readLine()) != null)
{
temp = new OrderRec(line, ";");
orders.put(new Integer(temp.getID()), temp);
}
infile.close();
} catch (IOException x) { System.err.println(x); System.exit(1); } Infile.close();
Collection c = orders.values();
Iterator ir = c.iterator(); while (ir.hasNext())
System.out.println(ir.next());
} // main
} // UseTreeMap2
`}