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

Groups > comp.lang.python > #64405

Re: which data structure to use?

Show key headers only | View raw

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

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