Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #64403

Re: which data structure to use?

Show all headers | View raw

Robert Voigtländer <r.voigtlaender@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 03:17 -0800
  Re: which data structure to use? Chris Angelico <rosuav@gmail.com> - 2014-01-21 22:27 +1100
  Re: which data structure to use? Ben Finney <ben+python@benfinney.id.au> - 2014-01-21 22:34 +1100
  Re: which data structure to use? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-01-21 11:49 +0000
    Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 05:38 -0800
      Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 05:43 -0800
        Re: which data structure to use? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-01-21 18:03 +0000
      Re: which data structure to use? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-01-21 13:59 +0000
      Re: which data structure to use? Peter Otten <__peter__@web.de> - 2014-01-21 15:09 +0100
      Re: which data structure to use? Peter Otten <__peter__@web.de> - 2014-01-21 15:19 +0100
        Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 07:33 -0800
          Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-21 07:37 -0800
            Re: which data structure to use? Peter Otten <__peter__@web.de> - 2014-01-21 19:39 +0100
              Re: which data structure to use? Robert Voigtländer <r.voigtlaender@gmail.com> - 2014-01-22 01:38 -0800

csiph-web