On 15/03/2014 01:13, Joshua Landau wrote:
On 8 March 2014 20:37, Mark Lawrence <breamore...@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
--
https://mail.python.org/mailman/listinfo/python-list
