get method

John Machin sjmachin at
Wed Dec 31 01:22:09 CET 2008

On Dec 31, 10:58 am, "James Mills" <prolo... at>
> On Wed, Dec 31, 2008 at 9:15 AM, MRAB <goo... at> wrote:
> (snip)
> > A while back I posted a Python implementation of 'bag' (also called a
> > multiset). The code would then become something like:
> What complexity is this ?

The "armchair philosopher" approach: bag has an iteritems method so
it's probably using a dict internally in which case a reasonable
assumption is that the counting is implemented efficiently ... guess:
bag(iterable) is O(len(iterable))

The "crawl through the shrubbery looking for evidence" approach
stumbles on the actual code:

    def __init__(self, iterable=None):
        self._items = {}
        if iterable is not None:
            for item in iterable:
                self._items[item] = self._items.get(item, 0) + 1

confirming the guess.

More information about the Python-list mailing list