2. Computational Complexity

In the last chapter we developed a drawing program. To hold the drawing commands we built the PyList container class which is a lot like the built-in Python list class, but helps illustrate our first data structure. When we added a drawing command to the sequence we called the append method. It turns out that this method is called a lot. In fact, the flower picture in the first chapter took around 700 commands to draw. You can imagine that a complex picture with lots of free-hand drawing could contain thousands of drawing commands. When creating a free-hand drawing we want to append the next drawing command to the sequence quickly because there are so many commands being appended. How long does it take to append a drawing command to the sequence? Can we make a guess? Should we care about the exact amount of time?

In this chapter you’ll learn how to answer these questions and you’ll learn what questions are important for you as a computer programmer. First you’ll read about some principles of computer architecture to understand something about how long it takes a computer to do some simple operations. With that knowledge you’ll have the tools you’ll need to make informed decisions about how much time it might take to execute some code you have written.

2.1. THe PlotData Program

You can download the program by clicking here. This program is used to plot data written in the plot XML format presented in the text. The next program, the list timing access program, writes data in the plot XML format.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
import turtle
import tkinter
import tkinter.colorchooser
import tkinter.filedialog
import xml.dom.minidom
import math
import sys

class PlotApplication(tkinter.Frame):
    def __init__(self, master=None, datafile=None):
        super().__init__(master)
        self.datafile = datafile
        self.pack()
        self.buildWindow()

 
    def buildWindow(self):
         
        self.master.title("Plot")

        bar = tkinter.Menu(self.master)
        fileMenu = tkinter.Menu(bar,tearoff=0)
            
        def loadFile(filename=None):

            if filename == None:
                filename = tkinter.filedialog.askopenfilename(title="Select a Plot File")
            
            theTurtle.clear()
            theTurtle.penup()
            theTurtle.goto(0,0)
            theTurtle.pendown()  
            screen.update()
            theTurtle.color("black")
            
            xmldoc = xml.dom.minidom.parse(filename)
                    
            plotElement = xmldoc.getElementsByTagName("Plot")[0]
            
            attr = plotElement.attributes
            self.master.title(attr["title"].value)

            axesElement = plotElement.getElementsByTagName("Axes")[0]
            
            xAxisElement = axesElement.getElementsByTagName("XAxis")[0]
            xAxisLabel = xAxisElement.firstChild.data.strip()
             
            yAxisElement = axesElement.getElementsByTagName("YAxis")[0]
            yAxisLabel = yAxisElement.firstChild.data.strip()
            
            xAttr = xAxisElement.attributes
            yAttr = yAxisElement.attributes
            
            minX = float(xAttr["min"].value)
            maxX = float(xAttr["max"].value)
            minY = float(yAttr["min"].value)
            maxY = float(yAttr["max"].value)
            
            xSize = maxX - minX
            ySize = maxY - minY
            xCenter = xSize / 2.0 + minX
            yCenter = ySize / 2.0 + minY
            
            xPlaces = max(4-round(math.log(xSize,10)),0)
            yPlaces = max(4-round(math.log(ySize,10)),0)
            
            labelYVal = maxY - 0.10 * ySize
            
            screen.setworldcoordinates(minX-0.20 * xSize,minY - 0.20 * ySize, \
                maxX + 0.20 * xSize,maxY + 0.20 * ySize)

            theTurtle.ht()
            
            theTurtle.penup()
            theTurtle.goto(minX,minY)
            theTurtle.pendown()
            theTurtle.goto(maxX,minY)
            theTurtle.penup()
            theTurtle.goto(minX,minY)
            theTurtle.pendown()
            theTurtle.goto(minX,maxY)
            theTurtle.penup()

            theTurtle.goto(xCenter, minY - ySize * 0.10)
            theTurtle.write(xAxisLabel,align="center",font=("Arial",14,"bold"))            

            theTurtle.goto(minX, maxY + 0.05 * ySize)
            theTurtle.write(yAxisLabel,align="center",font=("Arial",14,"bold"))
            
            for i in range(0,101,10):
                x = minX + xSize * i / 100.0
                y = minY + ySize * i / 100.0
                
                theTurtle.penup()
                theTurtle.goto(x,minY+ySize * 0.025)
                theTurtle.pendown()
                theTurtle.goto(x,minY-ySize * 0.025)
                theTurtle.penup()
                theTurtle.goto(x,minY-ySize * 0.05)
                
                theTurtle.write(("%1."+str(xPlaces)+"f")%x,align="center", \
                    font=("Arial",12,"normal"))
                
                theTurtle.penup()
                theTurtle.goto(minX+xSize * 0.025, y)
                theTurtle.pendown()
                theTurtle.goto(minX-xSize * 0.025, y)
                theTurtle.goto(minX-xSize * 0.001, y)
                theTurtle.write(("%1."+str(yPlaces)+"f")%y,align="right", \
                    font=("Arial",12,"normal"))
                 
            
            sequences = plotElement.getElementsByTagName("Sequence")
            
            for sequence in sequences:
                attr = sequence.attributes
                
                label = attr["title"].value.strip()
                color = attr["color"].value
                theTurtle.color(color)
                theTurtle.penup()
                theTurtle.goto(xCenter,labelYVal)
                labelYVal = labelYVal - 0.10 * ySize
                theTurtle.write(label,align="center",font=("Arial",14,"bold"))
                
                dataPoints = sequence.getElementsByTagName("DataPoint")
                
                first = dataPoints[0]
                attr = first.attributes
                x = float(attr["x"].value)
                y = float(attr["y"].value)
                theTurtle.goto(x,y)
                theTurtle.dot()
                theTurtle.pendown()
                
                for dataPoint in dataPoints:
                    attr = dataPoint.attributes
                    x = float(attr["x"].value)
                    y = float(attr["y"].value)
                    theTurtle.goto(x,y)
                    theTurtle.dot()
                    
                screen.update()

            
            
        fileMenu.add_command(label="Load Plot Data...",command=loadFile)
        
        fileMenu.add_command(label="Exit",command=self.master.quit)
        
        bar.add_cascade(label="File",menu=fileMenu)
        
        self.master.config(menu=bar)    
        
        canvas = tkinter.Canvas(self,width=1000,height=800)
        canvas.pack(side=tkinter.LEFT)
        
        theTurtle = turtle.RawTurtle(canvas)
         
        screen = theTurtle.getscreen()
        
        screen.tracer(0)

        if self.datafile != None:
            loadFile(self.datafile.strip())

def main():
    root = tkinter.Tk()
    datafile = None
    if len(sys.argv) > 1:
        datafile = sys.argv[1]
    plotApp = PlotApplication(root, datafile)  

    plotApp.mainloop()
    print("Program Execution Completed.")
        
if __name__ == "__main__":
    main()

2.2. List Access Timing

You can download the program by clicking here.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
import datetime 
import random
import time
        
def main():
    
    # Write an XML file with the results
    file = open("ListAccessTiming.xml","w")
    
    file.write('<?xml version="1.0" encoding="UTF-8" standalone="no" ?>\n')
    
    file.write('<Plot title="Average List Element Access Time">\n')
    
    # Test lists of size 1000 to 200000. 
    xmin = 1000
    xmax = 200000
    
    # Record the list sizes in xList and the average access time within
    # a list that size in yList for 1000 retrievals. 
    xList = []
    yList = []
    
    for x in range(xmin, xmax+1, 1000):

        xList.append(x)
        
        prod = 0
        
        # Creates a list of size x with all 0's
        lst = [0] * x
        
        # let any garbage collection/memory allocation complete or at least
        # settle down
        time.sleep(1)
        
        # Time before the 1000 test retrievals
        starttime = datetime.datetime.now()
        
        for v in range(1000):
            # Find a random location within the list
            # and retrieve a value. Do a dummy operation
            # with that value to ensure it is really retrieved. 
            index = random.randint(0,x-1)
            val = lst[index]
            prod = prod * val
        # Time after the 1000 test retrievals  
        endtime = datetime.datetime.now()
        
        # The difference in time between start and end.
        deltaT = endtime - starttime
        
        # Divide by 1000 for the average access time
        # But also multiply by 1000000 for microseconds.
        accessTime = deltaT.total_seconds() * 1000
        
        yList.append(accessTime)
     
    file.write('  <Axes>\n')
    file.write('    <XAxis min="'+str(xmin)+'" max="'+str(xmax)+'">List Size</XAxis>\n')
    file.write('    <YAxis min="'+str(min(yList))+'" max="'+str(60)+'">Microseconds</YAxis>\n')
    file.write('  </Axes>\n')
    
    file.write('  <Sequence title="Average Access Time vs List Size" color="red">\n')   
    
    for i in range(len(xList)):   
        file.write('    <DataPoint x="'+str(xList[i])+'" y="'+str(yList[i])+'"/>\n')    
        
    file.write('  </Sequence>\n')
    
    # This part of the program tests access at 100 random locations within a list
    # of 200,000 elements to see that all the locations can be accessed in 
    # about the same amount of time.
    xList = lst
    yList = [0] * 200000
    
    time.sleep(2)
    
    for i in range(100):
        starttime = datetime.datetime.now()
        index = random.randint(0,200000-1)
        xList[index] = xList[index] + 1
        endtime = datetime.datetime.now()
        deltaT = endtime - starttime   
        yList[index] = yList[index] + deltaT.total_seconds() * 1000000
        
    file.write('  <Sequence title="Access Time Distribution" color="blue">\n')           
  
    for i in range(len(xList)):
        if xList[i] > 0:
            file.write('    <DataPoint x="'+str(i)+'" y="'+str(yList[i]/xList[i])+'"/>\n')    
        
    file.write('  </Sequence>\n') 
    file.write('</Plot>\n')
    file.close()  
    
if __name__ == "__main__":
    main()

2.3. The PyList Datatype

This is the chapter 2 version of this datatype. In chapter 4 another, more complete version of this datatype is described. You can download the chapter 2 version of the datatype by clicking here.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class PyList:
    # The size below is an initial number of locations for the list object. The
    # count instance variable keeps track of how many elements are currently stored
    # in the list since self.items may have empty locations at the end.
    def __init__(self,size=5):
        self.items = [None] * size
        self.count = 0

    def append(self,item):
        if self.count == len(self.items):
            # We must make the list bigger by allocating a new list and copying
            # all the elements over to the new list.
            newitems = [None] * self.count * 2
            for k in range(len(self.items)):
                newitems[k] = self.items[k]

            self.items = newitems
            
        self.items[self.count] = item
        self.count += 1

def main():
    p = PyList()

    for k in range(100):
        p.append(k)

    print(p.items)
    print(p.count)
    print(len(p.items))

if __name__ == "__main__":
    main()