how to optimally count elements in a python list

Question

This is almost the same question than here, except that I am asking about the most efficient solution for a sorted result.

I have a list (about 10 integers randomly between 0 and 12), for example:

the_list = [5, 7, 6, 5, 5, 4, 4, 7, 5, 4]

I want to create a function that returns a list of tuples (item, counts) ordered by the first element, for example

output = [(4, 3), (5, 4), (6, 1), (7, 2)]

So far I have used:

def dupli(the_list):
    return [(item, the_list.count(item)) for item in sorted(set(the_list))]

But I call this function almost a millon time and I need to make it as fast as I (python) can. Therefore my question: How to make this function less time comsuming? (what about memory?)

I have played around a bit, but nothing obvious came up:

from timeit import Timer as T
number=10000
setup = "the_list=[5, 7, 6, 5, 5, 4, 4, 7, 5, 4]"

stmt = "[(item, the_list.count(item)) for item in sorted(set(the_list))]"
T(stmt=stmt, setup=setup).timeit(number=number)

Out[230]: 0.058799982070922852

stmt = "L = []; \nfor item in sorted(set(the_list)): \n    L.append((item, the_list.count(item)))"
T(stmt=stmt, setup=setup).timeit(number=number)

Out[233]: 0.065041065216064453

stmt = "[(item, the_list.count(item)) for item in set(sorted(the_list))]"
T(stmt=stmt, setup=setup).timeit(number=number)

Out[236]: 0.098351955413818359

Thanks
Christophe

Answer 1

Change where you sort for a savings of about 20%.

Change this:

def dupli(the_list):
    return [(item, the_list.count(item)) for item in sorted(set(the_list))]

To this:

def dupli(the_list):
    count = the_list.count # this optimization added courtesy of Sven's comment
    result = [(item, count(item)) for item in set(the_list)]
    result.sort()
    return result

The reason this is faster is that the sorted iterator must create a temporary list, whereas sorting the result sorts in place.

edit: Here's another approach that is 35% faster than your original:

def dupli(the_list):
    counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    for n in the_list:
        counts[n] += 1
    return [(i, counts[i]) for i in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) if counts[i]]

Note: You may want to randomize the values for the_list. My final version of dupli tests even faster with other random data sets (import random; the_list=[random.randint(0,12) for i in xrange(10)])

Answer 2

I would try:

from collections import defaultdict
output = defaultdict(lambda: 0)
for item in the_list: output[item] += 1
return sorted(output.items())

Answer 3

Taking advantage of the qualification "between 0 and 12":

>>> the_list = [5, 7, 6, 5, 5, 4, 4, 7, 5, 4]
>>> answer1 = [0] * 13
>>> for i in the_list:
...    answer1[i] += 1
...
>>> answer1
[0, 0, 0, 0, 3, 4, 1, 2, 0, 0, 0, 0, 0]
>>> # You might be able to use that as-is:
...
>>> for i, v in enumerate(answer1):
...     if v: print i, v
...
4 3
5 4
6 1
7 2
>>> # Otherwise you can build the list that you specified:
...
>>> answer2 = [(i, v) for i, v in enumerate(answer1) if v]
>>> answer2
[(4, 3), (5, 4), (6, 1), (7, 2)]
>>>

Answer 4

It might be faster to write your own function that counts the numbers in one pass through the list. You're calling the count function for every number in the set, and each of those calls requires a pass through the list.

counts = {}
for n in the_list:
    if n not in counts:
        counts[n] = 0
    counts[n] += 1
sorted(counts.items())

Answer 5

This seems fairly optimal in terms of space and speed:

def dupli2(list_):                                    
    dict_ = {}                                       
    for item in list_:                               
        dict_[item] = dict_.get(item, 0) + 1         
    return sorted(dict_.items())                    

Or this:

def dupli3(list_):                                            
    last = None                                               
    list_ = sorted(list_)                                     

    i = 0                                                     
    for item in list_:                                        
        if item != last and last is not None:                 
            yield last, i                                     
            i = 0                                             
        i += 1                                                
        last = item                                           

    yield last, i 

Not sure about the speed though. For that I'd recommend that you either do it in C or use Psyco ;)

With Psyco:

In [33]: %timeit list(dupli3(test.the_list))
100000 loops, best of 3: 6.46 us per loop

In [34]: %timeit list(dupli2(test.the_list))
100000 loops, best of 3: 2.37 us per loop

In [35]: %timeit list(dupli(test.the_list))
100000 loops, best of 3: 2.7 us per loop

Answer 6

itertools.groupby is perfect for this:

>>> from itertools import groupby
>>> the_list = [5, 7, 6, 5, 5, 4, 4, 7, 5, 4]
>>> gb = groupby(sorted(the_list))
>>> print [(i,len(list(j))) for i,j in gb]
[(4, 3), (5, 4), (6, 1), (7, 2)]