How to make faster Python code

Question

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 25-Jan-23 19:56pm

bartello

Updated 27-Jan-23 8:03am

Richard Deeming

v2

Add a Solution

2 solutions

Solution 2

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)

Posted 27-Jan-23 8:03am

bartello

Add a Solution

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

Richard Deeming · Accepted Answer · 2023-01-25T21:55:00

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.

How to make faster Python code

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

How to make faster Python code

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us