# Better sorting speed

import sys

lst = [int(sys.stdin.readline()) for i in xrange(x)]

lst.sort()

print lst


How can I make this code faster for large input?

• You probably can't; Python's built-in sort is Timsort, which is pretty good. – jonrsharpe Jul 6 '14 at 13:32
• is there any way in which i can make the iteration in the above more faster – shubham Jul 6 '14 at 13:45
• No; you need the int for correct sorting (unless all inputs will be single-digit numbers). – jonrsharpe Jul 6 '14 at 13:53
• One thing you need to consider is your actual use case. How large are these inputs? What resources do you have to perform your task? What about the performance of your current code is unsatisfactory? – AJMansfield Jul 6 '14 at 17:36

If "large input" is only up to a couple of GB, there's not much you can do. As long as all the data comfortably fits in memory, the built-in sort is about as good as you can get.

If, OTOH, your dataset is large enough to cause swapping and/or not load at all, you could:

1. Read the input in blocks, which you sort and save into files.
2. Merge the files while iterating by always choosing the extremal item.

By choosing block size close to sqrt(x), you only need to keep about $\sqrt x$ items in memory at a time.

Based on the dataset, and assuming you are using python v2, I would profile the speed of range over xrange. Depending on the dataset one might provide more performance over the other. Edit your code and run cProfile as such -

Example:

python -m cProfile test.py
1
9
[9]
5 function calls in 2.150 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    2.150    2.150 test.py:3(<module>)
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
2    2.149    1.075    2.149    1.075 {method 'readline' of 'file' objects}
1    0.000    0.000    0.000    0.000 {method 'sort' of 'list' objects}


You might also want to run a comparison with a generator expression to see if there is any benefit:

$more test1.py #!/usr/local/bin/python2.7 from bettertimeit import bettertimeit def test_me(): max1 = 100 def timeit_calculation(): l = [max1**2 for max1 in xrange(100)] max2 = 100 def timeit_calculation_2(): l = (max2**2 for max2 in xrange(100)) bettertimeit(test_me)$ ./test1.py
calculation: 100000 loops, best of 3: 9.76 usec per loop
calculation_2: 1000000 loops, best of 3: 0.723 usec per loop


Based on what you are doing, you may potentially be be able to speed things up by not using a list since there is some pre-allocation overhead that slows things down.

Also as part of:

list.sort() you can pass a key parameter to sort


which is supposedly faster than the default, however I never personally timed this. Beyond what I mentioned above, I don't think you can do much more without manipulating the dataset.

Hope this helps.

You might be able to get a mild speed-up by simply running the above code in python 3 instead of 2 (use range instead of xrange, as xrange was depreciated in v3 and turned into range). Another possible speed up is running the code under http://pypy.org. However, if you truly need bleeding performance, consider writing this code in C/C++.

Another thing to try is to rearrange your code in such a way that you sort at each iteration. Especially if you only need the last element, you do not even need a list. You can just store the desired elements and update them at each new line. However, if you do need the entire list to be sorted, this might give you more overhead than it's worth.