Why is Collections.counter so slow?

by

It’s not because collections.Counter is slow, it’s actually quite fast, but it’s a general purpose tool, counting characters is just one of many applications.

On the other hand str.count just counts characters in strings and it’s heavily optimized for its one and only task.

That means that str.count can work on the underlying C-char array while it can avoid creating new (or looking up existing) length-1-python-strings during the iteration (which is what for and Counter do).

Just to add some more context to this statement.

A string is stored as C array wrapped as python object. The str.count knows that the string is a contiguous array and thus converts the character you want to co to a C-“character”, then iterates over the array in native C code and checks for equality and finally wraps and returns the number of found occurrences.

On the other hand for and Counter use the python-iteration-protocol. Each character of your string will be wrapped as python-object and then it (hashes and) compares them within python.

So the slowdown is because:

  • Each character has to be converted to a Python object (this is the major reason for the performance loss)
  • The loop is done in Python (not applicable to Counter in python 3.x because it was rewritten in C)
  • Each comparison has to be done in Python (instead of just comparing numbers in C – characters are represented by numbers)
  • The counter needs to hash the values and your loop needs to index your list.

Note the reason for the slowdown is similar to the question about Why are Python’s arrays slow?.

I did some additional benchmarks to find out at which point collections.Counter is to be preferred over str.count. To this end I created random strings containing differing numbers of unique characters and plotted the performance:

from collections import Counter
import random
import string

characters = string.printable  # 100 different printable characters

results_counter = []
results_count = []
nchars = []

for i in range(1, 110, 10):
    chars = characters[:i]
    string = ''.join(random.choice(chars) for _ in range(10000))
    res1 = %timeit -o Counter(string)
    res2 = %timeit -o {char: string.count(char) for char in chars}
    nchars.append(len(chars))
    results_counter.append(res1)
    results_count.append(res2)

and the result was plotted using matplotlib:

import matplotlib.pyplot as plt

plt.figure()

plt.plot(nchars, [i.best * 1000 for i in results_counter], label="Counter",   c="black")
plt.plot(nchars, [i.best * 1000 for i in results_count],   label="str.count", c="red")
plt.xlabel('number of different characters')
plt.ylabel('time to count the chars in a string of length 10000 [ms]')
plt.legend()

Results for Python 3.5

The results for Python 3.6 are very similar so I didn’t list them explicitly.

enter image description here

So if you want to count 80 different characters Counter becomes faster/comparable because it traverses the string only once and not multiple times like str.count. This will be weakly dependent on the length of the string (but testing showed only a very weak difference +/-2%).

Results for Python 2.7

enter image description here

In Python-2.7 collections.Counter was implemented using python (instead of C) and is much slower. The break-even point for str.count and Counter can only be estimated by extrapolation because even with 100 different characters the str.count is still 6 times faster.

More Related Contents:

  1. How to sort Counter by value? – python
  2. Python: is “except KeyError” faster than “if key in dict”?
  3. Fastest way to check if a value exists in a list
  4. Why does concatenation of DataFrames get exponentially slower?
  5. Why does Python code run faster in a function?
  6. Roll rows of a matrix independently
  7. Efficient calculation of Fibonacci series
  8. Bin elements per row – Vectorized 2D Bincount for NumPy
  9. Why is looping over range() in Python faster than using a while loop?
  10. Vectorized searchsorted numpy
  11. Pandas groupby.size vs series.value_counts vs collections.Counter with multiple series
  12. What is the purpose of collections.ChainMap?
  13. Subtracting two lists in Python
  14. Accessing items in an collections.OrderedDict by index
  15. Efficient evaluation of a function at every cell of a NumPy array
  16. Key-ordered dict in Python
  17. Why is `np.sum(range(N))` very slow?
  18. Python defaultdict and lambda
  19. How to count the number of words in a sentence, ignoring numbers, punctuation and whitespace?
  20. Any way to speed up Python and Pygame?
  21. Python collections.Counter: most_common complexity
  22. matplotlib savefig performance, saving multiple pngs within loop
  23. Is there a way to circumvent Python list.append() becoming progressively slower in a loop as the list grows?
  24. Speed up writing to files
  25. Efficiently replace elements in array based on dictionary – NumPy / Python
  26. What are the differences between bool() and operator.truth()?
  27. improving python code in Monte Carlo simulation
  28. differences between “d = dict()” and “d = {}”
  29. Split Python sequence (time series/array) into subsequences with overlap
  30. numpy faster than numba and cython , how to improve numba code

Leave a Comment