Click here to Skip to main content
15,850,750 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
Hi, friends!

Can anyone tell me how can I make this code work faster.
Python
import sys
import time

for i in range(int(sys.stdin.readline())):

    sys.stdin.readline()
    # too slow, when len(lst) is about 20000
    lst = [int(i) for i in sys.stdin.readline().split()]

    summa = 0
    for item in set(lst):
      cnt = lst.count(item)
      summa += (cnt // 3 * 2 + cnt % 3) * item
    
    print(summa)


What I have tried:

Firstly I did this with dictionary, but it works too slow
Python
def calc_count(lst):
   d = dict()
   
   for item in lst:
      if(item not in d):
         cnt = lst.count(item)
         d[item] = cnt // 3 * 2 + cnt % 3
         
   return d
 
n = int(input())
 
 
for i in range(n):
    m = int(input())
    line = [int(i) for i in input().split()]
    
    dd = calc_count(line)
    
    summa = 0
    for item in dd:   
       summa += item * dd[item]
    print(summa)     


Then I do some refactoring, but it works still too slow.
Now I can't understand how can I make it faster.
Posted
Updated 27-Jan-23 9:03am
v2

Your original code iterates over the list in the order of N+1 times - once to generate a set of unique values, and once for each unique value to count the number of occurrences.

Your dictionary code also iterates over the list in the order of N+1 times - once for the outer loop, and once for each unique value to count the number of occurrences. That isn't going to improve the performance at all.

Try something like this:
Python
def calc_count(lst):
   d = dict()
   for item in lst:
      if (item in d):
         d[item] = d[item] + 1
      else
         d[item] = 1
         
   return d

n = int(input())
for i in range(n):
    m = int(input())
    line = [int(i) for i in input().split()]
    
    dd = calc_count(line)
    
    summa = 0
    for item in dd:
       cnt = dd[item]
       summa += (cnt // 3 * 2 + cnt % 3) * item
    
    print(summa)     
That iterates over the list once, either adding or updating the count stored in the dictionary.

NB: Since you don't know the final count when you add or update the dictionary, the formula needs to remain in the code that loops over the final dictionary.
 
Share this answer
 
Thank u for your answer!
I found a another solution.
from collections import Counter
import sys
 
for i in range(int(sys.stdin.readline())):
 
    sys.stdin.readline()
    lst = [int(i) for i in sys.stdin.readline().split()]
 
    cnt_lst = Counter(lst)
    summa = 0
    for item, cnt in Counter(lst).items():
        summa += (cnt // 3 * 2 + cnt % 3) * item
 
    print(summa)
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900