Hacker News Reader

Comment by vikinghckr | Hacker News Reader

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

View on HN

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.

Problem with bisect is that bisect.insort() insertion is O(n), whereas C++ set.insert() is O(log n).

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.or...

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....

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

> Binary search runs in logarithmic time in the worst case, making O(log n) comparisons...

~ https://en.wikipedia.org/wiki/Binary_search_algorithm

edit: Unless you mean moving the data?

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.

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.

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.

Could you please explain in some more detail how that would work, and especially how (logical) timestamp of insertion would help at all?

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.

Correct me, if I am wrong: take everything you described and remove the (logical) timestamp, and all you'd be losing out on would be the iteration in insertion order?

So how does the timestamp have any impact on persistence?

(We agree on basically everything you write.)

> [1]: And you can use an increment-only mutation counter instead of a timestamp to make this pure.

Agreed. That's what I'd call a logical timestamp or a logical clock.

> 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.

That still doesn't tell you anything at all about how you make the hashtable itself persistent.

One simple way would be to just introduce an arbitrary order on your hashes, eg compare them as if they were ints, and then stick them in an ordered map container. Of course, that's just a round-about way to impose an arbitrary order on your keys. Works perfectly well, it's just not too interesting.

To come back to your original question:

> 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.

In the cases we talked about making the keys comparable is only a means to an end, and any arbitrary order will do. That's the most common use case. Iterating over the keys in insertion order is also often useful.

In practice, I did come across some use cases that make genuine use of the order of keys. Eg when I was interested in (automatically) keeping track of the highest or lowest key or quantiles.

You can use a sorted map as a priority queue easily. A min heap would give you O(1) access to the minimum item, but if you actually want to pop it, it's O(log n) anyway. A sorted map as tree gives you O(log n) for basically all operations. For most uses that's either good enough, or doesn't even make a difference at all compared to a heap. Using your sorted map as a priority queue gives you arbitrary priority updates in O(log n) for no extra implementation complexity.

Sorted maps also came in handy when I was implementing geometric algorithms where I wanted to sweep a scanline over points. Or for divide and conquer algorithms over space.

A sorted map is also useful as a basic datastructure to build step functions on top of. (https://en.wikipedia.org/wiki/Step_function) A simple application is solving the infamous skyline problem.

When you want to store your data structure, having similar keys close together can help with compression. Google uses sorted string tables (sstable) show that principle quite well.

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...

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).

Reply on news.ycombinator.com