In this assignment we will hope to demonstrate the efficiency of dictionaries over lists for certain types of tasks. Most specifically, the task will be looking up telephone numbers of people in a phonebook data structure.To do this you will write two programs: one that creates data files to process, and a second that does timing comparisons for phone number queries in two different data structures.
Program 1:
This program will create a data file containing a specified number of phone records. The program should ask the user for a file name and the desired number of records. Each record in the file will contain three values separated by spaces: a first name, a last name, and a phone number.
Write a generator function that will return a randomly generated phone record when called. For the random generation, we will use a different function from the random module called choice(). You can pass this function a string containing characters to choose from, and it will randomly pick one. For the random record do the following. For both the first and last name, create strings of length 4, where each character is a randomly chosen lower case letter. For the phone number, this can be 7 characters long, where each character is a randomly chosen digit, 0-9. Yield a list that contains these three values, similar to what we saw in class. This function should have one parameter, which is the total number of records it should generate. You can then iterate through these records using a for loop, and you can write one line to your data file for each record generated.
Program 2:
This program will do timing tests. It should begin by reading the name of a data file to process. You should iterate through the lines of this file to create a list of phone records, where each phone record is a list of the three values: first name, last name, and phone number. You should also write a binary search function, that when passed a list and a name, will return the phone number for that name if it exists, or the value None if it does not. Write an iterative binary search routine rather than a recursive function (which is slower). Include in your code the comparison function we wrote in class for comparing names for a sort.
Next you will do a timing comparison. For the first timing, you should begin by creating a sorted version of the phone record list. You can use the sorted() function and pass it the phone record list and the name of the name comparison function. Then write a loop that iterates through every name in the original list, calling the binary search function to locate the corresponding phone number in the sorted list. You do not need to print out the search results. To compute how much time the sorting and searching takes, you can using the time() function in the time module. By calling this function before you start a task, and then after you are done with the task, you can subtract these two values to determine how long the task took. Time the sorting process. Then time the search loop. You should print out these two times.
For the second timing, you should create a dictionary, where the key for the dictionary is a string formed of the last name and first name, with a comma in between (just like we did in class), and the value stored in the dictionary is the phone number. Then use the same loop that iterates through every name in the original list, looking up the name in the dictionary to locate the corresponding phone number. You do not need to print out the number. Time the dictionary creation process. Then time the search loop. You should print out these two times.
What to turn in:
You should turn in the source code for the two programs. You should use your first program to create a set of data files that range in size from 100 to 10 million phone records. Then run each of these files through your second program to get timing results. Make a small table that compares these timing values for each of the different file sizes to see how the performance of using a list degrades in comparison to using the dictionary. Submit this table as well.