5 ms·

Disappointing that Python sill has no support for a sorted container in its standard library, akin to C++ `set` or `map` classes.

craftyguy 7y ago
But it does have a method to sort containers in its standard library, `sorted`, that C++ doesn't have. And it's trivial to use it to sort lists, sets, and dicts...
- vikinghckr 7y ago
  C++ also has the `sort()` function that allows you to sort any unsorted container. But that's not a replacement for a sorted container like `set` or `map` though. Because `set` or `map` allows you to insert elements at O(log n) runtime. If you have to sort every time you insert using the `sort()` or `sorted()` functions, the run time becomes O(n log n).
carapace 7y ago
https://docs.python.org/3.0/library/bisect.html https://docs.python.org/3.0/library/bisect.html > This module provides support for maintaining a list in sorted order without having to sort the list after each insertion.
- vikinghckr 7y ago
  Problem with bisect is that bisect.insort() insertion is O(n), whereas C++ set.insert() is O(log n).
  - stfwn 7y ago
    It is somewhat strange that Python does not have a binary tree in the standard library. I also couldn't find any discussion on the topic either. It might be a nice contribution. Edit: it was coined a few times on the python-ideas mailing list but it seems it just died a silent death there. https://mail.python.org/archives/list/python-ideas@python.org/message/3XA5XVGOPQNOVP6PRODTARAFPFXWG3PX/ https://mail.python.org/archives/list/python-ideas@python.or...
    - carapace 7y ago
      I suspect it's because you rarely need them in Python because the existing built-ins (list, tuple, dict, set) usually work well enough for a given job, or you're already using e.g. Pandas or something. FWIW: https://github.com/calroc/xerblin/blob/master/xerblin/btree.py https://github.com/calroc/xerblin/blob/master/xerblin/btree....
  - carapace 7y ago
    With respect, I think you're worng about that. > The module [bisect] ... uses a basic bisection algorithm to do its work. ~ https://docs.python.org/3.0/library/bisect.html https://docs.python.org/3.0/library/bisect.html > Binary search runs in logarithmic time in the worst case, making O(log n) comparisons... ~ https://en.wikipedia.org/wiki/Binary_search_algorithm https://en.wikipedia.org/wiki/Binary_search_algorithm edit: Unless you mean moving the data?
joshuamorton 7y ago
What's the value of a sorted map over an ordered map? I don't think I've ever cared to iterate over map values based on the alphanumeric ordering of their keys.
- eru 7y ago
  In Haskell we use sorted maps as persistent data structures. Persistent in this context means that the insert-method returns a new map and the old map is still around, if you need it. It's basically copy-on-write. The old and new map share all but O(log n) data. You could probably do something like that with an unsorted map, but it's a good fit for a sorted one.
  - joshuamorton 7y ago
    Sure, but fix your comparison metric as "timestamp of insertion" (and forget for a moment that this isn't technically pure, you can fiddle to make it pure), and you still get all the CoW-niceness, but this is internal to the mapping type, my keys and values don't need to be comparable or orderable, only hashable. I'm given an ordering, the ordering is arbitrary, but I don't care, because CoW/persistent hash maps are mostly an implementation detail or optimization.
    - eru 7y ago
      Could you please explain in some more detail how that would work, and especially how (logical) timestamp of insertion would help at all?
      - joshuamorton 7y ago
        So on eway to think of a hash table/map is a set of tuples of <key, value>. Imagine we extend that to <insertion timestamp, key, value>. All of your conventional mapping methods (get/has/put) work on the key and value and ignore the timestamp. But anything that relies on iteration takes advantage of the timestamp[1], and iterates in timestamp order (or, in fact how this is normally done, is that you have a sparse array/map of <key, pointer> and a dense array of <timestamp, value>. Whenever you insert a new key/value, you always append value to the end of the dense array (so that array is dense), and the key is hashed as normal, but the value in the hash table is a pointer into the dense array where the timestamp/value pair is stored. So internally, get is return (map[hash(key) % map_size])->value or approximately that (I haven't written C in a while). Then iteration over objects in the array is consistent: you just iterate over the dense array. Removal from the dense array is done by tombstoning, and possibly eventual compaction. This is essentially how python's current hash table implementation works. IIRC, if you're table can assume only insertions, this actually becomes really, really nice as a persistent data structure, since you can replace the backing vector with a backing linked list, and you only really lose out on iteration speed. Then you further extend that by swapping the linked list to a tree, and you share the entire backing structure. [1]: And you can use an increment-only mutation counter instead of a timestamp to make this pure.

craftyguy 7y ago

But it does have a method to sort containers in its standard library, `sorted`, that C++ doesn't have. And it's trivial to use it to sort lists, sets, and dicts...

vikinghckr 7y ago
C++ also has the `sort()` function that allows you to sort any unsorted container. But that's not a replacement for a sorted container like `set` or `map` though. Because `set` or `map` allows you to insert elements at O(log n) runtime. If you have to sort every time you insert using the `sort()` or `sorted()` functions, the run time becomes O(n log n).

carapace 7y ago

https://docs.python.org/3.0/library/bisect.html https://docs.python.org/3.0/library/bisect.html > This module provides support for maintaining a list in sorted order without having to sort the list after each insertion.

vikinghckr 7y ago
Problem with bisect is that bisect.insort() insertion is O(n), whereas C++ set.insert() is O(log n).
- stfwn 7y ago
  It is somewhat strange that Python does not have a binary tree in the standard library. I also couldn't find any discussion on the topic either. It might be a nice contribution. Edit: it was coined a few times on the python-ideas mailing list but it seems it just died a silent death there. https://mail.python.org/archives/list/python-ideas@python.org/message/3XA5XVGOPQNOVP6PRODTARAFPFXWG3PX/ https://mail.python.org/archives/list/python-ideas@python.or...
  - carapace 7y ago
    I suspect it's because you rarely need them in Python because the existing built-ins (list, tuple, dict, set) usually work well enough for a given job, or you're already using e.g. Pandas or something. FWIW: https://github.com/calroc/xerblin/blob/master/xerblin/btree.py https://github.com/calroc/xerblin/blob/master/xerblin/btree....
- carapace 7y ago
  With respect, I think you're worng about that. > The module [bisect] ... uses a basic bisection algorithm to do its work. ~ https://docs.python.org/3.0/library/bisect.html https://docs.python.org/3.0/library/bisect.html > Binary search runs in logarithmic time in the worst case, making O(log n) comparisons... ~ https://en.wikipedia.org/wiki/Binary_search_algorithm https://en.wikipedia.org/wiki/Binary_search_algorithm edit: Unless you mean moving the data?

joshuamorton 7y ago

What's the value of a sorted map over an ordered map? I don't think I've ever cared to iterate over map values based on the alphanumeric ordering of their keys.

eru 7y ago
In Haskell we use sorted maps as persistent data structures. Persistent in this context means that the insert-method returns a new map and the old map is still around, if you need it. It's basically copy-on-write. The old and new map share all but O(log n) data. You could probably do something like that with an unsorted map, but it's a good fit for a sorted one.
- joshuamorton 7y ago
  Sure, but fix your comparison metric as "timestamp of insertion" (and forget for a moment that this isn't technically pure, you can fiddle to make it pure), and you still get all the CoW-niceness, but this is internal to the mapping type, my keys and values don't need to be comparable or orderable, only hashable. I'm given an ordering, the ordering is arbitrary, but I don't care, because CoW/persistent hash maps are mostly an implementation detail or optimization.
  - eru 7y ago
    Could you please explain in some more detail how that would work, and especially how (logical) timestamp of insertion would help at all?
    - joshuamorton 7y ago
      So on eway to think of a hash table/map is a set of tuples of <key, value>. Imagine we extend that to <insertion timestamp, key, value>. All of your conventional mapping methods (get/has/put) work on the key and value and ignore the timestamp. But anything that relies on iteration takes advantage of the timestamp[1], and iterates in timestamp order (or, in fact how this is normally done, is that you have a sparse array/map of <key, pointer> and a dense array of <timestamp, value>. Whenever you insert a new key/value, you always append value to the end of the dense array (so that array is dense), and the key is hashed as normal, but the value in the hash table is a pointer into the dense array where the timestamp/value pair is stored. So internally, get is return (map[hash(key) % map_size])->value or approximately that (I haven't written C in a while). Then iteration over objects in the array is consistent: you just iterate over the dense array. Removal from the dense array is done by tombstoning, and possibly eventual compaction. This is essentially how python's current hash table implementation works. IIRC, if you're table can assume only insertions, this actually becomes really, really nice as a persistent data structure, since you can replace the backing vector with a backing linked list, and you only really lose out on iteration speed. Then you further extend that by swapping the linked list to a tree, and you share the entire backing structure. [1]: And you can use an increment-only mutation counter instead of a timestamp to make this pure.