[Python-ideas] Make len() usable on a generator

[Skip Montanaro]

On Fri, Oct 3, 2014 at 10:36 AM, Mark Young <marky1991 at gmail.com> wrote:
> Why do you think len is an inherently O(1) operation?

Almost all containers (dicts and sets look a bit different at casual
glance, but are still O(1)) in Snake store their current length as the
ob_size attribute. It's thus O(1) to "calculate" it. You need not
actually count the elements in the container. For example, for lists
(this is from 2.7-ish, so 3.x is perhaps subtly different), omitting
comments:

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

where PyObject_VAR_HEAD is:

#define PyObject_VAR_HEAD               \
    PyObject_HEAD                       \
    Py_ssize_t ob_size;

All len() does is return the ob_size attribute. Again, except for
dicts and sets, which do things slightly differently, but are still
O(1) in this regard.

Skip