Map Performance

We now have three implementation of the Map ADT that we've experimented with.

1. Python's dict structure with its key-value pairs
2. Our HashTable class that uses a paired list of values to store key-value information
3. The BinarySearchTree class that uses a series of TreeNode objects linked together by references.

Write a program map_performance.py which includes your programmatic solutions to these questions.

1. Which Map implementation is best for looking up information for a single set of data?

   To answer this question, construct a structure for each of the three Map implementations, fill it with 10000 random integers (each between 1 and 100000?), and then time how long it takes to look up a single value from each Map structure. Given what you know about each structure, can you predict which one will be fastest?

2. Which Map implementation is most performant? Ie. which has the best Big-O performance? This, of course, requires testing each map over a range of conditions. How does the time that it takes to look up a value compare with the number of values that have to be looked through? Collect data that can be graphed to help in identifying performance.

Extension 1

Use Python and the matplotlib library to create graphs of your data for each solutions retrieval time as a function of map size.

Extension 2

Use numpy or scipy tools to identify a regression for the data you plotted in Extension 1.