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

Groups > comp.lang.python > #64437

Re: which data structure to use?

Show all headers | View raw

Robert Voigtländer wrote:

> 
>> > >     def pop(self):
>> > >         f, node = heapq.heappop()
>> > >         del lookup[node.pos]
>> > >         return node
> 
>> > That should be
>> 
>> >     def pop(self):
>> 
>> >         f, node = heapq.heappop(self.heap)
>> >         del self.lookup[node.pos]
>> >         return node
>> 
>> Hi Peter,
>> this works great. I will try to find some info about the functionality
>> you used and to understnad what you did. Maybe you can add a function to
>> remove a node? Thanks for your support and all tthe swift answers.
>> 
>> Robert
> 
> Just realized what the pop function is for. I changed it from:
> def pop(self):
> to
> def pop(self,pos):
> 
> and it works.

Unlikely. Are you sure that .heap and .lookup contents are still in sync 
with your modification?

> Now I go on with trying to understand it.

The pop() method as posted can only remove the "lowest" node. If contrary to 
your initial spec

> 2. find the object with the lowest Node.f attribute and update or remove 
it

you want to remove arbitrary nodes a heap may not be the appropriate data 
structure. The modified

import operator

#...

class Nodes():
    def __init__(self):
        self.lookup = {}
    def add(self, node):
        self.lookup[node.pos] = node
    def __iter__(self):
        return iter(self.lookup.itervalues())
    def __contains__(self, pos):
        return pos in self.lookup
    def lowest(self):
        return min(self, key=operator.attrgetter("f"))
    def __delitem__(self, pos):
        del self.lookup[pos]

nodes = Nodes()

nodes.add(Node((1,1), None, 1, 5))
nodes.add(Node((1,2), (1,1), 4, 6))
nodes.add(Node((1,3), (1,2), 9, 10))

del nodes[1, 2]


allows you to delete random nodes, but the lowest() method will slow down as 
it has to iterate over all dict values.

One important caveat: both Nodes classes lead to data corruption if you 
modify a .pos attribute while the node is in a Nodes instance. The same goes 
for the first implementation and the .f attribute.

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