Assignment

The supplied program implements a form of ArrayList in Python. You will write a function to characterize its performance considering time and space. You will need to complete the analyzePerformance function to gather the data in the requested format. You will be given a list of values for N, a function to use for array growth, and the number of tries to average the time result over. This function returns a list of dictionaries, specified in the template code.

def analyzePerformance(nList, gfn, tries): data = [] ... return data 

For example, a call of the form analyzePerformance([10, 100], fn, 13) would produce the following result, a list containing a dictionary for each of the values in the list. The sample main program prints this out, each on a separate line.

[{'grow': .., 'N': 10, 'seconds': ..., 'sizes': [...]},{'grow': .., 'N': 100, 'seconds': ..., 'sizes': [...]}] 

We have provided a double function. You are encouraged to add the additional growth functions listed in 1.6.65 and test them out. You must create an additional growth function of your own design to discuss in the Canvas assignment along with those in 1.6.65. We will not use the the growth functions you create in the grading.

You may not modify the existing code in the ArrayList class, but you may add additional code to this class to capture and return the requested values for the different sizes of the array. Do not include the 0 in the sizes list, only the sizes created by the grow function. You will need to analyze this code to decide how to instrument it correctly and have no impact on the expected results.

You may also modify the main function to print the results from your other functions. Only the main function should do any printing. We do not use your main program in grading, it is ignored.

Grading

We do not use your main program, growth functions, or printed output in the grading of this assignment. We will unit test your analyzePerformance function by calling it directly using the following values and testing the list of dictionaries that your function returns.

different lists of N.

different growth functions defined in our test code.

different numbers of tries.

Note: please do not modify the code you might need to add some code

========================================================================================================

from time import time

''' The ArrayList class simulates a fixed array in Python, ala ArrayList in Java. Here we specify a growth function when we create the ArrayList. You may not modify any of the code here, but you may add additional code that does not affect the functioning of this code. ''' class ArrayList: def __init__(self, growfn): '''Initializes the empty ArrayList with the specified growth function.''' self.size = 0; self.used = 0; self.array = [] self.grow = growfn;

def get(self, index): if index < self.size: return self.array[index] # exception handling return None

def add(self, value): if self.used == self.size: newSize = self.grow(self.size) if newSize <= self.size: # exception handling return newArray = self.array[:]+[None for i in range(self.size,newSize)] self.array = newArray self.size = newSize self.array[self.used] = value self.used = self.used + 1 return None

''' Growth Functions Here is the basic growth function. You should add those from the assignment afterwards. ''' def double(size): if size == 0: return 1 return size + size

''' Additional growth functions for the solution. Three that were included in the assignment. '''

''' The analyzePerformance function accepts three parameters: * a list of N values for which results should be returned. * a growth function that returns the new size of the array given the old size. * the number of tries used to average the time. The analyzePerformance function returns a list of values, one for each value of N. Each of the values in the list is a dictionary {"grow": ..., "N":..., "seconds":..., "sizes":...} containing: * the growth function * the value of N * the decimal number of seconds required to add N elements to a new Array averaged over the specified number of tries. * the list of sizes the array grows through while adding the N elements Do not include the creation of the initial ArrayList object in the time. ''' def analyzePerformance(nList, gfn, tries): data = [] return data

''' Here is a sample main program for your testing purposes. We will use a different main program to call your analyze function with various lists and growth functions of our choice. You might graphs the values returned for the various functions to compare their actual versus expected behavior. ''' def main(): for result in analyzePerformance([1,10,100],double,11): print(result)

if __name__ == '__main__': main()

=============================================