Repository navigation
Expand file tree
/
Copy pathanaga_time.py
More file actions
84 lines (59 loc) · 2.06 KB
/
Copy pathanaga_time.py
File metadata and controls
84 lines (59 loc) · 2.06 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
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
import sys, random, string, time
n_arr = [63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767]
k_arr = [4, 7, 10, 13, 16, 19, 22, 25, 28, 31]
def randomString(size):
letters = string.ascii_lowercase
return ''.join(random.choice(letters) for i in range(size))
def algorithm(n, k):
count = 0
accepted = set()
rejected = set()
for i in range(n):
line = randomString(size)
count += 1
joined = ''.join(sorted(line.rstrip()))
if joined in accepted:
accepted.remove(joined)
rejected.add(joined)
elif joined not in rejected:
accepted.add(joined)
if count > n:
break
def time_constK(k):
for n in n_arr:
finalTime = 0
for i in range(999):
tic = time.process_time()
algorithm(n, k)
toc = time.process_time()
elapsed = toc - tic
tic2 = time.process_time()
for i in range(n):
randomString(k)
toc2 = time.process_time()
elapsed2 = toc2 - tic2
finalTime = finalTime + (elapsed - elapsed2) * 1000
finalTime = finalTime / 1000
print("Total time for " + str(n) + ": " + str(elapsed) + " overhead: " + str(elapsed2) + "\n Total - overhead: " + str(finalTime) + " ms\n")
def time_constN(n):
for k in k_arr:
finalTime = 0
for i in range(999):
tic = time.process_time()
algorithm(n, k)
toc = time.process_time()
elapsed = toc - tic
finalTime = finalTime + elapsed * 1000
finalTime = finalTime / 1000
print("Total time for word size " + str(k) + ": " + str(finalTime) + " ms\n")
line1 = sys.stdin.readline()
firstline = line1.split()
numWords = int(firstline[0])
size = int(firstline[1])
is_constN = int(firstline[2])
if (is_constN == 1):
time_constN(numWords)
elif (is_constN == 0):
time_constK(size)
#print(len(accepted))
sys.exit()