Are lists at least as efficient as dictionaries?

Peter Otten __peter__ at web.de
Fri Aug 29 10:07:20 CEST 2003


Narendra C. Tulpule wrote:

> If I have a list with 100 elements, each element being a long string,
> is it more efficient to maintain it as a dictionary (with a key = a
> string from the list and value = None) for the purpose of insertion
> and removal?

Wild guess: I suppose that both implementations will not significantly
affect the overall speed of your application, e.g. if the strings are
*really* large (as opposed to the list of *only* 100 elements), reading
from disk will take much longer than inserting into the list, even at
arbitrary positions.

Also, note that no particular order is preserved for the keys in a
dictionary.

And now for something completely different:

>>>> x = ([],)
>>>> x[0] += ['something']
> Traceback (most recent call last):
>   File "<stdin>", line 1, in ?
> TypeError: object doesn't support item assignment

+= calls the list.__iadd__(self, other) method, which seems to be
implemented as

def __iadd__(self, other):
    self.append(other)
    return self 

The call of this method succeds, but the following assignment fails, because
tuples are immutable. This could only be remedied if all assignments

a = a

were silently ignored, or, if the += operator would not perform an
assignment, which has the disadvantage that it would no longer work for
immutables, so that
>>> i = 1
>>> i += 1
>>> print i
1 # admittedly faked
>>>

You could change __iadd__() to

def __iadd__(self, other):
    return self + other

but then sane behaviour in one special case comes at the cost of always
creating a copy of a potentially large (say more than 100 items :-) list.

By the way, one topic per post is always a good idea :-)

Peter




More information about the Python-list mailing list