O(n^2) is bad - can it be fixed?

[Alex Martelli]

"Roy Smith" <roy at panix.com> wrote in message
news:roy-916424.08545222052001 at news1.panix.com...
    ...
> How does python deal with sparse lists,

By raising exceptions, at least in your example.

> i.e. what if I did this:
>
> list = []
> list[9001] = 'foo'

This raises an IndexError.  Python lists never
automatically "grow" when an assignment statement
attempts to bind an item at an invalid index --
rather, they raise IndexError.  To "grow" a list,
you may assign appropriately to a SLICE of it,
but that can never cause "sparsity" either.  Or
you can call .append or .extend on the list, but,
again, no 'sparsity' can thereby be caused.

The normal way to say "add 9001 items with value
None to my list" is
    mylist.extend(9001*[None])
and this, too, can never cause "sparsity".

To say "extend my list to 9001 items long no
matter how long it is now":
    mylist.extend((9001-len(mylist))*[None])

Note that, if len(mylist)>=9001 when you do
this, no problem -- N*[None] produces the
empty list if N<=0, so everything works out
fine - mylist.extend([]) is a quiet no-op:-).


Assigning to a *dictionary* item with a key (index)
that is not yet present does 'grow' the dictionary,
but by one item only -- again, no 'sparsity' issue
can possibly arise.

If you do need to handle "sparse lists" a lot
in your applications, you'll probably want to
wrap the "sparse list" implementation into a
class.  One might start from UserList, but I
suspect that little of its implementation would
in fact be reusable -- it's likely that the
best underlying implementation data structure
is a dictionary plus perhaps some auxiliary
information to allow faster computation of,
e.g., __length__.


Alex