辅导案例-FIT1008
FIT1008 Introduction to Computer Science (FIT2085: for Engineers) Interview Prac 3 - Weeks 11 and 12 Semester 2, 2019 Learning objectives of this practical session To be able to implement and use hash tables in Python. Important requirements For this prac, you are required to: • Create a new file/module for each task named task[num].py (that is, task1.py, task2.py, and so on). • Provide documentation for each basic piece of functionality in your code (see below) • The documentation needs to include (in the docstring): – pre and post conditions – Big O best and worst time complexity – information on any parameters used • Provide testing for those functions/methods explicitly specified in the questions. The testing needs to include: – a function to test it – a comment indicating the purpose of each test – at least two test cases per test function. These cases need to show that your functions/methods can handle both valid and invalid inputs. – assertions for testing the cases, rather than just printing out messages Your tests should be added to the corresponding test_task[num].py file provided • VERY IMPORTANT: As before the code cannot use any of the Python functionality that would make the job trivial (like dictionaries), but this time your are allowed to use any Python list or string functionality you want. Supporting Files To get you started, you will find some supporting files on Moodle under Week 11: • HashTable.py, Freq.py: Skeleton files for the HashTable and Freq classes, which you may use as starting points. • test_prac3.py, test_task[num].py, test_common.py: Testing harnesses for each of the tasks. • Additional text files for testing your dictionaries (and used by the testing harness). Your code will be tested with an extended version of this harness, so make sure your code can run inside the harness. To make the testing work, we have made assumptions about the naming of instance variables, so please follow the naming used in the skeletons. Your modules should guard any computa- tion/printing/etc. for the tasks with if __name__ == ’__main__’:, so they can be safely imported by the testing harness. The harness you have been provided is not exhaustive, so don’t rely on it to ensure correctness! Remember to add your own tests, as well. Important: Checkpoint for Week 11 To reach the check point you must complete Tasks 1, 2 and 3 by the end of your lab in Week 11, and submit all files corresponding to these tasks before leaving the lab. Remember: reaching the checkpoint is a hurdle. Task 1 6 marks Define a class HashTable that implements a hash table (accepting only strings as keys), using Linear Probing to resolve collisions. As in Prac 2, you should use a Python list to represent the underlying array. Include implementations for the following methods: • __init__(self, table_capacity, hash_base): Creates a new hash table, with initial table ca- pacity table_capacity, and with using base hash_base for the hash function (see hash below). If table_capacity or hash_base are not specified, the hash table should use appropriate default values. • getitem (self, key): Returns the value corresponding to key in the hash table. Raises a KeyError if key does not exist in the hash table. Remember that this can be called from Python code as table[key] • setitem (self, key, value): Sets the value corresponding to key in the hash table to be value. If the hash table is full and the key does not exist in the table yet, it first calls the rehash method (see below) and then reinserts the key and value. Called from Python as table[key] = value • contains (self, key): Returns True if key is in the table and False otherwise. • hash(self, key): Calculates the hash value for the given key, using the uniform hash function specified in lecture 27 (page 35) with the base hash_base given on table creation. • rehash(self): It first creates a new array using as size the smallest prime number in the Primes list below that is larger than twice the current size. It then updates the size of the hash table and reinserts all key-value pairs in the old array into the new array using the new size. Raises a ValueError if there is no such prime in the list. For now, this method is only called when the table is full and we want to insert an element. Primes = [ 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30313, 36353, 43627, 52361, 62851, 75521, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369] The file test_task1.py defines tests for some of the HashTable methods. But be warned: these tests are not comprehensive, and it is in your interest to think about what kinds of inputs we have not covered. Important: you must add your own tests for the __setitem__ and rehash methods. Task 2 5 marks • Write a function load_dictionary(hash_table, filename, time_limit) that reads a file filename containing one word per line, and adds each word to hash_table with integer 1 as the associated data. time_limit is an optional argument – if it is specified and loading the dictionary takes more than time_limit seconds, the function should immediately raise an exception. Important: you must add your own tests for the load_dictionary method, using one or more very small dictionary files to do so. • Write a function load_dictionary_time(hash_base, table_size, filename, max_time) that creates a new hash table with base hash_base and table_size, and returns the tuple (words,time), where words is the number of (distinct) words added to the table, and time is the time taken (in seconds) for load_dictionary to complete if less or equal than max_time, and None otherwise. • Download from Moodle the dictionary files english small.txt, english large.txt and french.txt. Write a Python function table_load_dictionary_time(max_time) that does the following: for each of these dictionaries and each combination of the values specified in the table below for TABLESIZE and b in the universal hash function, uses load_dictionary_time to time how long it takes for load_dictionary to run and prints a line to file output task2.csv containing the name of the dic- tionary, the TABLESIZE and b used, the number of words added to the hash table, and either the time taken to run load_dictionary for that combination, or TIMEOUT if the time exceeded max_time. b TABLESIZE 1 250727 27183 402221 250726 1000081 Note that the above table gives a total of 3*3=9 combinations per dictionary file. Nested for loops would be a good way to implement these combinations, and you are allowed to use ”in” for this. • Execute table_load_dictionary_time(max_time) for max_time = 120 (i.e., 2 minutes) and use the information in the newly created file output task2.csv to graph the time taken for each file combination (i.e., a graph where the x axis has the 9 combinations, the y has the time, and each combination shows 3 columns, one per file – an example is given at the end of the prac sheet), using the same methodology as you used in the code review prac of week 5 (giving TIMEOUT the value max_time+10). Create also an explanation task2.pdf file that contains this graph together with a short analysis regarding what values work best and which work poorly, and an explanation of why these might be the case. IMPORTANT: The dictionary files use the utf-8 encoding. Depending on your system configura- tion, you may need specify this when you open the file (e.g. open(a_file, ’r’, encoding=’utf-8’)). Note: If you are playing around with no time out, you can use Ctrl+c to stop execution of your program if some combination of values takes too long. Task 3 4 marks When discussing open addressing, we introduced two concepts: that of collision, which occurs when we attempt to insert a key, but the location for that key is already occupied by a different key); and that of probe chain, which is the sequence of positions we inspect before finding an empty space. Consider inserting keys s1, s2 and s3 into an empty table with linear probing, assuming all three hash to location 10. When we insert s1, location 10 is empty, so there is no conflict. If we then insert s2, location 10 is full, but 11 is empty. This is a conflict, with probe chain length 1. When we insert s3, 10 and 11 are full, but 12 is free. This is one conflict, with probe chain length 2. • Extend your HashTable class with a method statistics(self), which returns a tuple (collision count, probe total, probe max, rehash count), consisting of: (a) the total number of collisions, (b) the total length of the probe chains, (c) the length of the longest probe chain, and (d) the number of times rehash has been called. Important: you must add your own tests for your statistics method. • Write a function load_dictionary_statistics(hash_base, table_size, filename, max_time) which does the same as load_dictionary_time (from Task 2), but returns the following tuple: (words, time, collision_count, probe_total, probe_max, rehash_count), where the tuple elements represent the same information described above. • Using the function above, write a function table_load_dictionary_statistics(max_time) that is similar to that in Task 2, but also prints the four counters above in the output task3.csv file. • Execute table_load_dictionary_statistics(120) and create an explanation task3.pdf file that contains the associated graph and a comment regarding the relationship between these counters and the runtime, and regarding the length of the longest probe chain and the promise of O(1) time complexity. Explain why rehash_count is 0 in all runs (it should be!) Again, remember to include your csv and pdf files in your submission. Hint: To avoid duplicating this code later in the prac, you may wish to pass the HashTable class as an optional argument to load_dictionary_statistics. CHECKPOINT (You should reach this point during week 11) Task 4 3 marks Modify your hash table from the previous task to use Quadratic Probing to resolve collisions. Repeat the analysis from Task 3 on your Quadratic Probing hash table, and add to your explanation task4.pdf file the graph associated with the table in output task4.csv together with a comparison of the running time and reported statistics against those found when using Linear Probing. Hint: If you followed the previous hint, you should not need to modify load_dictionary_statistics. Task 5 4 marks Implement a hash table that uses Separate Chaining to resolve collisions, where the linked data structure used is a Binary Search Tree (we will see this data type in Week 11, and you will be provided with an implementation of the Binary Search Tree, so do not worry about this just yet). Note that the content of the array cells should initially be None. Whenever you need to add a (key,data) pair in that cell, you should create an empty binary search tree (say my_tree = BinarySearchTree()), then insert the (key,data) into my_tree, and then put my_tree in the cell. Once this is done, compare again the runtime and value of the counters obtained in explanation task5.pdf for Separate Chaining against those obtained for Quadratic and for Linear Probing. Background In most large collections of written language, the frequency of a given word in that collection is inversely proportional to its rank in the words. That is to say: the second most common word appears about half as often as the most common word, the third most common word appears about a third as often as the most common word and so on1. If we count the number of occurrences of each word in such a collection, we can use just the number of occurrences to determine the approximate rank of each word. Taking the number of occurrences of the most common word to be max and the relationship described earlier, we can give a rarity score to each word: • Any word that appears at least max/100 times is considered to be common (score 0). • Any word that appears less than max/1000 times is considered to be rare (score 2). • Any word in between (less than max/100 and greater or equal to max/1000) is considered to be uncommon (score 1). • Any word which has never been observed is a misspelling (score 3). In the following we will use a hash table to facilitate a frequency analysis on a given text file. Task 6 4 marks Create a new class Freq that uses the Linear Probing hash table to perform a frequency analysis of a set of files as follows. First, add to this class the method add_file(self,filename), which reads each word from the file into the hash table, in such a way that the data associated to the word is its “occurrence count”, i.e., the number of times the word has been “added” to the hash table (which is the same as the number of times it has already appeared in the file). The class (and its methods) must keep track of the number of occurrences max for the most common word read. Then, add to this class a method rarity(self, word) that given a word, returns its rarity score (an integer in the range [0, 5]). We have provided ebooks of some classic texts from https://www.gutenberg.org/ in the Prac folder. Use Freq to read the provided 1342-0.txt, 2600-0.txt and 98-0.txt into your hash table. At the end of this process the table will store the number of times each word appears in the texts. We will consider the resulting hash table as a reasonably accurate representation of the frequency of words in the English language. Make sure you use the data you collected in the previous tasks to select an appropriate table size for the selected text files. Also, modify __setitem__ to call rehash when the load of the hash table is above 0.5, rather than when full (this will not be used if you choose an appropriate table size, but is more realistic for cases where you do not know the number or size of the books being read). Important: You must add your own tests for the add_file and rarity methods. Task 7 2 marks Add to the Freq class a method evaluate_frequency(self, other_filename) that returns a tuple (common, uncommon, rare, errors) of the percentage of words appearing in other_filename which have the corresponding rarity (with respect to the current frequency counts). 1This is known as Zipf’s law. You can read more at https://en.wikipedia.org/wiki/Zipf%27s_law Use evaluate_frequency to compute the frequency of each rarity score in 84-0.txt, using the expected frequencies you constructed in Task 6. Example Plot This is an example of the style of plot you should be generating: b=1, t=398 b=27183,t=40221 0 5 10 15 20 25