CSCI-1200 Data Structures Spring 2019
homework | assignment | database – 这是一个关于database的题目, 主要考察了关于database的内容,是一个比较经典的题目, 涵盖了database等程序代做方面, 这是值得参考的assignment代写的题目
homework 9 IMDB Search
The Internet Movie database (IMDB) keeps track of data related to films. We have processed some of the data fromhttps://www.imdb.com/interfaces/since the full dataset has some interesting problems and is far too large for us to work with.
Your program will take input fromstd::cinwhich constitutes a list of commands. Some of these commands will describe how your hash table for the assignment will work, and other commands will request output to std::cout.
The goal is to write our own simple search engine for movie data. In a search, we may have exact information, or we may only have partial information (more on this later). In order to make our search time-efficient we will use extra memory in our hash table to store more keys.
Movie Data
When your program receives themoviescommand, it will be given a filename to read from. Each entry in the file will look like:
Title Year of Release Runtime in Minutes GenreCount GenreList ActorCount ActorList RoleCount RoleList
There will be no spaces in any of the data, for example instead of John Wayne we would have JohnWayne. None of the fields will be blank, andGenreCount,ActorCount,RoleCountwill all be1. GenreListwill haveGenreCount entries, ActorListwill have ActorCountentries, andRoleList will haveRoleCount entries. Refer to the sample for more concrete examples.
One strange thing about the data is that instead of the actors having names, they all have strings starting with n which we will refer to asnconsts. This is because there might be two actors with the same name, so we instead use a unique identifier. However, there is another commandactorswhich also gives a filename. The structure of the actors file is much simpler with each line consisting of:
nconst ActorName
The third major operation isquery. After the wordqueryyour program can expect input that looks like an entry from the movie file. However, it is also possible to have unknown values. If the title, runtime, or year are ? it means that they are a wildcard and will match any movie. If the GenreCount, ActorCount or RoleCount are 0, it means they are a wildcard and will match any movie. When your program receives a query, it should search the hash table (more on that in a moment) and return all results that match. In order for two GenreLists, ActorLists, or RoleLists to match, they must have the same number of values, every value must match, and the values must be in the same order.
Choice of Hash Function and Table Implementation
The choice of the hash function is up to you. A good hash function should be fast, O(1) computation, and provide a random, uniform distribution of keys throughout the table. You may use one of the hash functions mentioned in lecture, one found on the internet, or one of your own devising. If you choose to download a hash function from the internet, you must provide the URL in your README and include the source code with your submission. If the downloaded file requires a copyright notice, you MUST include that notice. Be
sure to observe any copyright restrictions on the use of the code. In your README file, describe your hash function and table implementation.
One of your challenges will be figuring out how to hash movie data – each entry in your hash table will have a value that is either movie data or a pointer to movie data. Keep in mind data is a plural, so this may refer to more than one movie. We will not be picky about which approach you take for the value, but pointers will be much more memory efficient since you will replicate a lot of data and may be required for larger test cases. The key in your hash table should be a unique identifier of the movie data. Where this gets interesting is that in addition to hashing the movie object, you will need to hash every partial version of a movie object. Recall from the description above of thequerycommand that you may be given only some information with others left as unknowns. It would be very slow to check every single movie object, so instead you will need to store these partial hashes as keys with the full movie data as values.
For example, the second query intop250exampleinput.txtlooks for any movie from 1994, so all movies in the dataset that have a year of 1994 should be values associated with the hash of the partial movie data where everything is empty except the year, which is set to 1994. Representing partial queries and figuring out how to generate all of them is another challenge in this assignment. Partial queries may return several results, your hash table implementation should enable efficient retreival of the multiple movies that match the querys criteria. Hint: There should be around 64 partial queries you can make per movie.
To store the hashes and the associated movies in the hash table, once the table index of the query key has been found, you may use any of the data structures that we have covered so far in class. To handle collisions, use one of the open addressing methods described in lecture (linear probing, quadratic probing, or secondary hashing). Linear probing is the simplest of these three methods. You may not usestd::hash, std::unorderedmap,std::unorderedset,std::mapor similar STL functions/containers.Exception: You can use a map to store actor data, but not movie data.
When implementing the hash table, set the initial size of the table. As you enter data in the table, calculate the occupancy ratio:
occupancy=
number of unique key entries
table size
When theoccupancy>than some fixed level, double the size of the table and rehash the data. Describe your re-sizing method in the hash table section of the README file.
Input/Output & Basic Functionality
The program should read a series of commands from std::cin (STDIN) and write responses to std::cout (STDOUT). Sample input and output files have been provided. You can redirect the input and output to your program using the instructions in the sectionRedirecting Input & Output found athttp: //www.cs.rpi.edu/academics/courses/spring19/csci1200/other_information.php
Your program should accept the following commands:
- movies filename- Read movie data fromfilename.
- actors filename- Read actor data fromfilename.
- tablesize N- this is an optional command. Nis an integer. It is the initial hash table size. If it does not appear in the command file, the initial table size should be set to 100.
- occupancy f- this is an optional command.fis a float. When the occupancy goes above this level, the table should be resized. If it does not appear in the command file, the initial level should be set to 0.5.
- query querydata- Search the movie data for any matches toquerydata.
2
- quit- Exit the program. You may assume that iftablesizeoroccupancyappear, they will appear beforemovies. You can also assume thatmoviesandactorswill appear before anyquerycommands.
For output to queries, if matches are found, the program will print the number of matches and the corresponding movie data. Otherwise, the program will print No results for query. Since the ordering will depend on your hash function, you are not required to print the results of a query in any particular order. One subtle detail is that when outputting movie data you should use the actual names of actors instead of their nconsts.
You are not explicitly required to create any new classes when completing this assignment, but please do so as it will improve your program design. We expect you to useconstand pass by reference/alias as appropriate throughout your assignment.
Submission
Use good coding style and detailed comments when you design and implement your program. Please use the provided templateREADME.txtfile for any notes you want the grader to read, including work for extra credit. You must do this assignment on your own, as described in the Collaboration Policy & Academic Integrity. If you did discuss the problem or error messages, etc. with anyone, please list their names in your README.txtfile.