Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Mark Lawrence <breamoreboy@yahoo.co.uk>
Subject: blist in standard library  (was Re: Balanced trees)
Date: Sat, 15 Mar 2014 12:31:26 +0000
References: <lennh4$kpm$1@cabale.usenet-fr.net> <CAPTjJmomgZSFj7TanBn8_qXP4ULhCm85abJ5=2PcikXJkrH6GQ@mail.gmail.com> <CAN1F8qU8AJ+Z-Rb4+wGsYWd_bS5aOA3bsjd5NjF46MUvnecSeQ@mail.gmail.com> <mailman.7473.1393598638.18130.python-list@python.org> <XnsA2E95FA1E1EB6duncanbooth@127.0.0.1> <bnvctpF5vanU1@mid.individual.net> <mailman.7920.1394252278.18130.python-list@python.org> <87eh2d3x8h.fsf_-_@elektro.pacujo.net> <CAGGBd_qU3Zp3A4pymnDQfWynWZwFVrdHJpG=U0WZTap4HiymdA@mail.gmail.com> <lffv32$mqo$1@ger.gmane.org> <CAN1F8qU=2K6ysbpnu-JoUtfWfTToRsOaRek0dSQzjPx_sYzPKQ@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; rv:24.0) Gecko/20100101 Thunderbird/24.3.0
In-Reply-To: <CAN1F8qU=2K6ysbpnu-JoUtfWfTToRsOaRek0dSQzjPx_sYzPKQ@mail.gmail.com>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.8155.1394886716.18130.python-list@python.org>
Lines: 98
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:68366

On 15/03/2014 01:13, Joshua Landau wrote:
> On 8 March 2014 20:37, Mark Lawrence <breamoreboy@yahoo.co.uk> wrote:
>> I've found this link useful http://kmike.ru/python-data-structures/
>>
>> I also don't want all sorts of data structures added to the Python library.
>> I believe that there are advantages to leaving specialist data structures on
>> pypi or other sites, plus it means Python in a Nutshell can still fit in
>> your pocket and not a 40 ton articulated lorry, unlike the Java equivalent.
>
> The thing we really need is for the blist containers to become stdlib
> (but not to replace the current list implementation). The rejected PEP
> (http://legacy.python.org/dev/peps/pep-3128/) misses a few important
> points, largely in how the "log(n)" has a really large base:
> random.choice went from 1.2µs to 1.6µs from n=1 to n=10⁸, vs 1.2µs for
> a standard list.
>
> Further, it's worth considering a few advantages:
>
> * copy is O(1), allowing code to avoid mutation by just copying its
> input, which is good practice.
>
> * FIFO is effectively O(1), as the time just about doubles from n=1 to
> n=10⁸ so will never actually branch that much. There is still a speed
> benefit of collections.deque, but it's much, much less significant.
> This is very useful when considering usage as a multi-purpose data
> structure, and removes demand for explicit linked lists (which have
> foolishly been reimplemented loads of times).
>
> * It reduces demand for trees:
>      * There are efficient implementations of sortedlist, sortedset and
> sorteddict.
>      * Slicing, slice assignment and slice deletion are really fast.
>      * Addition of lists is sublinear. Instead of
> "list(itertools.chain(...))", one can add in a loop and end up
> *faster*.
>
> I think blist isn't very popular not because it isn't really good, but
> because it isn't a specialised structure. It is, however, almost there
> for almost every circumstance. This can help keep the standard library
> clean, especially of tree data structures.
>
> Here's what we kill:
>
> * Linked lists and doubly-linked lists, which are scarily popular for
> whatever reason. Sometimes people claim that collections.deque isn't
> powerful enough for whatever they want, and blist will almost
> definitely sate those cases.
>
> * Balanced trees, with blist.sortedlist. This is actually needed right now.
>
> * Poor performance in the cases where a lot of list merging and pruning happens.
>
> * Most uses of bisect.
>
> * Some instances where two data structures are used in parallel in
> order to keep performance fast on disparate operations (like `x in y`
> and `y[i]`).
>
> Now, I understand there are downsides to blist. Particularly, I've
> looked through the "benchmarks" and they seem untruthful. Further,
> we'd need a maintainer. Finally, nobody jumps at blists because
> they're rarely the obvious solution. Rather, they attempt to be a
> different general solution. Hopefully, though, a stdlib inclusion
> could make them a lot more obvious, and support in some current
> libraries could make them feel more at home.
>
> I don't know whether this is a good idea, but I do feel that it is
> more promising and general than having a graph in the standard
> library.
>

I'd raise this on python-dev or python ideas as a result of reading PEP 
3128.  Specifically the second paragraph states Raymond Hettinger's sage 
advice:-

"Depending on its success as a third-party module, it still has a chance 
for inclusion in the collections module. The essential criteria for that 
is whether it is a superior choice for some real-world use cases. I've 
scanned my own code and found no instances where BList would have been 
preferable to a regular list. However, that scan has a selection bias 
because it doesn't reflect what I would have written had BList been 
available. So, 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. After all, its learning curve is 
near zero -- the only cost is the clutter factor stemming from 
indecision about the most appropriate data structure for a given task."

-- 
My fellow Pythonistas, ask not what our language can do for you, ask 
what you can do for our language.

Mark Lawrence

---
This email is free from viruses and malware because avast! Antivirus protection is active.
http://www.avast.com