Why are tuples immutable?

Antoon Pardon apardon at forel.vub.ac.be
Thu Dec 16 12:03:28 CET 2004


Op 2004-12-16, Max M schreef <maxm at mxm.dk>:
> Antoon Pardon wrote:
>
>> Well IMO there are two sides in this argument. The first is whether
>> or not python allows mutable keys. The second is whether or not
>> limiting keys to immutables in dictionaries provides a performance
>> gain.
>
>
> The problem is that you don't understand what dicts are typically used 
> for. Because of the nonliniarity in dict lookups, dicts are used for 
> optimisation.
>
> I actually think it's the most important tool for optimising Python code.
>
> If dicts allowed mutable keys, a dict would need to run code that 
> corresponds to::
>
> def has_key(key):
>      for key in self.keys():
>          if a_key == key:
>              return True
>      return False

No you just would have to advise the programmer that he shouldn't
mutated objects that are keys in a dictionary, because if he does
things will break.

Just as people shouldn't mutate objects that are in a sorted list
on which one wants to do searches based on the fact that the list
is sorted and just as people shouldn't mutate objects that are
in a heapqueue.

The fact that the elements in certain kind of containers should
be have some kind of invariant is not a good argument to limit
those elements to immutable objects.

And as it turns out to be, python allows mutable objects as
keys just fine.

> Using immutable keys, a code can be generated for the key, that can be 
> efficiently stored in something like a binary tree.

Just as it can with a mutable key, as long as the programmer takes care
not to mutate the objects that are currently used as a key.

> This makes lookup *very much* faster, and is the speed concern that 
> Python programmers care about.
>
> Not the time taken to convert a list into a tuple.

You shouldn't speak for others. Others do have argued about speed loss
because of the need to copy a key before it was entered in a dictionary.

-- 
Antoon Pardon



More information about the Python-list mailing list