CODEWITHSUNDEEP
pythonperformance
Suhaib Shakeel
Suhaib Shakeel

Reputation: 23

Why is Code 1 faster than Code 2?

Code 1:

n = int(input())
ls = []
for x in range(n):
    ls += [(input())]
ls.sort(key = int)
for x in ls:
    print (x)

Code 2:

n = int(input())
ls = []
for x in range(n):
    ls += [int(input())]
ls.sort()
for x in ls:
    print (x)

These were my solutions to the HackerRank's "Big Sorting" problem: https://www.hackerrank.com/challenges/big-sorting

Code 1 does not give time limit exceeded error while Code 2 does.

Why is Code 1 faster and than Code 2?

Upvotes: 1

Views: 134

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1121306

The code is slower because you now need to convert the list of integers back to strings, while version 2 keeps the string versions, only converting to integers to sort.

Converting integers back to strings takes time too:

>>> import timeit
>>> timeit.timeit("str(235739630407432043190819704398)", number=10**7)
2.4063552810002875

I strongly suspect that the values to sort included in some of the tests are both numerous and very, very large.

I'd not use in-place extending either. Use a list comprehension instead:

ls = [input() for x in range(n)]

Personally, I'd use iteration over sys.stdin to read faster than input() calls can; here all loops are delegated to optimised C code:

import sys
from itertools import islice

n = int(next(sys.stdin))
nums = sorted(map(str.strip, islice(sys.stdin, n)), key=int)
print(*nums, sep='\n')

(because the last line read from stdin has no newline you can't count on the newline being present on all lines, and then it's just easier and faster to strip).

Replacing str.strip with int will once more cause time-outs.

Upvotes: 4

Related Questions