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. -- https://mail.python.org/mailman/listinfo/python-list
