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
