In algorithms and data structures I implemented an unsorted unique container class for each of the following:
| Container | Description | Time Average | Time Worst | Space Worst |
|---|---|---|---|---|
| Python List | This is a simple list of items. The simplest type of array data structure is a linear array, also called one-dimensional array. Think of it as a giant filing cabinet drawer. Each item is placed in a folder and placed right behind another, but none of them are sorted. If you have to retrieve an item, each folder must be checked until the item is found. | O(n) | O(n) | O(n) |
| Binary Search Tree or Binary Tree (BST) | In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. (Wikipedia) | O(log(n)) | O(n) | O(n) |
| Hash Table or Hash Map | In computing, a hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array ofbuckets or slots, from which the correct value can be found. (Wikipedia) | O(1) | O(n) | O(n) |
Big O Notation
Big O notation is used to classigy algoritms by how they respond (processing time or working space requirements) to changes in input size. More on big O notation can be found at Big-O Cheatsheet and on Wikipedia's Big O Notation page.
Requirements
Each class should support these methods: Exists, Insert, Traverse, Delete, Retrieve, and Size. Compare the Insert, Traverse, Delete, and Retrieve times for each container class with the dataset. Each dataset is a text file containing a line of five whitespace separated "student records" with the following fields last name, first name, SSN, email, and age. Here is a sample line from the a data file:
WHITE WALTER 123-45-6789 W.WHITE@NEWMEXICO.ORG 49
Data sets
There were three different sizes of datasets and only the small file should be used with the Python List container class. Also, for saving time one should create a smaller list of data for testing purposes.
| Records | Size | ||
|---|---|---|---|
| Small | 30,000 | 1.61 MB | |
| Medium | 300,000 | 16.1 MB | |
| Large | 3,000,000 | 161.1 MB |
Results using Python 2.7
- All times are listed in seconds.
- Hovering over a bar in histogram will modify the pie chart and legend.
- Hovering over pie slice will update the histogram.