Rasmi Ranjan Nayak - 4 months ago 5x
Python Question

# How to optimize the python code (running time should be less than 10s)?

I have to optimize the code, as the running time of the code goes above

`10s`
. The code works absolutely fine (less than
`10s`
) for small inputs if the input length increases then the output goes above
`10s`
.

``````import re, time
#from collections import OrderedDict
final_dict = {}
k_m_n = input()
k_m_n = list(map(lambda x: int(x), re.findall(r'([0-9]+)', k_m_n)))
AI = []
start = time.time()
for i in range(k_m_n[2]):
AI.append(int(input()))
AI_sort, l = sorted(AI), len(AI)

i = 0
while i < l:
final_dict[AI_sort[i]] = cnt = AI_sort.count(AI_sort[i])
i += cnt
print(final_dict)
i = 0
for k in sorted(final_dict, key=final_dict.get, reverse=True):
if i < k_m_n[0]:
print(k)
i += 1

print(time.time()-start)
``````

if the input is

`k_m_n = 3 3 8`

and
`AI.append(int(input())) = 2 2 1 1 1 5 5 5`
. It works fine.

if the input is
`k_m_n = 999 999 256000`
and
`AI.append(int(input()))= 1..999..1...999`
(then the time goes above
`10s`

``````K = 3: Number of output I want to see
m = 3: Number of different types of numbers
n = 8: List of numbers

Suppose
AI.append(int(input())) = 2 2 1 1 1 5 5 5
Here there are 3 types of number provided (2,1,5) # m
Total numbers in the list are = 8 # n
Outputs required in lexical order here is 1 5 2 #k.. although 1 and 5 are repeated 3 times but I need to print 1 then 5 then 2
``````

Your primary culprit is the counting code, which unnecessarily scales with `O(l^2)`. That is, this part:

``````i = 0
while i < l:
final_dict[AI_sort[i]] = cnt = AI_sort.count(AI_sort[i])
i += cnt
``````

This implementation walks through the list entirely to count the elements for each element in the list, resulting in `l^2` iterations in total. It also does unnecessary work by re-counting each element for every time it appears in the list, just overwriting the previous, identical result.

Switching it to this implementation solves that problem and improves the runtime quite a lot (I'm not getting your 10+ seconds to being with, though, but perhaps that's a difference in hardware performance):

``````final_dict = {}
for a in AI_sort:
final_dict[a] = final_dict.get(a, 0) + 1
``````

That being said, though, there are quite some other unnecessary things that the program does as well. It could be written with far less code this way:

``````import collections

k, m, n = [int(x) for x in input().split()]
occurrences = collections.Counter(int(input()) for i in range(n))
for num, seen in occurrences.most_common(k):
print(seen)
``````