On 12/10/2012 1:38 PM, PJ Eby wrote:
On Mon, Dec 10, 2012 at 1:01 PM, Armin Rigo <ar...@tunes.org> wrote:
On Mon, Dec 10, 2012 at 5:16 PM, PJ Eby <p...@telecommunity.com> wrote:
On the other hand, this would also make a fast ordered dictionary
subclass possible, just by not using the free list for additions,
combined with periodic compaction before adds or after deletes.
Technically, I could see Python switching to ordered dictionaries
everywhere. Raymond's insight suddenly makes it easy for CPython and
PyPy, and at least Jython could use the LinkedHashMap class (although
this would need checking with Jython guys).
What about IronPython?
Also, note that using ordered dictionaries carries a performance cost
for dictionaries whose keys change a lot. This probably wouldn't
affect most dictionaries in most programs, because module and object
dictionaries generally don't delete and re-add a lot of keys very
often. But in cases where a dictionary is used as a queue or stack or
something of that sort, the packing costs could add up. Under the
current scheme, as long as collisions were minimal, the contents
wouldn't be repacked very often.
Without numbers it's hard to say for certain, but the advantage to
keeping ordered dictionaries a distinct type is that the standard
dictionary type can then get that extra bit of speed in exchange for
dropping the ordering requirement.
I think that there should be a separate OrderedDict class (or subclass)
and that the dict docs should warn (if not now) that while iterating a
dict *may*, in some circumstances, give items in insertion *or* sort
order, it *will not* in all cases. Example of the latter:
>>> d = {8:0, 9:0, 15:0, 13:0, 14:0}
>>> for k in d: print(k)
8
9
13
14
15
If one entered the keys in sorted order, as might be natural, one might
mistakenly think that insertion order was being reproduced.
--
Terry Jan Reedy
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
