9
\$\begingroup\$

I am trying to write a count sort in Python to beat the built-in timsort in certain situations. Right now it beats the built-in sorted function, but only for very large arrays (1 million integers in length and longer, I haven't tried over 10 million) and only for a range no larger than 10,000. Additionally, the victory is narrow, with count sort only winning by a significant margin in random lists specifically tailored to it.

I have read about astounding performance gains that can be gained from vectorizing Python code, but I don't particularly understand how to do it or how it could be used here. I would like to know how I can vectorize this code to speed it up, and any other performance suggestions are welcome.

def countsort(unsorted_list):
    counts = {}
    for num in unsorted_list:
        if num in counts:
            counts[num] += 1
        else:
            counts[num] = 1

    sorted_list = []
    for num in xrange(min(unsorted_list), max(unsorted_list) + 1):
        if num in counts:
            for j in xrange(counts[num]):
                sorted_list.append(num)

    return sorted_list

GitHub

Additional info:

  • All that counts is raw speed here, so sacrificing even more space for speed gains is completely fair game.
  • I realize the code is fairly short and clear already, so I don't know how much room there is for improvement in speed.
  • If anyone has a change to the code to make it shorter, as long as it doesn't make it slower, that would be awesome as well.
  • After doing some more precise timing, it is clear that the first for loop takes about 2/3 of the execution time, with the second, constructor, loop taking just 1/3 of the time.
\$\endgroup\$
15
\$\begingroup\$

I did some benchmarks using the timeit module and this test data:

random.seed(1)
data = [random.randint(0,10000) for _ in xrange(1000000)]

Original version clocks in at 411 ms, and the builtin sorted at 512 ms.

Using counts = defaultdict(int) that allows unconditional counts[num] += 1 takes it to 330 ms.

Using sorted_list.extend(counts[num] * [num]) instead of the inner loop improves to 250 ms, or 246 ms when also omitting the second if.

Using min(counts), max(counts) instead of min(unsorted_list), max(unsorted_list) improves further to 197 ms.

Using chain and repeat from itertools to construct the result takes 182 ms (though repeat does not make much difference).

Code looks like this after the changes:

from collections import defaultdict
from itertools import chain, repeat

def countsort(unsorted_list):
    counts = defaultdict(int)
    for num in unsorted_list:
        counts[num] += 1

    return list(
            chain.from_iterable(
                repeat(num, counts[num])
                for num in xrange(min(counts), max(counts) + 1)))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ collections.Counter was faster than collections.defaultdict on my computer (Jython 2.5). Results may vary. Test your environment and your data to see which one gives better performance. As @Blckknght indicated, the performance difference of defaultdict and Counter is dependent on how repetitious your data is. If few data elements are repeated then there is little/no benefit in building counts. Countsort is only appropriate for highly repetitious data. \$\endgroup\$ – IceArdor Mar 12 '14 at 17:18
3
\$\begingroup\$

min() and max() each has to make a pass through your entire unsorted_list. You might do better by keeping track of your extrema while you build your counts, from a cache locality standpoint.

On the other hand, it's possible that Python's (or NumPy's) min() and max() are highly optimized, in which case you should leave it.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Interesting, use dp to only iterate once for max and min. I'll give it a try. \$\endgroup\$ – sortfiend Aug 29 '13 at 4:50
1
\$\begingroup\$

One way to get a minor speedup is to avoid testing if the value you're adding to the counts dictionary already exists. This code idiom is known as "easier to ask forgiveness than permission" and it is faster because it only does the minimum number of lookups on the dictionary.

def countsort(unsorted_list):
    counts = {}
    for num in unsorted_list:
        try:
            counts[num] += 1
        except KeyError:
            counts[num] = 1

    sorted_list = []
    for num in range(min(unsorted_list), max(unsorted_list) + 1):
        try:
            for j in xrange(counts[num]):
                sorted_list.append(num)
        except KeyError:
            pass

    return sorted_list

I had initially though that a collections.Counter instance would be faster still, but for the data I was testing against it was a bit slower. I think this may be because it uses the equivalent of dict.get to do the incrementing, which is slower if most of the use is for values that already exist (d[x] += 1 is faster than d[x] = d.get(x,0)+1).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ try/except is a good catch. I need to update the original post with what I am using now. I tried to update the second block to a pure list comprehension with a filter, but I'm getting lists of lists even though it is faster. I like your try/except solution for it though, and will give it a whirl. \$\endgroup\$ – sortfiend Aug 29 '13 at 5:27
  • 1
    \$\begingroup\$ How about collections.defaultdict(int)? \$\endgroup\$ – Janne Karila Aug 29 '13 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.