> I'm curious as to the implementation (I'd be happy to dig through the > source, just don't have the time right now). I've seen various > implementations across interpreters in the past (some which have been > rather shocking) and I'd like to get some insight into Python (well, > CPython at this point anyway). > > When len() is called passing an immutable built-in type (such as a > string), I'd assume that the overhead in doing so is simply a function > call and there are no on-call calculations done. Is that correct? > > I'd also assume that mutable built-in types (such as a bytearray) would > cache their size internally as a side effect of mutation operations. Is > that correct? If so, is it safe to assume that at least all built-in > types observe this behavior, or are there some that incur an O(n) cost > on every len() call?
It appears that list has len() complexity of O(1) source: http://wiki.python.org/moin/TimeComplexity It may be worth mentioning that lists in Python are implemented using arrays instead of linked lists. It's reasonable to assume that other built-in collection types would be similar, though I don't see anything explicitly saying so for bytearray. -Nick Cash -- http://mail.python.org/mailman/listinfo/python-list
