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

[Stefan Drees]

On 2014-09-21 07:36 +02:00, Guido van Rossum wrote:
> So write a PEP for sorted dict and tree.

but let us all read it - and the implementation samples - exactly before 
even thinking about rejecing it ;-) as in the rejected PEP3128 I read 
(in the fifth paragraph of
http://legacy.python.org/dev/peps/pep-3128/#use-case-trade-offs not 
counting the list):

"""
The performance for the LIFO use case could be improved to O(n) time, by 
caching a pointer to the right-most leaf within the root node. For lists 
that do not change size, the common case of sequential access could also 
be improved to O(n) time via caching in the root node. [...]
"""

which - not really being in the topic - I would rather expect to read:
"""
The performance for the LIFO use case could be improved to O(1) time, by 
caching a pointer to the right-most leaf within the root node. For lists 
that do not change size, the common case of sequential access could also 
be improved to O(1) time via caching in the root node. [...]
"""

At least this is what I would consider an enhancement over O(log n) and 
also expect from a single cached pointer implementation and the like.

All the best,
Stefan.

> I rarely seem to need ordereddict myself, but it makes a clean LRU cache.
>
> On Saturday, September 20, 2014, David Wilson <dw+python-ideas at hmmz.org
> <mailto:dw%2Bpython-ideas at hmmz.org>> wrote:
>
>     On Sun, Sep 21, 2014 at 02:37:39PM +1000, Steven D'Aprano wrote:
>
>      > > In 2007, this PEP was created that suggested integrating Daniel
>     Stutzbach's
>      > > blist into Python: http://legacy.python.org/dev/peps/pep-3128/
>      > >
>      > > The PEP was rejected, but Raymond Hettinger made a note that
>     "after a few
>      > > months, I intend to poll comp.lang.python for BList success
>     stories. If
>      > > they exist, then I have no problem with inclusion in the
>     collections
>      > > module."
>      >
>      > I have not used blist, but I have no objection to it becoming a
>      > collections type if the author agrees.
>
>     It seems unsettling that we'd consider adding another special use
>     collection to the stdlib, when more widely applicable generalizations of
>     it are missing. In blist's case, it can (mostly) be trivially
>     reimplemented using an ordered map, which the standard library lacks.
>     The remainder of blist (IIRC) are some fancy slicing and merging methods
>     that exploit the underlying structure.
>
>     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.
>
>     Coming from this perspective, I'd prefer that further additions were
>     limited to clean and far better understood structures. In this light,
>     could we perhaps instead discuss the merits of a collections.Tree,
>     collections.SortedDict or similar?
>
>
>      > which makes blist an optimization, if and when it is available.
>
>     blist has functionality that would require significant boilerplate to
>     replicate in normal code, so it's definitely not just useful as an
>     optimization.
>
>
>     David
>     _______________________________________________
>     Python-ideas mailing list
>     Python-ideas at python.org <javascript:;>
>     https://mail.python.org/mailman/listinfo/python-ideas
>     Code of Conduct: http://python.org/psf/codeofconduct/
>
>
>
> --
> --Guido van Rossum (on iPad)
>
>
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>