EECS 2011辅导、Java语言讲解、Java程序调试、辅导data types

2019.01.27 - 首页 >> Java编程

EECS 2011: Assignment 1

January 9, 2019

6 % of the course grade

Due: Friday, January 25, 2019, 23:00 EST

Motivation

The purpose of this assignment is to practice using file input-output, abstract classes, and

interfaces through implementing a List data structure. In addition, the assignment will

allow you to improve your understanding of how primitive data types are stored in Java,

and what challenges might arise when storing and manipulating large collections of data.

Introduction

List1 is an ordered collection (also known as a sequence). The user of this interface has

precise control over where in the list each element is inserted (unlike when working with

a Set). The user can access elements by their integer index (position in the list), and

search for elements in the list. The List interface provides four methods for positional

(indexed) access to list elements, two methods to search for a specified object, and two

methods to [hopefully] efficiently insert and remove multiple elements at an arbitrary

point in the list.

While some of these operation execute in constant amount of time, the others may

execute in time proportional to the index value, depending on an implementation (the

LinkedList class, for example, is not very efficient when accessing elements in the

middle of the list).

Implementation

In this assignment, you will have to write a file-based implementation of the List

interface, for Number-s

only, where the items are stored in a file in the local file

system. The implementation should also extend an abstract FileContainer class

provided. After that, you will have to test the performance of several operations when

using your implementation.

Part 1

Implement the following public methods in your implementation of the List interface,

called FileList:

1. boolean add(E e)

2. void add(int index, E element)

3. void clear()

4. E remove(int index)

5. boolean remove(Object o)

6. String toString() (see Java API: AbstractCollection)

7. int size()

1 https://docs.oracle.com/javase/8/docs/api/java/util/List.html

2 https://docs.oracle.com/javase/8/docs/api/java/lang/Number.html

Two public constructors should exist in your implementation: one that takes no

parameters and creates a new file when the class is instantiated; and another that allows

you to specify a file name of a file you wish to use, possibly with the data created by an

application in the past (the file may also be empty, or may not exist):

public FileList(String fileName)

The class should use generics. The behaviour of the methods inf your implementation

should be equivalent to that of Java Standard Library’s classes (e.g., ArrayList; please

refer to the class API online). For the remaining methods of the interface, you may just

throw an exception (note, that you might have to implement certain methods anyways,

e.g., in order to execute the next part):

public type someUnneededMethod() {

throw new UnsupportedOperationException();

}

Of course, you are free to implement any private or protected methods and classes as you

see fit. However, you may not have any public methods other than the ones mentioned

(or the ones present in the interface or class’ superclass).

When the class is implemented, insert the following items into your list, using the first

add method from Part 1

1, 2, 3

and save the file that your application creates as a result under the name 123.list.

Reopening that file should allow one to have the list containing the same elements when

it is used in the future (possibly even by a different application). Repeat the process for

numbers

4, ?5.0, 6e0

and save the file as 456.list.

Part 2

Name your class ListTester. Use your list implementation and compare it to a Java

library List implementation ArrayList.

For numbers N = {10, 100, 1000, 10000, 100000, 1000000}

a) Starting with empty lists of Number-s, measure how long it takes to insert N integer

numbers (int, or Integer) with random values ranging from 0 to 10N into the lists,

when inserting them at the beginning, at the end, and into a random location of the list

(use indices to indicate where to do the insertion (e.g., list.add

(randomLocation, number)).

b) Starting with non-empty lists of N items (e.g., from part a), measure how long it takes

to remove N numbers from the lists when removing them from the beginning, from the

end, and from a random location of the list (use indices to indicate the location).

c) Starting with non-empty lists of N items (same as part b), measure how long it takes to

remove N random numbers (with values between 0 and 10N) from the two lists (note that

since the numbers are random, some values you wish to remove might not exist in the

list!).

At the end, produce the following table (the timing values below are just placeholders

and do not relate to any real measurements):

N = 10: ms to Ins. start, end, rnd; Rmv. start, end, rnd; Rmv. by value

ArrayList 12 345 678 12 345 678 123456

FileList 12 345 678 12 345 678 123456

N = 100: ms to Ins. start, end, rnd; Rmv. start, end, rnd; Rmv. by value

…

N = 1000: ms to Ins. start, end, rnd; Rmv. start, end, rnd; Rmv. by value

…

Make sure you reset the timer (or save the intermediate time before the next

measurement); i.e., make sure you measured time contains only the time to perform one

set of operations that was supposed to be timed.

In case the operations for larger N numbers take too long (e.g., more than 10–15 s) you

may reduce the number to a smaller one or eliminate it (so that you will have a range

from, say, 1 to 100,000 or even 10,000).

Save the result of your program execution in a file testrun.txt and submit it together

with your other files.

NOTES:

1. You may use any format for the file you use to store the data. Model implementation

used a RandomAccessFile3 class, but feel free to use any other that works best for

you. You can use any format for the data you write into your file. Keep in mind that the

items in a list may be of more than one type. The only items that your implementation

needs to handle are objects of Byte, Short, Integer, Long, Float, and Double;

feel free to ignore any other Number objects.

2. Do not use package-s in your project (put your classes in the default package).

Using packages will cost you a 10 % deduction from the assignment mark.

3. Some aspects of your code will be marked automatically (e.g., how it handles

boundary cases and error conditions), using a custom tester class. It is also imperative

you test your classes. If any of the java files that you submit do not compile, the whole

submission will be given a grade of zero, regardless of how trivial the compiler error is.

The code you submit should compile using

javac *.java

3 https://docs.oracle.com/javase/8/docs/api/java/io/RandomAccessFile.html

command in either Windows, Linux, or MacOS. It should also run using

java ListTester

4. Your code should include Javadoc comments. You can use the following list

implementation [4] for guidance.

5. Simpler implementation for a lower score:

- if your submission implements only methods 1, 3, 6, and 7, it is eligible for a maximum

score of 70/100. Part 2 of the assignment will change accordingly.

- if your submission can only handle an Integer type, it is eligible for a maximum of

50/100.

Submission

Submit your work using the submit command below; if using Eclipse, remember that

you first need to find your workspace directory, and your project directory. Name your

classes as specified. Using incorrect names will cost you a 20 % deduction from the

assignment mark.

submit 2011 a1 <list of your files>

You can check the usage examples by executing man submit.

Alternatively, you may use the web form at

https://webapp.eecs.yorku.ca/submit/index.php

You only need to submit 5 files; optionally, you may also submit a file readme.txt

containing comments for the marker. Do not compress your files into zip, etc.

Late penalty is 20 % per day. Submission 5 days or more after deadline will be given a

mark of zero (0). Contact the instructor well in advance if you cannot meet the deadline,

explaining your circumstances.

Academic Honesty

Academic honesty will be strictly enforced in this course. Specifically, direct

collaboration (e.g., sharing code or answers) is not permitted, and plagiarism detection

software will be employed. You are, however, allowed to discuss the questions, ideas, or

approaches you take. You might find the following article useful to have an idea what

kind of collaboration is appropriate: https://en.wikipedia.org/wiki/Clean_room_design

Cite all sources you use (online sources, books, etc.) in your code comments; using

textbook examples is allowed, but these must be cited as well.

E.g.,

1) /**

4 http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/00cd9dc3c2b5/src/share/classes/java/util/ArrayList.java

* Constructs an empty list with the specified initial capacity.

* @param initialCapacity the initial capacity of the list

* @exception IllegalArgumentException if the specified initial capacity

* is negative

* uses code from www.xxx.yyy.edu/123.html for file operations

2) //formula based on Jane Smart’s thesis, page XX, available at https://...

a = b + c;