Home Original page

[Python-Dev] More compact dictionaries with faster iteration

Terry Reedy tjreedy at udel.edu
Mon Dec 10 21:50:15 CET 2012 
On 12/10/2012 1:38 PM, PJ Eby wrote:
> On Mon, Dec 10, 2012 at 1:01 PM, Armin Rigo <arigo at tunes.org> wrote:
>> On Mon, Dec 10, 2012 at 5:16 PM, PJ Eby <pje at 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
More information about the Python-Dev mailing list