-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmode.py
More file actions
47 lines (42 loc) · 1.16 KB
/
mode.py
File metadata and controls
47 lines (42 loc) · 1.16 KB
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
__author__ = 'Theo'
#
# Given a list L of n numbers, find the mode
# (the number that appears the most times).
# Your algorithm should run in Theta(n).
# If there are ties - just pick one value to return
#
from operator import itemgetter
def mode(L):
# your code here
counts = {}
for y in L:
oldVal = counts.get(y, 0)
counts[y] = oldVal + 1
return max(counts, key=counts.get)
####
# Test
#
import time
from random import randint
def probar():
assert 5 == mode([1, 5, 2, 5, 3, 5])
iterations = (10, 20, 30, 100, 200, 300, 1000, 5000, 10000, 20000, 30000)
times = []
for i in iterations:
L = []
for j in range(i):
L.append(randint(1, 10))
start = time.clock()
for j in range(500):
mode(L)
end = time.clock()
print start, end
times.append(float(end - start))
slopes = []
for (x1, x2), (y1, y2) in zip(zip(iterations[:-1], iterations[1:]), zip(times[:-1], times[1:])):
print (x1, x2), (y1, y2)
slopes.append((y2 - y1) / (x2 - x1))
# if mode runs in linear time,
# these factors should be close (kind of)
print slopes
probar()