Op 2004-12-21, Jeff Shannon schreef <[EMAIL PROTECTED]>: > Antoon Pardon wrote: > >>Op 2004-12-21, Nick Coghlan schreef <[EMAIL PROTECTED]>: >> >> >>>Antoon Pardon wrote: >>> >>> >>>>Why then doesn't python think the same about sorted lists. When I have a >>>>sorted list and do operations on it that depend on it being sorted, >>>>I can mess things up just as easily by mutating an element in that >>>>sorted list as I can mess things up by mutating a dictionary key. >>>> >>>> >>>Incorrect, and this appears to be the point where our major disagreement >>>lies. >>> >>>Mutate a value in a sorted list and you can fix that easily, just by calling >>>its >>>sort() method again (and, in fact, mutate and resort is a fairly common >>>idiom >>>for small datasets). 'sorted' and 'heapified' are list properties that are >>>easily broken by direct manipulation, but are also easily restored by once >>>again >>>'sorting' or 'heapifying'. >>> >>> >> >>That is an implemantation detail. Likewise a dictionary is probably not >>always in a sane state when a new key is inserted. The fact remains that >>in a sorted list or a heap, mutating an element arbitrarily can mess up >>things greatly. >> >> > > These comparisons to sorted lists and heaps are a red herring. The > analogous situation to those is dictionary *values*, not dictionary keys > -- in essence, the "keys" of a list (whether sorted or not) are integers.
No it is not a red herring. The analogy is not in the fact that sorted lists have keys, but that sorted lists and heapqueues have an invariant just like dictionary keys and that this invariant can be violated by mutating the objects just as the dictionary invariant can be violated by mutating a key. That sorted lists have keys too is just an insignificant coincidense here. >>>Change the hash value of an item used as a key in a dictionary, and *the >>>internal state of the dictionary is likely to broken in a manner you >>>probably >>>cannot fix*. The only reason the 'probably' is there is because you should >>>be >>>able to 'fix it' by changing the hash value back to what it was originally. >>> >>> >> >>I could argue that this is then a failing of dictionary that doesn't >>provide a method to clean up after a key is mutated. >> >> > > So show us a dictionary (i.e. hash table) implementation that can do > this. Why should I, Do you doubt that it is possible? > You'll need to be able to derive the old hash from the new hash, > of course, so that you can correctly associate the values already stored > under that key. And you'll have to be able to do that without referring > to the pre-modified object again, because dicts can't track every Python > operation that might modify a key object. And it needs to deal properly > with equivalent-but-different-ID list literals, because using literals > (and not references stored elsewhere) is an important and common dict > key usage. > > If you can show me how you plan to accomplish this, I'll accept that > you're right on this. Until then... I don't have to accomplish all that in order to be able to clean up a mutated dictionary key. All I need to do is go over the keys, see if they hash to the same bucket as they are in now and otherwise put them in the new bucket. Sure that would be costly, but so would allowing arbitrary mutation in a sorted list and resorting everytime or in a heapqueue and reheapifying. >>>Waitasec - wouldn't it be easier if dictionaries just made it a rule that >>>the >>>hash value wasn't allowed to change? Hang on, that's exactly what they do. >>> >>> >> >>No it is not. >> >> > > Seems to me that the docs are pretty clear on that. It's true that > dictionaries can't enforce that the hash value never change over the > entire life of an object, because dicts can only take enforcement > actions when the dict itself is referenced -- but that's *why* it's > documented. >>And yes I know what to do if I want to use mutable keys as objects. I'm >>just argueing against those who think that should be somehow forbidden. >> >> > > We're not arguing that it should be arbitrarily forbidden. We're > arguing that doing anything else makes it impossible to behave > sensibly. How does having stable keys in a mutable objects makes it impossible to behave sensible for dictionaries? > So prove us wrong, I don't have to prove you wrong. If you want to argue something, you have to provide reasoning that shows you right. > by implementing something that behaves > sensibly in the face of mutating keys (which compare by value, as lists > do, rather than by identity). You are confusing two things with each other. That is 1) a mutable object that is a key and 2) a mutating key. Even if an object is mutable it can be stable for some duration and thus unmutating. There is IMO nothing wrong with using such mutable objects as dictionary keys or in other structures that require an invariant. Requiring that such objects be immutable and thus can't even mutate during periods they are not so used, creates an unnecessary burden. -- Antoon Pardon -- http://mail.python.org/mailman/listinfo/python-list
