how to optimally count elements in a python list
Question: This is almost the same question than
[**here**](http://stackoverflow.com/questions/3710976/counting-unique-
elements-in-a-list), 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: I would try:

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

