Analysis program Create an Analysis experiment program u sing simple Python code

Question

Analysis program

Create an Analysis experiment program using simple Python code. (list below)

-Devise an Analysis experiment to verify that get item and set item are O(1) for dictionaries.

-Measure the execution time for get and set for various size dictionaries of n entries. (Have the program create a table of executions times for each size output. Each line will have the size, set time, and get time with tabs ( ) between the numbers.)

-Run the program with different sizes to show that the times are constant with respect to the size.

The program below can be used as an example.

import time

def timeInsert(n):

    l = list(range(n))

    times = 750

    lists = [ list(l) for i in range(times)]

    t1 = time.time()

    for i in range(times):

        x = lists[i]

        x.insert(n-1,"x")

        x.insert(n//2,"x")

        x.insert(0,"x")

    t2 = time.time()

    return (t2-t1)

zeros = 0

for n in range(1,50000,150):

    t = timeInsert(n)

    print( "%d %f" % (n,t))

    if t == 0.0:

        zeros = zeros + 1

print("zeros: ", zeros)

The code below can be used as an example for creating a dictionary.

d = dict()

for i in range(n):

   d[i] = i

dicts = [ dict(d) for i in range(times) ]

Explanation / Answer

Here we collect elements of A[] smaller than or equal to the pivot in the array L and those that are larger than the pivot in the array R. We allocate memory for these additional arrays. Since the sizes of L and R are not known a priori, we have to prepare for the maximum possible size (n-1) for both. In addition, we use a constant number (six) of variables. The total additional space requirement for this function is therefore

which is O(n).

Let us plan to reduce this space requirement. A possible first approach is to store L and R in a single array LR of size n-1. Though each of L and R may be individually as big as having a size of n-1, the total size of these two arrays must be n-1. We store elements of L from the beginning and those of R from the end of LR. The following code snippet incorporates this strategy:

The total amount of extra memory used by this function is

which, though about half of the space requirement for partition1, is still O(n).

We want to reduce the space complexity further. Using one or more additional arrays will always incur O(n) space overhead. So we would avoid using any such extra array, but partition A in A itself. This is called in-place partitioning. The function partition3 below implements in-place partitioning. It works as follows. It maintains the loop invariant that at all time the array A is maintained as a concatenation LUR of three regions. The leftmost region L contains elements smaller than or equal the pivot. The rightmost region R contains elements bigger than the pivot. The intermediate region U consists of yet unprocessed elements. Initially, U is the entire array A (or A without the first element which is taken to be the pivot), and finally U should be empty. The region U is delimited by two indices lIdx and rIdx indicating respectively the first and last indices of U. During each iteration, the element at lIdx is compared with the pivot, and depending on the comparison result this element is made part of L or R.

The function partition3 uses only four extra variables and so its space complexity is O(1). That is a solid improvement over the earlier versions.

It is easy to check that the time complexity of each of these three partition routines is O(n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.