[Python-Dev] Proposal: add odict to collections

[Stephen Hansen]

> But my point is that we we need to focus on finding real use cases and
> exploring how best to solve them.  Otherwise we might as well throw in
> my OrderedSet[1] as-is, despite that it's got no comments and no
> ratings.  Even I don't seem to use it.
>

I'm mostly lurking on these threads, so as to be semi-prepared when new
versions come out.. in fifty years, since we *just* migrated from 2.3 to 2.4
on our product, so. :)

Anyways, we've had an OrderedDictionary sort of implementation in our
library for eons. The product is commercial and a mix between a desktop
application and a web one, with an application server and cross-platform
availability... so there's a slightly bizarre and wide range of uses that
we've found for putting ordered dictionaries to. If some various use-cases
and our reasoning helps, here it is. If not, ignore :)

- One is that the system is modular, with various parts able to be activated
or deactivated in configuration. The order of module load is important, as
we've never quite bothered to put in automatic dependency checking -- that's
just overboard for us. Further, the modules can't really be referred to each
other via "import" or in code, but instead need to go through a layer of
indirection through a name-- so-- the system maintains an ordered dict of
modules, a la sys.modules, with the order determining load when it goes
through to initialize itself.

- There's several more places with a similar pattern; a mapping between
"Component Name" and "Module" for generic systems. A processing host which
is meant to be able to load and run any kind of service or task.

- There's several places where a user is configuring a slightly complex set
of actions-- he gives these actions a name, which is shown to the user, and
then we have the configuration options itself we use if that is chosen. Its
just natural/easy to store that in an ordered dict after we pull it out of
the DB, as we want its order to be whatever the user chooses in their setup,
and the key->value association is clear.

- In a modular application with a generic outer interface(meaning the main
app can't even fathom what all it might be asked to load), there's things
like a "Windows" menu item that's easily stored internally as a mapping
between window names and the window object itself, so the menu can be
readily re-generated at will and the window found to switch to.

- In fact, we use a lot of OrderedDictionaries as a part of that UI to
data/configuration mapping, come to think of it. We know the order of
"fields" that someone can search on in the database in advance, and have
them written into the searchUI code as an ordered dict because it just works
nicely. The keys() become a drop-down list, the value a structure
identifying to the central server what field it is they're searching on.

- Fiiinally (sorta), we find passing ordered dictionaries to our Genshi web
templating layer very lovely for making easy-designable web templates for
the web client. We even let customers edit them sometimes!

Basically, after looking at all of these, my impressions of an "ordered
dictionary" for the various use cases we use are:

- The ordered dictionary is used almost exclusively in situations where we
are getting the order implicitly from some other source. Be it a SQL query
(with its own ORDER BY statements), a configuration option, the order of
lines in a file, an auto-sequenced table, or hard-coded data.... Thus, we've
always found "insertion order" to be important.

- Much to my surprise, we actually aren't ever using an ordered dictionary
in a situation where the value ends up being modified after the dictionary
is loaded.

- The only time we use dictionaries where we are updating them after the
fact and their order is -expected- to change is when we are using a *sorted*
dictionary.

- As such, I'd be quite surprised if I was updating the value of an ordered
dictionary and it were to change its order. Meaning:

  >>> d = odict()
  >>> d["hello"] = 1
  >>> d["there"] = 2
  >>> d["hello"] = 3
  >>> d.keys()
  ['hello', 'there']

And not: ['there', 'hello']

An ordered dictionary that does not simply preserve initial insertion order
strikes me as a *sorted* dictionary-- sorting on insertion time. I'd expect
a sorted dictionary to shift itself around as appropriate. I'd not expect an
ordered dictionary to change the order without some explicit action.

To me, "ordered dictionary" is in fact a *preordered* dictionary. The order
is defined before the data in, and the dictionary's job is to just preserve
it.

Anyways. No idea if that'll help the discussion, but a couple people kept
talking about use cases :)

--Stephen
P.S. Our implementation, incidentally, is essentially the same as one
mentioned above though its subclassing from UserDict (historical reasons for
now). We just track the keys in _keys, and if someone's setting something in
the dictionary not in keys, we append. It seemed the most natural/obvious
way to do it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20080615/c6e89f7e/attachment-0001.htm>