Add sorted (ordered) containers
I mean mutable containers that are always sorted when iterating over them. See http://bugs.python.org/issue28433 for example: * SortedSet (sorted unique elements, implemented using (rb?)tree instead of hash) * SortedList (sorted elements, the same as SortedSet, but without uniquiness constraint) - actually a (rb?)tree, not a list (i.e. not an array) * SortedDict (sorted by key when interating) - like C++'s ordered_map There are many implementations in the net, like: https://bitbucket.org/bcsaller/rbtree http://newcenturycomputers.net/projects/rbtree.html https://sourceforge.net/projects/pyavl http://www.grantjenks.com/docs/sortedcontainers https://github.com/tailhook/sortedsets https://pypi.python.org/pypi/skiplist and also in pip: pip3 search sorted | grep -Ei '[^a-z]sorted' I think it should be one standardized implementation of such containers in CPython. For example, C++ has both ordered_map and unorderd_map. Instead of trees, implementation may use SkipList structure, but this is just implementation details. Such structres imply fast insertion and deletion, ability to iterate, and also memory efficiency.
Related: Nick posted an excellent answer to this question here: http://stackoverflow.com/questions/5953205/why-are-there-no-sorted-container... On Thursday, October 13, 2016 at 4:36:39 PM UTC-4, Марк Коренберг wrote:
On 14 October 2016 at 06:48, Neil Girdhar <mistersheik@gmail.com> wrote:
Ah, so this thread is why I've been getting SO notifications for that answer :) While I think that was a decent answer for its time (as standardising things too early can inhibit community experimentation - there was almost 12 years between Twisted's first release in 2002 and asyncio's provisional inclusion in the standard library in Python 3.4), I also think the broader context has changed enough that the question may be worth revisiting for Python 3.7 (in particular, the prospect that it may be possible to provide this efficiently without having to add a large new chunk of C code to maintain). However, given that Grant has already been discussing the possibility directly with Raymond as the collections module maintainer though, there's probably not a lot we can add to that discussion here, since the key trade-off is between: - helping folks that actually need a sorted container implementation find one that works well with typical memory architectures in modern CPUs - avoiding confusing folks that *don't* need a sorted container with yet another group of possible data structures to consider in the standard library *That* part of my original SO answer hasn't changed, it's just not as clearcut a decision from a maintainability perspective when we're talking about efficient and relatively easy to explain pure Python implementations. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
I'm all for adding more featureful data structures. At the risk of confusing Nick's folks, I think it's possible to do even better than Sorted/Ordered for many collections. In my experience, the simple Ordered trait alone was not enough of a feature improvement over the simpler builtin, leading me to implement an OrderedMultiDict, for instance. Another, more cogent example would be Boltons' IndexedSet: http://boltons.readthedocs.io/en/latest/setutils.html It's a normal MutableSet, with almost all the same time complexities, except that you can do indexed_set[0] to get the first-added item, etc. Sometimes it helps to think of it as a kind of UniqueList. If we're going for more featureful containers, I say go all-in! Mahmoud On Fri, Oct 14, 2016 at 8:23 AM, Nick Coghlan <ncoghlan@gmail.com> wrote:
On 13.10.16 23:36, Марк Коренберг wrote:
I recommend to read thorough review articles written by Andrew Barnert: http://stupidpythonideas.blogspot.com/2013/07/sorted-collections-in-stdlib.h... http://stupidpythonideas.blogspot.com/2014/04/sortedcontainers.html
Those are great articles. One thing that Andrew does recommend would be to standardize the interface to the sorted containers, and add them to collections.abc as SortedDict, and SortedSet. I recently switched from blist to sortedcontainers and it would be nice to have these standardized going forward. Another reason to standardize them is for use with the new type checking. Best, Neil On Thursday, October 13, 2016 at 5:54:09 PM UTC-4, Serhiy Storchaka wrote:
Related: Nick posted an excellent answer to this question here: http://stackoverflow.com/questions/5953205/why-are-there-no-sorted-container... On Thursday, October 13, 2016 at 4:36:39 PM UTC-4, Марк Коренберг wrote:
On 14 October 2016 at 06:48, Neil Girdhar <mistersheik@gmail.com> wrote:
Ah, so this thread is why I've been getting SO notifications for that answer :) While I think that was a decent answer for its time (as standardising things too early can inhibit community experimentation - there was almost 12 years between Twisted's first release in 2002 and asyncio's provisional inclusion in the standard library in Python 3.4), I also think the broader context has changed enough that the question may be worth revisiting for Python 3.7 (in particular, the prospect that it may be possible to provide this efficiently without having to add a large new chunk of C code to maintain). However, given that Grant has already been discussing the possibility directly with Raymond as the collections module maintainer though, there's probably not a lot we can add to that discussion here, since the key trade-off is between: - helping folks that actually need a sorted container implementation find one that works well with typical memory architectures in modern CPUs - avoiding confusing folks that *don't* need a sorted container with yet another group of possible data structures to consider in the standard library *That* part of my original SO answer hasn't changed, it's just not as clearcut a decision from a maintainability perspective when we're talking about efficient and relatively easy to explain pure Python implementations. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
I'm all for adding more featureful data structures. At the risk of confusing Nick's folks, I think it's possible to do even better than Sorted/Ordered for many collections. In my experience, the simple Ordered trait alone was not enough of a feature improvement over the simpler builtin, leading me to implement an OrderedMultiDict, for instance. Another, more cogent example would be Boltons' IndexedSet: http://boltons.readthedocs.io/en/latest/setutils.html It's a normal MutableSet, with almost all the same time complexities, except that you can do indexed_set[0] to get the first-added item, etc. Sometimes it helps to think of it as a kind of UniqueList. If we're going for more featureful containers, I say go all-in! Mahmoud On Fri, Oct 14, 2016 at 8:23 AM, Nick Coghlan <ncoghlan@gmail.com> wrote:
On 13.10.16 23:36, Марк Коренберг wrote:
I recommend to read thorough review articles written by Andrew Barnert: http://stupidpythonideas.blogspot.com/2013/07/sorted-collections-in-stdlib.h... http://stupidpythonideas.blogspot.com/2014/04/sortedcontainers.html
Those are great articles. One thing that Andrew does recommend would be to standardize the interface to the sorted containers, and add them to collections.abc as SortedDict, and SortedSet. I recently switched from blist to sortedcontainers and it would be nice to have these standardized going forward. Another reason to standardize them is for use with the new type checking. Best, Neil On Thursday, October 13, 2016 at 5:54:09 PM UTC-4, Serhiy Storchaka wrote:
participants (5)
-
Mahmoud Hashemi -
Neil Girdhar -
Nick Coghlan -
Serhiy Storchaka -
Марк Коренберг