| Assigned | Wednesday, Sep 5, 2007 |
| Due | 11:59pm, Friday Sep 21, 2007 |
| Updates |
The Java Collections Framework was introduced in the Java 2 platform. The framework's major objective was to provide an architecture for the representation and manipulation of collections. A collection is an object that represents a group of heterogeneous objects. In Java 5, generics were introduced such that a collection could represent a group of homogeneous objects. One of the advantages to using the collections framework is that it implements many powerful data structures and the algorithms for sorting and searching them so that you don't have to implement them yourself. Because these high-performance implementations share a common interface, you can switch between implementations simply by changing the type of your collection.
Before you begin, you should read and understand the Sun's tutorials on the Collection classes and on Generics.
Your program will test each of the forementioned classes for four different operations - adding a given number of elements to the collection, iterating thru these elements, finding a given element in the collection and removing the given element. If the collection is a list, it will also test the speed at which the elements may be randomly accessed. Because we are assuming that this is your first Java project we will be giving you a Timer thread that will calculate the number of microseconds for a given operation. In your program, you must create a static array of objects of type Integer and of size 1000 that is accessible to your all the methods within the benchmark. The array will contain random integer values between the 0 and 999. The name of this array is found in the benchmark code. One of the elements in the array must be the Integer o that serves as a parameter for the findElement and the removeElement.
The code for the benchmark follows:
public static void benchmark(Collection c) {
System.out.printf("%-50s",c.getClass().getName());
Timer clock = new Timer();
clock.start();
clock.begin();
addElements(c);
clock.end();
//add
System.out.printf("%15d ns",
clock.getElapsedTime());
clock.reset();
clock.begin();
iterateOverElements(c);
clock.end();
//iter
System.out.printf("%15d ns",
clock.getElapsedTime());
clock.reset();
clock.begin();
findElement(c, o);
clock.end();
//find
System.out.printf("%15d ns",
clock.getElapsedTime());
//random
if (c instanceof List) {
List l = (List)c;
clock.reset();
clock.begin();
randomAccess(l);
clock.end();
System.out.printf("%15d ns",
clock.getElapsedTime());
}
else
System.out.printf("%15d ns", 0);
//remove
clock.reset();
clock.begin();
removeElement(c, o);
clock.end();
System.out.printf("%15d ns\n",
clock.getElapsedTime());
}
We will also be providing you with the code for the three of the static methods used above:
public static void addElements(Collection c) {
for (int i = 0; i < NUM_ITEMS; i++) {
c.add(objects[i]);
}
}
public static void iterateOverElements(Collection c) {
for (int i = 0; i < NUM_ITEMS; i++) {
Iterator iter = c.iterator();
while (iter.hasNext()) {
Object o = iter.next();
}
}
}
public static void randomAccess(List c) {
for (int i = 0; i < NUM_ITEMS; i++) {
Object o = c.get(random());
}
}
You are expected to write the random, removeElement, and findElement methods. You should use the static random method in the java.lang.Math class to implement this method. The random method in the randomAccess method should return a random integer between 0 and 999. The benchmark method currently does not incorporate any generic programming.
Dr. Rheingans' public directory for this project is
CLASS NAME ADD ITERATE FIND RANDOM REMOVE java.util.ArrayList 443911 ns 39319522 ns 178515 ns 1381460 ns 128508 ns java.util.Collections$SynchronizedRandomAccessList 1413029 ns 35398633 ns 546718 ns 537778 ns 70121 ns java.util.LinkedList 1008788 ns 28832994 ns 101410 ns 3488432 ns 72076 ns java.util.Collections$SynchronizedList 2026794 ns 29971687 ns 55594 ns 2248331 ns 50565 ns java.util.TreeSet 5107353 ns 36716957 ns 37155 ns 0 ns 41067 ns java.util.Collections$SynchronizedSet 5661893 ns 34539306 ns 13689 ns 0 ns 14248 ns java.util.HashSet 2049981 ns 38050087 ns 27377 ns 0 ns 32685 ns java.util.Collections$SynchronizedSet 2936966 ns 35672690 ns 10895 ns 0 ns 18717 ns java.util.Vector 997613 ns 49625861 ns 77663 ns 310375 ns 127391 ns
Be sure that the p1-output.txt file is in plain text format.
Submit the files using the procedure below.
Submission Tools
There are a number of tools available to you to check on your submittal. It is
your responsibility to ensure that the submittal is correct and will result in
a successful compilation of your project. Do not wait till the last minute to
submit your files. Give yourself enough time to check that your submittal is
correct.
If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/. The class name is cs341 and the project name is Proj1. One of the tools provided by the submit program is submitls. It lists the names of the files you have submitted.
Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory /afs/umbc.edu/users/r/h/rheingan/pub/341/ and are named submitmake and submitrun. You can use these programs to compile and run your submitted projects.
The syntax is similar to that for submit:
submitmake <class> <project>
Example: submitmake cs341 Proj1 <parameter list>
Project grading is described in the
Project
Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for this
course.
Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.