Java程序辅导

CSc 460 — Database Design
Fall 2016 (McCann)
http://www.cs.arizona.edu/classes/cs460/fall16
Program #1: Exponential Searching a Binary File
Due Dates:
Part 1: September 1 st, 2016, at the beginning of class
Part 2: September 8 th, 2016, at the beginning of class
Overview: Your second programming assignment will ask you to create an index on a binary file. I could
just give you the binary file, or merge the two assignments, but creating the binary file from a real-world text
file makes for a nice “shake off the rust” assignment, plus it provides a gentle (?) introduction to binary file
processing for those of you who have yet to experience it.
A binary file is not mysterious; it’s just a file that contains information in the same format in which the
information is held in memory. (In a text file, all information is stored as ASCII or UNICODE characters.)
Consequently, binary files are generally faster and easier for a program to read and write than are text files.
As long as the file is well-structured, doesn’t need to be read by people, or ported to a different type of system,
binary files are often the best way to store program information.
Our data comes from the “USDA National Nutrient Database for Standard Reference, Release 28 (2015),” a
text file containing a collection of 8,790 food items and their content.1 Each line has 53 pieces of information
about a food item, including its name, vitamins, minerals, etc. In DBMS Land, these pieces are often called
fields, and each line’s worth of fields is a record. Converting the content of such a file into binary format
requires some effort in Java, because Java wasn’t originally designed for this type of task. (By comparison,
“systems” languages like C can interact more directly with the operating system to provide more convenient
file I/O.) On the class web page you’ll find a sample Java binary file I/O program, which should help get you
started. Details about the data file can be found in the Data section, below.
Assignment: This assignment is in two parts:
Part 1 : Write a complete, well-documented Java 1.8 program named Prog1p1.java that accepts the name
of the input text file on the command line and creates a binary file version of the text file (with the same
name but an extension of bin; that is, if the input file name is ABBREV.txt, the binary file’s name will be
ABBREV.bin) consisting of just the first 10 fields of each food item record, and with records stored in ascending
order by the fourth field of each record (the “Energ Kcal” field, a.k.a. the food item’s number of calories).
Each field’s type is to be int, double, or a string of 8-bit ASCII characters, as defined by Table 16 of the
sr28 doc.pdf file (see pages 39 and 40). If you follow that table, each record of your binary file should require
131 bytes of storage. (This uniformity is another advantage of binary file storage.)
Be aware that this part is due a week before the next part; see the due dates at the top of this document. The
reason? We don’t want you to wait two weeks minus one day to get started.
Part 2 : Write a second complete, well-documented Java 1.8 program named Prog1p2.java that does both of
the following, in this order:
1. Reads and prints to the screen the content of the first five records of data and the last five records of
data in the binary file, and the total number of records in the binary file. (Write the program to accept
the complete pathname of the binary file from the command line.)
2. Using one or more “Energ Kcal” values given by the user in response to a prompt from your program,
locates within the binary file (using exponential binary search, described below), reads from the binary
file, and displays to the screen the content of all fields of the records matching that value, or the message
“No matching records.” otherwise.
1
p(Being optioned as a major Hollywood summer romcom) = 0.
Data: The complete lectura pathname of our sample data file is /home/cs460/fall16/ABBREV.txt. Your
program (when running on lectura or a lab machine) can read the file directly from that directory; just give
your program the complete path name of the file. There’s no reason to waste disk space by making another
copy of the file in your account.
The fields are caret(‘^’)-separated. Text fields include tildes (‘~’) to mark the start and end of the text. For
example, here are the first 10 fields of the first record of ABBREV.txt:
~01001~^~BUTTER,WITH SALT~^15.87^717^0.85^81.11^2.11^0.06^0.0^0.06^
The field descriptions for ABBREV.txt can be found in the file /home/cs460/fall16/sr28 doc.pdf, on pages
38-41. Those descriptions should be a big help in the selection of meaningful variable names.
Please keep in mind that we have not combed through the data to see that it is all formatted perfectly. This is
completely intentional, not (just!) because we are lazy. Corrupt data is a huge problem in data management,
and we hope that this file is no exception. We want you to think about how to deal with malformed data, and
ask questions, as needed, about how to handle it.
Output: The basic output expectations are given in the Assignment section, above. Additional details are
up to the TA(s).
Hand In: You are required to submit your completed program file(s), and your ABBREV.bin binary file, using
the turnin facility on lectura. The submission folder is cs460p1. Instructions are available from the document
of submission instructions linked to the class web page. In particular, because we will be grading your program
on lectura, it needs to run on lectura. Thus, be sure to test it on lectura. Name your main program source files
Prog1p1.java and Prog1p2.java, as indicated earlier, so that we don’t have to guess which files to compile,
but feel free to split up your code over additional files if doing so is appropriate to achieve acceptable code
modularity. Submit all files as-is, without packaging them into .zip, .jar, .tar, etc., files.
Want to Learn More?
• https://www.ars.usda.gov/Services/docs.htm?docid=25700 — This is the United States Depart-
ment of Agriculture’s (USDA’s) page with links to the available forms of the Standard Reference data.
We’re using the “Abbreviated” version.
Other Requirements and Hints:
• Don’t “hard–code” values in your program if you can avoid it. For example, don’t assume a certain
number of records in the input file or the binary file. Your program should automatically adapt to simple
changes, such as more or fewer lines in a file or changes to the file names or locations. For example, we
may test your program with a file of just a few records, or even no records. We expect that your program
will handle such situations gracefully.
• Once in a while, a student will think that “create a binary file” means “convert all the data into the
characters ‘0’ and ‘1’.” The binary I/O functions in Java will read/write the data in binary format
automatically. See the BinaryIO.java sample program to learn how to create and access binary files.
• Wondering how to efficiently get the last five records from a binary file? seek() the Java API and ye
shall find!
• Comment your code according to the style guidelines as you write the code (not an hour before class!). The
requirements and some examples are available from: http://www.cs.arizona.edu/~mccann/style.html
• You can make debugging easier by using only a few lines of data from the data file for your initial testing.
Try running your code on the complete file only when you can process that reduced data file.
• Finally: Start early! File processing can be tricky.
2
Exponential Binary Search
Exponential Binary Search is an extension of normal binary search originally intended for searching unbounded
data, but it works for bounded data, too, such as might be stored in a binary file. The algorithm has two
stages:
Stage 1 : For i = 0, 1, . . ., probe at index 2(2i − 1) until the index is invalid or an element ≥ the
desired target is found. (If the probed element equals the target, the search is complete.)
Stage 2 : Perform binary search on the range of indices from 2(2i−1 − 1) + 1 to min(2(2i − 1) −
1, largest index), inclusive.
To better understand how this works, sketch an array of 16 integers on a piece of paper, and imagine that
you’re searching for an item toward the far end of the array.
The algorithm can be extended to have as many repetitions of Stage 1 as desired to further narrow the range
that Stage 2 needs to search. For our purposes, this basic version is adequate.
Reference: Bentley and Yao, “An Almost Optimal Algorithm for Unbounded Searching,” Information Pro-
cessing Letters 5(3), 1976, pp. 82-87.
3