which data structure to use?

[Oscar Benjamin]

On Tue, Jan 21, 2014 at 03:17:43AM -0800, Robert Voigtländer wrote:
> Hi,
> 
> which would be the best data structure to use for the following case?
> 
> I have objects like this:
> 
> class Node(object): 
>     def __init__(self, pos, parent, g , h): 
>         self.pos = pos 
>         self.parent = parent 
>         self.g = g 
>         self.h = h 
>         self.f = g+h 
> 
> 
> I need to build a "list" of these objects. The amount is unknown.
> On this list I need to regularly
> 
> 1. check if a specific item - identified by Node.pos - is in the list.
> 2. find the object with the lowest Node.f attribute and update or remove it
> 
> 
> What would be a good approach. Using a list I always need to traverse the whole list to do one of the above actions.

Is the order of the items in the list significant?

If not you might try using a modification of this sorted dict recipe:
http://code.activestate.com/recipes/576998-sorted-dictionary/

You would want to use node.pos as the key and node as the value but modify the
_sorted_list so that it sorts keys according to Node.f.

Strictly speaking the sorted dict above has an O(N) overhead for insertion and
removal and O(NlogN) for creation. However these particular big-O's are
handled quite efficiently by the sort(), list.insert() and list.remove()
functions so it depends how big the list is.

If that's not okay then you may want the sorteddict from the blist package on
PyPI:
http://stutzbachenterprises.com/blist/sorteddict.html

That would give you O(logN) insertion/removal. The problem is that the sort
key() function only gets to operate on the dict key not the value so you'd
have to do something pretty funky to make it work. Perhaps:

from blist import sorteddict

def my_sorteddict(*args, **kwargs):
    # There's a good chance this doesn't work...
    def keyfunc(dictkey):
        return d[dictkey].f
    d = sorteddict(keyfunc, *args, **kwargs)
    return d


Oscar