from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
import time
time.time()
1706539148.227787
import time
time.time()
1706539168.5435426
from time import time, sleep
start = time()
sleep(1)
end = time()
print(end - start)
1.0121650695800781
from time import time, sleep
start = time()
sum(range(10**6))
end = time()
print(end - start)
499999500000
0.05357217788696289
def myTimer(f):
start = time()
f()
end = time()
return (end - start)
myTimer(lambda: sum(range(10**6)))
0.043149471282958984
def myTimer1(f):
duration=0
for _ in range(10):
start = time()
f()
end = time()
duration+=(end - start)
return duration/10
myTimer1(lambda: sum(range(10**6)))
0.03145809173583984
import timeit
timeit.timeit('sum(range(10**6))', number=100)
2.8972529000000122
timeit.timeit(stmt='sorted(lst)',
setup='import random ; lst = [random.random() for _ in range(100)]',
number=100)
0.001084900000023481
import random # we can use timeit to time whatever we want
def to_time(lst):
# do something interesting with the list
pass
timeit.timeit(stmt='to_time(lst)',
setup='lst = [random.random() for _ in range(100)]',
globals=globals(), # allows timeit to access functions we've defined in this notebook
number=1000)
0.00022620000004280882
lst = [0] * 10**5
#lst
lst[0]
0
import timeit
timeit.timeit(stmt='lst[0]', globals=globals())
0.0521668999999747
timeit.timeit(stmt='lst[10**5-1]', globals=globals())
0.04811310000013691
times = [timeit.timeit(stmt='lst[{}]'.format(i),
globals=globals(),
number=100)
for i in range(10**5)]
times[:10]
[1.7099999695346924e-05, 1.609999981155852e-05, 1.6200000118260505e-05, 1.6200000118260505e-05, 1.5700000403739978e-05, 1.1800000265793642e-05, 1.1899999663000926e-05, 1.1799999811046291e-05, 1.1699999959091656e-05, 1.1999999969702912e-05]
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x25d31953250>]
Observation: accessing an element in a list by index takes a constant amount of time, regardless of position.
How? A Python list uses an array as its underlying data storage mechanism. To access an element in an array, the interpreter:
Task: to locate an element with a given value in a list (array).
def index(lst, x): # return left most index location of value x, None on not found
i=0
for a in lst:
if a==x:
return i
i+=1
return None
# return True #but we want index
lst = list(range(100))
index(lst, 10)
10
index(lst, 99)
99
index(lst, -1)
def index(lst, x): # return left most index location of value x, None on not found
for i in range(len(lst)):
if lst[i]==x:
return i
return None
# return True #but we want index
lst = list(range(100))
index(lst, 10)
10
def index(lst, x): # return left most index location of value x, None on not found
for i, a in enumerate(lst):
if a==x:
return i
return None
# return True #but we want index
lst = list(range(100))
index(lst, 10)
10
import timeit
lst = list(range(1000))
times = [timeit.timeit(stmt='index(lst, {})'.format(x),
globals=globals(),
number=100)
for x in range(1000)]
import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x25d341d2370>]
Task: to locate an element with a given value in a list (array) whose contents are sorted in ascending order.
def index(lst, x):
# assume that lst is sorted!!!
start=0
end=len(lst)-1
while start<=end:
mid=(start+end)//2
# lst[mid] == x or lst[mid] < x or lst[mid] > x
if lst[mid] == x:
return mid
elif lst[mid] < x:
start=mid+1
else:
end=mid-1
return None
lst = list(range(1000)) # THIS IS SORTED
index(lst, 10)
10
index(lst, 999)
999
index(lst, -1)
import timeit
lst = list(range(1000))
times = [timeit.timeit(stmt='index(lst, {})'.format(x),
globals=globals(),
number=1000)
for x in range(1000)]
import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x25d31d321c0>]
import timeit
times = []
for size in range(1000, 100000, 100):
lst = list(range(size))
times.append(timeit.timeit(stmt='index(lst, -1)',
globals=globals(),
number=1000))
import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x25d331012e0>]
import timeit
times = []
for e in range(5, 20):
lst = list(range(2**e))
times.append(timeit.timeit(stmt='index(lst, -1)',
globals=globals(),
number=100000))
# growth in runtime on a not found binary search
import matplotlib.pyplot as plt
plt.plot(times, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x25d331c1f70>]
Task: to sort the values in a given list (array) in ascending order.
import random
lst = list(range(1000))
random.shuffle(lst)
import matplotlib.pyplot as plt
plt.plot(lst, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x286ef7579a0>]
def insertion_sort(lst):
# outer loop that keeps track of the index of the current item (the next item to be walked down)
for i in range(1,len(lst)):
j=i
# inner loop to "walk it down"
while j>0 and lst[j-1] > lst[j]:
# if lst[j-1] > lst[j]:
#swap em
lst[j-1],lst[j] = lst[j],lst[j-1]
#move i i-=1
j-=1
insertion_sort(lst)
lst[:10]
lst[990:]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[990, 991, 992, 993, 994, 995, 996, 997, 998, 999]
plt.plot(lst, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x286ef7b7070>]
import timeit
import random
times = [timeit.timeit(stmt='insertion_sort(lst)',
setup='lst=list(range({})); random.shuffle(lst)'.format(size),
globals=globals(),
number=1)
for size in range(100, 5000, 250)]
plt.plot(times, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x286ef808700>]
def selection_sort(lst):
# DO THIS MULTIPLE TIMES on a smaller lst each time
# lst is "from" index 0 "to" index len(lst)-1
# find me the smallest item in lst "from" "to"
# swap that item into postion 0, position 0 goes to that items position
for i in range(0,len(lst)): # i is the index to start the find min at
# also where to swap that min to
currentmin=lst[i]
currentj=i
#find min inner loop
for j in range(i+1,len(lst)):
if lst[j]<currentmin:
currentmin=lst[j]
currentj=j
lst[i],lst[currentj]=lst[currentj],lst[i]
import random
lst1 = list(range(1000))
random.shuffle(lst1)
selection_sort(lst1)
plt.plot(lst1, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x286ef8699a0>]
import timeit
import random
times = [timeit.timeit(stmt='selection_sort(lst)',
setup='lst=list(range({})); random.shuffle(lst)'.format(size),
globals=globals(),
number=1)
for size in range(100, 5000, 250)]
plt.plot(times, 'ro')
plt.show()
[<matplotlib.lines.Line2D at 0x286ef8c8280>]