Menu
collection.Counter("bcdefffaa")
returns output:
Counter({'f': 3, 'a': 2, 'c': 1, 'b': 1, 'e': 1, 'd': 1})
Since the result is in descended sorted order of values, does this mean the cost of building the Counter is O(nlogn) and not O(n)?
395
As the source code shows, Counter is just a subclass of dict. Constructing it is O(n), because it has to iterate over the input, but operations on individual elements remain O(1).
Counter is an unordered collection where elements are stored as Dict keys and their count as dict value. Counter elements count can be positive, zero or negative integers. However there is no restriction on it's keys and values.
Counter is a subclass of dict that's specially designed for counting hashable objects in Python. It's a dictionary that stores objects as keys and counts as values. To count with Counter , you typically provide a sequence or iterable of hashable objects as an argument to the class's constructor.
According to Python wiki: Time complexity, set is implemented as a hash table. So you can expect to lookup/insert/delete in O(1) average.
As the source code shows, Counter is just a subclass of dict. Constructing it is O(n), because it has to iterate over the input, but operations on individual elements remain O(1).
Note also from that source that it does not keep an order internally, but simply sorts by most common on output, in the __repr__ method.
128
Depends on the implementation, obviously, but the factors that matter are the need to touch each element of the original list, which implies O(n) is a lower bound, and the need to insert elements into a dict and/or update a dict. The display of the elements in the output is not relevant to the cost of building the Counter.
45
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
