A sorted container in python based on comparisons

Question

Coming from a C++ background I miss a nice sorted container that is only based on comparisons and does not need a hash.

Does anybody know a good implementation of a balanced tree? Or is there an alternative sorted container in the (standard) library that is just as easy to use?

This is my usecase that I try to solve now: A have a file describing a surface with triangles. Each triangle has three nodes, and many nodes will be the same. I need to reconstruct this surface and need to know which nodes are the same. Unfortunately, in the ASCII input, there are sometimes small differences between the printed floats even if they belong to the same node. So I can't use a simple text compare to see if they are equal.

In C++ my solution would be to make a std::map to store the nodes with a 'softcompare' that treats the nodes as equal if the distance between them is small. Then I can just add the nodes while parsing the file and use an index to build the surface.

But in Python I'm struggling to do it equally efficiently in a straightforward way.

Thanks, Luke

Thanks all for your contributions!

To goncalopp: Sort is not a good alternative, because it is O(n log(n)) worst case on each insert. Same goes for bisect. It is good on search, but not on insert. It maintains an unbalanced tree which is O(n) in worst case and then the following insert in list is O(n).

To Aaron: I fully agree with you that the goal is to write elegant code. For me, choosing the right container (data structure) is often the first step to do this. Your solution is O(n) which is even faster then a balanced tree, very nice and I like the trick with the round(). I did not think of that, now I realize it works in python because of infinite precision of int. So I'll go with your construction.

To MrE: Thanks for the link to bintree, it looks like the solution for my question (balanced tree). I found blist before, but that uses an internal dict and hashes for lookup, so that didn't work, but bintree looks a lot better.

you could just `sort` and [`bisect`](http://docs.python.org/2/library/bisect.html) — loopbackbee, Sep 27 '13 at 15:33

score 0 · Answer 1 · answered Sep 27 '13 at 14:33

In C++, everything is about efficiency. In Python, beauty is equally important: Pythonians first try to find an elegant algorithm and in the few cases where it actually is too slow, we invest a few minutes in optimizing a few lines to make it fast enough.

In your case, you need to find points that are close to each other. One approach would be the one your describe. Here is how I would solve this:

Determine how accurate the coordinates need to be. How many of those decimals do you want/need/have to keep? 1, 2?

While reading the input, truncate or round the coordinates to the appropriate number of decimal places, create a tuple key from that. Now you can use the standard Python dictionary:

def round(x):
    return int(round(x*100)) # Keep 2 decimal places, return int for precision (and speed)

filter = {}
filteredPoints = []
for x,y,z in points:
    x,y,z = round(x),round(y),round(z)
    key = (x,y,z)
    index = filter.get(key, None)
    if index is None:
        index = len(filteredPoints)
        filteredPoints.append(key)
        filter[key] = index

Thanks all for your contributions! To goncalopp: – Luke Sep 30 '13 at 09:59 — Luke, Sep 30 '13 at 09:59

A sorted container in python based on comparisons

1 Answers1