title: how to optimally count elements in a python list
body: <p>This is almost the same question than <a href="https://stackoverflow.com/questions/3710976/counting-unique-elements-in-a-list"><strong>here</strong></a>, except that I am asking about the most efficient solution for a sorted result.</p>
  
  <p>I have a list (about 10 integers randomly between 0 and 12), for example:</p>
  
  <pre><code>the_list = [5, 7, 6, 5, 5, 4, 4, 7, 5, 4]
  </code></pre>
  
  <p>I want to create a function that returns a list of tuples (item, counts) ordered by the first element, for example</p>
  
  <pre><code>output = [(4, 3), (5, 4), (6, 1), (7, 2)]
  </code></pre>
  
  <p>So far I have used:</p>
  
  <pre><code>def dupli(the_list):
      return [(item, the_list.count(item)) for item in sorted(set(the_list))]
  </code></pre>
  
  <p>But I call this function almost a millon time and I need to make it as fast as I (python) can. Therefore my question: <strong>How to make this function less time comsuming? (what about memory?)</strong></p>
  
  <p>I have played around a bit, but nothing obvious came up:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>Thanks<br>
  Christophe</p>