CODEWITHSUNDEEP
pythonperformancepython-3.xoptimization
Rasmi Ranjan Nayak
Rasmi Ranjan Nayak

Reputation: 11948

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). Please help.

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

Upvotes: 2

Views: 213

Answers (1)

Dolda2000
Dolda2000

Reputation: 25855

Your primary culprit is the counting code, which unnecessarily scales with O(m*n), if n is the number of inputs and m is the number of unique inputs. 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 unique element in the list, resulting in m*n iterations in total (resulting in ~256 million iterations for your larger example).

Switching it to this implementation solves that problem and improves the runtime quite a lot (I'm not getting your 10+ seconds to begin 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)

Upvotes: 3

Related Questions