which data structure to use?

[Ben Finney]

Robert Voigtländer <r.voigtlaender at gmail.com> writes:

> which would be the best data structure to use for the following case?

First up, I want to compliment you on asking exactly the right question.
Getting the data structure right or wrong can often shape the solution
dramatically.

> 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 

It's important to note a distinction: The class ‘Node’ doesn't have
attributes ‘pos’, ‘f’, ‘g’, ‘h’, etc. Those attributes are assigned to
each instance when the instance is initialised.

> I need to build a "list" of these objects. The amount is unknown.

Any built-in Python collection type seems good so far.

> 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

So, in neither of those cases is it correct to talk of ‘Node.pos’ or
‘Node.f’, since those are attributes of the class, and the attribute
names don't exist (unless there is other code which you're not showing
us). They'll be attributes of a specific instance of the class in each
case.

> What would be a good approach. Using a list I always need to traverse
> the whole list to do one of the above actions.

If the ‘pos’ attribute is unique for all Node instances – as implied by
your “indentified by” clause above – then you could maintain a mapping
from ‘pos’ values to the Node instances:

    nodes = dict()

    root_node = Node(pos='root', parent=None, g=object(), h=object())
    nodes[root_node.pos] = root_node

    foo_node = Node(pos='foo', parent=root_node, g=object(), h=object())
    nodes[foo_node.pos] = foo_node

As for finding the node with the lowest value of an attribute, I'd
recommend you just use brute force until you get concrete measurements
showing that that specific operation is occupying too much time. Write
the code correct and readable first, before trying to optimise what you
don't need to yet.

-- 
 \           “Value your freedom or you will lose it, teaches history. |
  `\     “Don't bother us with politics,” respond those who don't want |
_o__)                               to learn.” —Richard Stallman, 2002 |
Ben Finney