Better sorting speed

Question

import sys

x=int(sys.stdin.readline())

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

lst.sort()

print lst 

How can I make this code faster for large input?

Answer 1

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.

Answer 2

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.

Answer 3

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.