which data structure to use?

[Oscar Benjamin]

On Tue, Jan 21, 2014 at 05:38:34AM -0800, Robert Voigtländer wrote:
> 
> > On Tue, Jan 21, 2014 at 03:17:43AM -0800, Robert Voigtl�nder wrote:
> > 
> 
> > > 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
> > 
> 
> 
> First thanks to all who responded. Although I only partially understand your answers as I am a Python starter.
> What's clear to me is the difference between object and instance of an object. Just didn't explain it well.  
> 
> Maybe I give some more info on what I need / want to do. I will also provide a working code example. Should have done this before.
> 
> I would very much appreciate a working example of what you mean. Then I have a chance to understand it. :-)
> 
> I would like to implement a class for a A* pathfinding algorithm. (there are ready libraries out there but I would like to learn it myself) This requires to maintain a list of nodes to be processed and nodes already processed. For new nodes I need to check if they are on one of the lists. I also need to regularly pick the node with the lowest value f from the list.
> 
> Here some working code. For one function I sill need a solution. Any better solution is welcome.
> 
> Thanks
> Robert
> 
> ---------------
> class Node:
>     def __init__(self, pos, parent, g , h):
>         self.pos = pos
>         self.parent = parent
>         self.g = g
>         self.h = h
>         self.f = g+h
> 
> 
> def isinlist(nodeToSeatch):
>     for item in openlist:
>         if item.pos == nodeToSeatch: return True
>     return False
> 
> 
> def lowestF():
>     lowestF = ''
>     for item in openlist:
>         if item.f < lowestF: lowestF = item
>     return lowestF

The function above is incorrect. I think it should be:

 def lowestF():
     lowestF = ''
     for item in openlist:
         if item.f < lowestF:
            lowestF = item.f  # Note the .f here
     return lowestF

> 
> def deleteItemWithPos(pos):
>     ## need this function or different approach
>     pass

def deleteItemWithPos(pos):
    for n, item in enumerate(openlist):
        if item.pos == pos:
            del openlist[n]
            return
    else:
        raise RuntimeError('Not in the list!')


> 
> openlist=[]
> openlist.append(Node((1,1),None,1,5))
> openlist.append(Node((1,2),(1,1),4,6))
> openlist.append(Node((1,3),(1,2),9,10))
> 
> for item in openlist: print item.pos, item.f
> 
> print isinlist((1,1))
> print isinlist((1,5))
> 
> nextNode = lowestF()
> print nextNode.pos, nextNode.f

My first suggestion would be to use a dict instead of a list:


class Node:
    def __init__(self, pos, parent, g , h):
        self.pos = pos
        self.parent = parent
        self.g = g
        self.h = h
        self.f = g+h

def isinlist(pos):
    return pos in opendict

def lowestF():
    return min(opendict.values(), key=lambda x: x.f)

def deleteItemWithPos(pos):
    del opendict[pos]

nodes = [
    Node((1,1),None,1,5),
    Node((1,2),(1,1),4,6),
    Node((1,3),(1,2),9,10),
    ]

opendict = {}
for node in nodes:
    opendict[node.pos] = node

for item in opendict.values():
    print item.pos, item.f

print isinlist((1,1))
print isinlist((1,5))

nextNode = lowestF()
print nextNode.pos, nextNode.f


The above is more efficient and simpler. It is still O(N) for the lowestF()
function. Changing data structure could make that more efficient.


Oscar