Recipe for fast, easy to use, order maintaining dict like structure in Python?

Hey there,

i am wondering if there are any recipes or best practices to create a python class with the following properties:

[ul]
[li]High performance (for currently up to 1000 to 2000 entries. For adding, removing, changing order etc.)
[/li][li]Maintains a given order
[/li][li]Allows for adding items at specified place
[/li][li]Allows for easy re-ordering (move item up/down, move item before or after item, delete item etc.)
[/li][li]Allows for nesting (optionally)
[/li][/ul]

I have been googling and came across things like OrderedDict. That seems to be rather good performance wise, but only maintains the order items are initially added.

Any pointers are more than welcome :slight_smile:

Regards,
Thorsten

This is more of a guess, but it sounds like you could use stacks for this.

I’s kinda of a wild guess but there might be something interesting using a double linked list associated with a dict :


class MyContainer(object):
    # classic double linked list structure
    class DoubleLinkedList(object):
        class LLNode(object):
            def __init__(self):
                self.prev = None
                self.next = None
                self.data = None
            # ...
            
        def __init__(self):
            self.root = None
        # ...        
    
    def __init__(self):
        self.__dict = {}
        self.__dllist = DoubleLinkedList()

    def __setitem__(self, key, value):
        if self.__dict.has_key(key):
            oldNode = self.__dict[key]
            oldNode.data = value
        else:
            self.__dllist.append(value)
            self.__dict[key] = self.__dllist.last()

    def __getitem__(self, key):
        return self.__dict[key].data

    # ...


# Now you can use it this way:

container = MyContainer()
container["first_elem"] = "some_data"
container["second_elem"] = 123.123
container[3.0] = MyContainer()
container[4] = {"dummy" : 1, "no_inspiration" : 2}

container["second_elem"] = 42

container.previousKey("second_elem")    # returns "first_elem"
container.nextKey(3.0)                  # returns 4


The interface needs to be worked a bit, and performance tests have to be done, but it actually tickled my curiosity, so I might dig a bit deeper into it :slight_smile:
Has as I said it’s a quick idea and it might be a really bad one.
Any obvious flaws ?

Interesting approach. It does not satisfy the optional parent/tree requirement, but that is…well…optional for now :wink:

As a bit of background information i am basically going to have layer structure. So i will have Layers (=nodes in the tree) which are a class containing all layer information that are stored in order. Eventually nested layers would be great, but currently not a requirement. So basically this structure would hold the layer data and would be used by GUI tools to display and manipulate the layers.

Regards,
Thorsten

Putting more thoughts to it, it appears that the idea of combining dict with any data structure could work.

The dict part allows you to access directly any data/node/object of your structure (as long as any new element is referenced in your dict). If you know the key of the element you want you don’t need to run a search in your structure.

Starting from Python 2.7 you can used an OrderedDict:
http://docs.python.org/2/library/collections.html#collections.OrderedDict

There are also back-port recipes available on line that you can use with older versions. I’ve recently worked on a project where I extended such a recipe to implement the exact thing you mentioned (insert and movement of object in a particular way)

Unless the ordering is intrinsic to the ordinary application – you need to monitor it in real time for example, or it gets changed at very high frequency – it seems like you could keep the name > content relationships in a standard dictionary and maintain a separate dequefor the ordering. Deque’s are fast and can be extended in either direction.

If the deque contains your dictionary keys, you have random access through the dictionary or ordered acess through the deque. There’s a double lookup there (linear time in both cases) but for 2000 objects I have a hard time believing it would be problematic – you’re not going to be running this in real time, are you?

if your talking about thousands of entries, wouldn’t just going to a database like mysql work?

@Theodox: Well it is going to replace the Max Layersystem because it gets unusable above 500 Layers. So no realtime. Just updating and changing when adding/removing/editing layers etc. Haven’t worked with deques before. I need to look into that. Thanks!

@passerby: See above, mysql seems like an overhead. Thousands of entries should not be a problem to deal with i think.

Regards,
Thorsten

I use odict and json for stuff like this.

Thorsten - I think i recall an earlier thread from you on a similar topic, something about compositing together max scenes from hundreds or thousands of components. It sounds like you might be hitting the outer limits of what Max can really do for you - have you considered an alternate app as the ‘composition’ step and using max only for creating the components?

Well kinda. But currently the whole lighting and shading and rendering pipeline is build around and inside max and vray. So no matter what we do in the long run we need to work around this until then. Hence am evaluating options. Actually Max deals pretty well with a lot of crazy and massive stuff we throw at it. The layersystem is a big exception tho. And well it simply was not designed to handle what we do. So i see no problem writing something that is.

Regards,
Thorsten

In the past I’ve done systems that basically composited max files by combining multiple max files – the big files only existed for non-interactive purposes so the perf didn’t matter :wink:

Last time I looked the real bottlneck in layers was just the UI, which was very slow for big scenes regardless of layer density or not. Maybe you could do a UI in .Net that bypassed the layers dialog but otherwise used vanilla functionality. However that was probably max 2009, so I may be off base here…

We’re not using the layer UI anyways already. We have a custom solution in place already. But it just adds on top of the Max Layersystem. And as hinted in the other thread Layeroperation performance is degrading exponentially with layercount. Without any objects or GUI involved. Hence i am looking into getting rid only of that part and replace it with something light and unobstrusive that allows to keep all needed features. I see quite some bumps on the road ahead (like how to carry along layerdata when merging scenes etc brr) but am hardly left with a choice :confused:

Are you sure this is actually a problem? Have you tried just the easiest thing that comes to mind and see if it’s fast enough?

Well nope, and it turns out it would most likely be. Thanks for the heads up. Seems like a tree vs. forest issue :wink: Seriously then: Back to the drawing board. Try finding the most versatile and future proof version. As this will be cross application most likely it should be able to deal with any thinkable and most unthinkable cases :smiley:

Regards,
Thorsten