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
mailto:dw%2Bpython-ideas@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@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@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/