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
|
def min1 (lst):
minSoFar = lst[0]
for x in lst:
if x < minSoFar:
minSoFar = x
return minSoFar
def min2 (lst):
for x in lst:
numSmaller = sum(y < x for y in lst)
if numSmaller == 0:
return x
import time
import random
for f in [min1, min2]:
print ("testing " + f.__name__)
assert 1 == (f ([1, 12, 23, 3, 24, 25, 2]))
assert 2 == (f ([12, 23, 3, 24, 25, 2]))
assert 3 == (f ([12, 23, 3, 24, 25, 4]))
assert 3 == (f ([12, 3, 24, 25]))
base = 2000
for multiplier in [1, 2, 4, 8]:
length = base * multiplier
lst = [random.random() for i in range(length)] # min random
#lst = [-i for i in range(length)] # min at end
#lst = range(length) # min at beginning
start = time.time()
result = f (lst)
end = time.time()
print ("Duration of " + f.__name__ + "(" + str(len(lst)) + "): " + str(end - start))
def minPos1 (lst):
minPosSoFar = 0
for i in range(len(lst)):
if lst[i] < lst[minPosSoFar]:
minPosSoFar = i
return minPosSoFar
assert 0 == (minPos1 ([1, 12, 23, 3, 24, 25, 2]))
assert 5 == (minPos1 ([12, 23, 3, 24, 25, 2]))
assert 2 == (minPos1 ([12, 23, 3, 24, 25]))
assert 1 == (minPos1 ([12, 3, 24, 25]))
def minPos2 (lst):
minSoFar = lst[0]
minPosSoFar = 0
for i in range(len(lst)):
if lst[i] < minSoFar:
minPosSoFar = i
minSoFar = lst[i]
return minPosSoFar
assert 0 == (minPos2 ([1, 12, 23, 3, 24, 25, 2]))
assert 5 == (minPos2 ([12, 23, 3, 24, 25, 2]))
assert 2 == (minPos2 ([12, 23, 3, 24, 25]))
assert 1 == (minPos2 ([12, 3, 24, 25]))
def minPos3 (lst):
minPosSoFar = 0
n = len(lst)
i = 1
while i < n:
if lst[i] < lst[minPosSoFar]:
minPosSoFar = i
i += 1
return minPosSoFar
assert 0 == (minPos3 ([1, 12, 23, 3, 24, 25, 2]))
assert 5 == (minPos3 ([12, 23, 3, 24, 25, 2]))
assert 2 == (minPos3 ([12, 23, 3, 24, 25]))
assert 1 == (minPos3 ([12, 3, 24, 25]))
def minPosR (lst):
return minPosHelper (lst, 1, 0)
def minPosHelper (lst, i, minPosSoFar):
if i >= len(lst):
return minPosSoFar
if lst[i] < lst[minPosSoFar]:
return minPosHelper (lst, i + 1, i)
else:
return minPosHelper (lst, i + 1, minPosSoFar)
assert 0 == (minPosR ([1, 12, 23, 3, 24, 25, 2]))
assert 5 == (minPosR ([12, 23, 3, 24, 25, 2]))
assert 2 == (minPosR ([12, 23, 3, 24, 25]))
assert 1 == (minPosR ([12, 3, 24, 25]))
print ("Finished tests")
|