[Python-Dev] More compact dictionaries with faster iteration (original) (raw)

Antoine Pitrou solipsis at pitrou.net
Mon Dec 10 17:22:52 CET 2012

Le Mon, 10 Dec 2012 11:16:49 -0500, PJ Eby <pje at telecommunity.com> a écrit :

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.

I suspect that's what Raymond has in mind :-)

Regards

Antoine.

More information about the Python-Dev mailing list