Create an Analysis experiment program. (Please use simple python code for an int

Question

Create an Analysis experiment program.

(Please use simple python code for an introductory python class)

The following is a list of information needed to create the Analysis experiment program:

-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

The Timer will be storing the integers in a dictionary using the strings as keys.

# {{{cog include('timeit/timeit_dictionary.py', 'header')}}}
import timeit
import sys

# A few constants
range_size=1000
count=1000
setup_statement="l = [ (str(x), x) for x in range(%d) ]; d = {}" % range_size
# {{{end}}}

Next, we can define a short utility function to print the results in a useful format. The timeit() method returns the amount of time it takes to execute the statement repeatedly. The output of show_results() converts that into the amount of time it takes per iteration, and then further reduces the value to the amount of time it takes to store one item in the dictionary (as averages, of course).

# {{{cog include('timeit/timeit_dictionary.py', 'show_results')}}}
def show_results(result):
"Print results in terms of microseconds per pass and per item."
global count, range_size
per_pass = 1000000 * (result / count)
print '%.2f usec/pass' % per_pass,
per_item = per_pass / range_size
print '%.2f usec/item' % per_item

print "%d items" % range_size
print "%d iterations" % count
print
# {{{end}}}
To establish a baseline, the first configuration tested will use __setitem__(). All of the other variations avoid overwriting values already in the dictionary, so this simple version should be the fastest.

Notice that the first argument to Timer is a multi-line string, with indention preserved to ensure that it parses correctly when run. The second argument is a constant established above to initialize the list of values and the dictionary.

# {{{cog include('timeit/timeit_dictionary.py', 'setitem')}}}
# Using __setitem__ without checking for existing values first
print '__setitem__: ',
sys.stdout.flush()
# using setitem
t = timeit.Timer("""
for s, i in l:
d[s] = i
""",
setup_statement)
show_results(t.timeit(number=count))
# {{{end}}}
The next variation uses setdefault() to ensure that values already in the dictionary are not overwritten.

# {{{cog include('timeit/timeit_dictionary.py', 'setdefault')}}}
# Using setdefault
print 'setdefault: ',
sys.stdout.flush()
t = timeit.Timer("""
for s, i in l:
d.setdefault(s, i)
""",
setup_statement)
show_results(t.timeit(number=count))
# {{{end}}}
Another way to avoid overwriting existing values is to use has_key() to check the contents of the dictionary explicitly.

# {{{cog include('timeit/timeit_dictionary.py', 'has_key')}}}
# Using has_key
print 'has_key: ',
sys.stdout.flush()
# using setitem
t = timeit.Timer("""
for s, i in l:
if not d.has_key(s):
d[s] = i
""",
setup_statement)
show_results(t.timeit(number=count))
# {{{end}}}
Or by adding the value only if we receive a KeyError exception when looking for the existing value.

# {{{cog include('timeit/timeit_dictionary.py', 'exception')}}}
# Using exceptions
print 'KeyError: ',
sys.stdout.flush()
# using setitem
t = timeit.Timer("""
for s, i in l:
try:
existing = d[s]
except KeyError:
d[s] = i
""",
setup_statement)
show_results(t.timeit(number=count))
# {{{end}}}
And the last method we will test is the (relatively) new form using

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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