01
02
03
04
05
06
07
08
09
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
|
import time
run = 0
## python lists are mutable, whereas strings are immutable
def main0():
print ("main0")
l = [11, 21, 31, 41]
k = l
print (l)
k.append (51)
print (l, k)
s = "@@@@"
t = s
print (s)
s = s + "*"
print (s, t)
#run = 1 ## uncomment to run main1
## confirm that python copies strings when necessary
## to avoid unnecessary copying, the python compiler does alias analysis
## if s is aliased, then (end - middle) = O(n)
## if s is NOT aliased, then (end - middle) = O(1)
def main1 ():
print ("main1")
base = 2 ** 25
length = base
while length <= base * 32:
length = length * 2
t = ""
s = "*"
## create a big string
while len(s) < length:
s = s + s
start = time.time()
#t = s ## try (un)commenting this
middle = time.time()
s = s + "*"
end = time.time()
print ("Duration (" + str(len(s)) + "," + str(len(t)) + "): " + '{0:.8f}'.format(middle - start) + "," + '{0:.8f}'.format(end - middle))
#run = 2
## confirm that python does not copy lists
## regardless of whether s is aliased, (end - middle) = O(1)
def main2 ():
print ("main2")
base = 2 ** 25
length = base
while length <= base * 8:
length = length * 2
t = []
s = ["*"]
## create a big list
while len(s) < length:
s = s + s
start = time.time()
#t = s ## try (un)commenting this
middle = time.time()
s.append(0)
end = time.time()
print ("Duration (" + str(len(s)) + "," + str(len(t)) + "): " + '{0:.8f}'.format(middle - start) + "," + '{0:.8f}'.format(end - middle))
def addOne (s):
return s + "*"
#run = 3
## This test allows you to time list and string creation
## try uncommenting lines 1-6, one at a time.
def main3 ():
print ("main3")
base = 10000
for multiplier in [1, 2, 4, 8, 16, 32]:
length = base * multiplier
l = []
s = ""
start = time.time()
for i in range (length):
l.append("*") ## 1. list append at end
#l.insert(len(l), "*") ## 2. list append at end
#l.insert(0, "*") ## 3. list prepend at beginning
#s = s + "*" ## 4. string append at end
#t = s + "*" ## 5a. string append at end with temporary
#s = t ## 5b. (this goes with 5a)
#s = addOne (s) ## 6. string append with function call
end = time.time()
print ("Duration (" + str(length) + "): " + '{0:.8f}'.format(end - start))
mains = [main0, main1, main2, main3]
mains[run]()
# for m in mains:
# m()
|