EECS 2011辅导、Java语言讲解、Java程序调试、辅导data types
解析Haskell程序|辅导R语言程序
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
2
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.html2
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 3
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.html4
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
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.java5
* 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;