[Python-ideas] Putting `blist` into collections module

[Antoine Pitrou]

On Sun, 21 Sep 2014 15:50:32 +1000
Nick Coghlan <ncoghlan at gmail.com> wrote:
> On 21 September 2014 15:18, David Wilson <dw+python-ideas at hmmz.org> wrote:
> >
> > Even after reviewing the original PEP, the presence of OrderedDict (and
> > particularly under that moniker) feels wrong. Since its addition, in
> > every case I've encountered it in commercial code, the use has been
> > superfluous, diabolically miscomprehended, or used as a hacky stand-in
> > for some cleaner, simpler approach.
> 
> The main intended use case for OrderedDict was preserving insertion
> order, such as when executing code, parsing a JSON file, or
> maintaining an LRU cache.
> 
> For many cases involving a *sorted* key, just sorting when necessary
> is often easier than preserving sort order on every update (not
> necessarily *faster*, but often fast enough that the extra dependency
> isn't justified).

Except when precisely you need to preserve sort order after every
update ;-) Which is at least O(n) using .sort(), but O(log n) using an
appropriate structure.

That said, I agree with your basic point that OrderedDict is quite
useful in itself, and not a poor man's replacement for a binary tree.

(what's more, the O(1) lookup behaviour makes it superior to a tree for
the many cases where lookup performance is dominant)

Regards

Antoine.