On Dec 31, 10:58 am, "James Mills" <prolo...@shortcircuit.net.au> wrote: > On Wed, Dec 31, 2008 at 9:15 AM, MRAB <goo...@mrabarnett.plus.com> 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. -- http://mail.python.org/mailman/listinfo/python-list