[Python-Dev] More compact dictionaries with faster iteration

PJ Eby pje at telecommunity.com
Mon Dec 10 17:16:49 CET 2012


On Mon, Dec 10, 2012 at 10:48 AM, Antoine Pitrou <solipsis at pitrou.net> wrote:
> Le Mon, 10 Dec 2012 10:40:30 +0100,
> Armin Rigo <arigo at tunes.org> a écrit :
>> Hi Raymond,
>>
>> On Mon, Dec 10, 2012 at 2:44 AM, Raymond Hettinger
>> <raymond.hettinger at gmail.com> wrote:
>> > Instead, the data should be organized as follows:
>> >
>> >     indices =  [None, 1, None, None, None, 0, None, 2]
>> >     entries =  [[-9092791511155847987, 'timmy', 'red'],
>> >                 [-8522787127447073495, 'barry', 'green'],
>> >                 [-6480567542315338377, 'guido', 'blue']]
>>
>> As a side note, your suggestion also enables order-preserving
>> dictionaries: iter() would automatically yield items in the order they
>> were inserted, as long as there was no deletion.  People will
>> immediately start relying on this "feature"...  and be confused by the
>> behavior of deletion. :-/
>
> If that's really an issue, we can deliberately scramble the iteration
> order a bit :-) (of course it might negatively impact HW prefetching)

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.


More information about the Python-Dev mailing list