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

Groups > comp.lang.python > #60928 > unrolled thread

extracting a heapq in a for loop - there must be more elegant solution

Back to article view | Back to comp.lang.python

Contents

  extracting a heapq in a for loop - there must be  more elegant solution Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-12-03 12:18 +0000
    Re: extracting a heapq in a for loop - there must be more elegant solution Peter Otten <__peter__@web.de> - 2013-12-03 13:38 +0100
      Re: extracting a heapq in a for loop - there must be more elegant solution Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-12-04 09:36 +0000
        Re: extracting a heapq in a for loop - there must be more elegant solution Peter Otten <__peter__@web.de> - 2013-12-04 10:50 +0100
    Re: extracting a heapq in a for loop - there must be  more elegant solution rusi <rustompmody@gmail.com> - 2013-12-03 04:40 -0800
      Re: extracting a heapq in a for loop - there must be  more elegant solution Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-12-04 09:37 +0000
    Re: extracting a heapq in a for loop - there must be  more elegant solution Duncan Booth <duncan.booth@invalid.invalid> - 2013-12-03 13:06 +0000
      Re: extracting a heapq in a for loop - there must be  more elegant solution Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-12-04 09:39 +0000
    Re: extracting a heapq in a for loop - there must be  more elegant solution Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-12-03 15:56 +0200
      Re: extracting a heapq in a for loop - there must be  more elegant solution Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-12-04 09:41 +0000
    Re: extracting a heapq in a for loop - there must be  more elegant solution Cameron Simpson <cs@zip.com.au> - 2013-12-04 08:13 +1100
      Re: extracting a heapq in a for loop - there must be  more elegant solution Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-12-04 09:44 +0000
        Re: extracting a heapq in a for loop - there must be  more elegant solution Cameron Simpson <cs@zip.com.au> - 2013-12-05 13:29 +1100
    Re: extracting a heapq in a for loop - there must be more elegant solution Ian Kelly <ian.g.kelly@gmail.com> - 2013-12-03 14:43 -0700
    Re: extracting a heapq in a for loop - there must be more elegant solution Ned Batchelder <ned@nedbatchelder.com> - 2013-12-03 17:32 -0500

#60928 — extracting a heapq in a for loop - there must be more elegant solution

Hi,

I'd like to extracted elements from a heapq in a for loop.
I feel my solution below is much too complicated.
How to do it more elegantly? 
I know I could use a while loop but I don't like it.

Many thanks for some lessons in Python.

Here is my clumsy solution

from heapq import heappush, heappop
# heappop raises IndexError if heap is empty

H=[]
for N in 'H','C','W','I' :
  heappush(H,N)

# how to avoid / simplify the following function

def in_sequence(H) :
  try :
    while True :
      N= heappop(H)
      yield N
  except IndexError :
    raise StopIteration

# and here the application:

for N in in_sequence(H) :
  print(N)

[toc] | [next] | [standalone]

#60930 — Re: extracting a heapq in a for loop - there must be more elegant solution

Helmut Jarausch wrote:

> Hi,
> 
> I'd like to extracted elements from a heapq in a for loop.
> I feel my solution below is much too complicated.
> How to do it more elegantly?
> I know I could use a while loop but I don't like it.
> 
> Many thanks for some lessons in Python.
> 
> Here is my clumsy solution
> 
> from heapq import heappush, heappop
> # heappop raises IndexError if heap is empty
> 
> H=[]
> for N in 'H','C','W','I' :
>   heappush(H,N)

H = ["H", "C", "W", "I"]
heapq.heapify(H)

But see below.

> # how to avoid / simplify the following function
> 
> def in_sequence(H) :
>   try :
>     while True :
>       N= heappop(H)
>       yield N
>   except IndexError :
>     raise StopIteration
> 
> # and here the application:
> 
> for N in in_sequence(H) :
>   print(N)

If you are iterating over the complete heap I see no advantage over a sorted 
list. So

for N in sorted(H):
    print(N)

If H is huge use H.sort() instead of sorted() to save memory.
If you need only a few items use heapq.nsmallest().

[toc] | [prev] | [next] | [standalone]

#60996 — Re: extracting a heapq in a for loop - there must be more elegant solution

On Tue, 03 Dec 2013 13:38:58 +0100, Peter Otten wrote:

> Helmut Jarausch wrote:
> 
>> Hi,
>> 
>> I'd like to extracted elements from a heapq in a for loop.
>> I feel my solution below is much too complicated.
>> How to do it more elegantly?
>> I know I could use a while loop but I don't like it.
>> 
>> Many thanks for some lessons in Python.
>> 
>> Here is my clumsy solution
>> 
>> from heapq import heappush, heappop
>> # heappop raises IndexError if heap is empty
>> 
>> H=[]
>> for N in 'H','C','W','I' :
>>   heappush(H,N)
> 
> H = ["H", "C", "W", "I"]
> heapq.heapify(H)
> 
> But see below.
> 
>> # how to avoid / simplify the following function
>> 
>> def in_sequence(H) :
>>   try :
>>     while True :
>>       N= heappop(H)
>>       yield N
>>   except IndexError :
>>     raise StopIteration
>> 
>> # and here the application:
>> 
>> for N in in_sequence(H) :
>>   print(N)
> 
> If you are iterating over the complete heap I see no advantage over a sorted 
> list. So
> 
> for N in sorted(H):
>     print(N)
> 
> If H is huge use H.sort() instead of sorted() to save memory.
> If you need only a few items use heapq.nsmallest().


Many thanks!
In my real application the data which is pushed onto the heap will be extracted from a small file
which is executed several thousands times. So, I thought, I could keep the CPU a bit busy while
the OS is doing file I/O. Of course, I could have appended all these strings to a list which is
sorted at the end.

[toc] | [prev] | [next] | [standalone]

#61002 — Re: extracting a heapq in a for loop - there must be more elegant solution

Helmut Jarausch wrote:

> On Tue, 03 Dec 2013 13:38:58 +0100, Peter Otten wrote:
> 
>> Helmut Jarausch wrote:
>> 
>>> Hi,
>>> 
>>> I'd like to extracted elements from a heapq in a for loop.
>>> I feel my solution below is much too complicated.
>>> How to do it more elegantly?
>>> I know I could use a while loop but I don't like it.
>>> 
>>> Many thanks for some lessons in Python.
>>> 
>>> Here is my clumsy solution
>>> 
>>> from heapq import heappush, heappop
>>> # heappop raises IndexError if heap is empty
>>> 
>>> H=[]
>>> for N in 'H','C','W','I' :
>>>   heappush(H,N)
>> 
>> H = ["H", "C", "W", "I"]
>> heapq.heapify(H)
>> 
>> But see below.
>> 
>>> # how to avoid / simplify the following function
>>> 
>>> def in_sequence(H) :
>>>   try :
>>>     while True :
>>>       N= heappop(H)
>>>       yield N
>>>   except IndexError :
>>>     raise StopIteration
>>> 
>>> # and here the application:
>>> 
>>> for N in in_sequence(H) :
>>>   print(N)
>> 
>> If you are iterating over the complete heap I see no advantage over a
>> sorted list. So
>> 
>> for N in sorted(H):
>>     print(N)
>> 
>> If H is huge use H.sort() instead of sorted() to save memory.
>> If you need only a few items use heapq.nsmallest().
> 
> 
> Many thanks!
> In my real application the data which is pushed onto the heap will be
> extracted from a small file which is executed several thousands times. So,
> I thought, I could keep the CPU a bit busy while the OS is doing file I/O.
> Of course, I could have appended all these strings to a list which is
> sorted at the end.

In that case have a look at bisect.insort() which adds an item to a list 
while keeping it sorted.

[toc] | [prev] | [next] | [standalone]

#60931

On Tuesday, December 3, 2013 5:48:59 PM UTC+5:30, Helmut Jarausch wrote:
> Hi,
>
> I'd like to extracted elements from a heapq in a for loop.
> I feel my solution below is much too complicated.
> How to do it more elegantly? 
> I know I could use a while loop but I don't like it.

How about

def in_sequence(h):
  for i in range(len(h)):
    yield heapq.heappop(h)

Yeah its a bit fiddly:
1. i needed for for but not used
2. The range in the for loop -- normally a python 'smell'

If python3

def ins3(h):
   yield from (heapq.heappop(h) for i in range(len(h)))

[toc] | [prev] | [next] | [standalone]

#60997

On Tue, 03 Dec 2013 04:40:26 -0800, rusi wrote:

> On Tuesday, December 3, 2013 5:48:59 PM UTC+5:30, Helmut Jarausch wrote:
>> Hi,
>>
>> I'd like to extracted elements from a heapq in a for loop.
>> I feel my solution below is much too complicated.
>> How to do it more elegantly? 
>> I know I could use a while loop but I don't like it.
> 
> How about
> 
> def in_sequence(h):
>   for i in range(len(h)):
>     yield heapq.heappop(h)
> 
> Yeah its a bit fiddly:
> 1. i needed for for but not used
> 2. The range in the for loop -- normally a python 'smell'
> 
> If python3
> 
> def ins3(h):
>    yield from (heapq.heappop(h) for i in range(len(h)))

Many thanks, I'm using Python3 anyway!
Helmut

[toc] | [prev] | [next] | [standalone]

#60933

Helmut Jarausch <jarausch@igpm.rwth-aachen.de> wrote:

> Hi,
> 
> I'd like to extracted elements from a heapq in a for loop.
> I feel my solution below is much too complicated.
> How to do it more elegantly? 
> I know I could use a while loop but I don't like it.
> 
> Many thanks for some lessons in Python.
> 
> Here is my clumsy solution
> 
> from heapq import heappush, heappop
> # heappop raises IndexError if heap is empty
> 
> H=[]
> for N in 'H','C','W','I' :
>   heappush(H,N)
> 
> # how to avoid / simplify the following function
> 
> def in_sequence(H) :
>   try :
>     while True :
>       N= heappop(H)
>       yield N
>   except IndexError :
>     raise StopIteration
> 
> # and here the application:
> 
> for N in in_sequence(H) :
>   print(N)
> 

If all you want to do is pull all of the elements out of the heap in 
order, you would probably be better off just doing:

for N in sorted(H):
    print(N)

Heaps are mostly useful if you want only some of the elements, or if you 
are continually producing more elements while also processing the 
smallest ones.

However, if you really wnt to do this:

    for N in iter(lambda: heappop(H) if H else None, None):
        print(N)

will work so long as H cannot contain None. If it can just replace both 
occurences of None with some other sentinel:

    sentinel = object()
    for N in iter(lambda: heappop(H) if H else sentinel, sentinel):
        print(N)


Alternatively your 'in_sequence' function would look better without the 
exception handling:

def in_sequence(H) :
    while H:
        yield heappop(H)

-- 
Duncan Booth

[toc] | [prev] | [next] | [standalone]

#60998

On Tue, 03 Dec 2013 13:06:05 +0000, Duncan Booth wrote:

> Helmut Jarausch <jarausch@igpm.rwth-aachen.de> wrote:
> 
>> Hi,
>> 
>> I'd like to extracted elements from a heapq in a for loop.
>> I feel my solution below is much too complicated.
>> How to do it more elegantly? 
>> I know I could use a while loop but I don't like it.
>> 
>> Many thanks for some lessons in Python.
>> 
>> Here is my clumsy solution
>> 
>> from heapq import heappush, heappop
>> # heappop raises IndexError if heap is empty
>> 
>> H=[]
>> for N in 'H','C','W','I' :
>>   heappush(H,N)
>> 
>> # how to avoid / simplify the following function
>> 
>> def in_sequence(H) :
>>   try :
>>     while True :
>>       N= heappop(H)
>>       yield N
>>   except IndexError :
>>     raise StopIteration
>> 
>> # and here the application:
>> 
>> for N in in_sequence(H) :
>>   print(N)
>> 
> 
> If all you want to do is pull all of the elements out of the heap in 
> order, you would probably be better off just doing:
> 
> for N in sorted(H):
>     print(N)
> 
> Heaps are mostly useful if you want only some of the elements, or if you 
> are continually producing more elements while also processing the 
> smallest ones.
> 
> However, if you really wnt to do this:
> 
>     for N in iter(lambda: heappop(H) if H else None, None):
>         print(N)
> 
> will work so long as H cannot contain None. If it can just replace both 
> occurences of None with some other sentinel:
> 
>     sentinel = object()
>     for N in iter(lambda: heappop(H) if H else sentinel, sentinel):
>         print(N)
> 
> 
> Alternatively your 'in_sequence' function would look better without the 
> exception handling:
> 
> def in_sequence(H) :
>     while H:
>         yield heappop(H)

Many thanks!
And as noted in another reply, I try to overlap CPU time with file I/O since
I have to open / read / close a file for each line that gets pushed onto the heap.
Helmut

[toc] | [prev] | [next] | [standalone]

#60935

Helmut Jarausch writes:
...
> I know I could use a while loop but I don't like it.
...
> from heapq import heappush, heappop
> # heappop raises IndexError if heap is empty
...
> # how to avoid / simplify the following function
> 
> def in_sequence(H) :
>   try :
>     while True :
>       N= heappop(H)
>       yield N
>   except IndexError :
>     raise StopIteration

That seems equivalent to this:

def in_sequence(H):
  while H: yield heappop(H)

But I don't like the side-effect. I'd change the name to something
that indicates the draining of the heap - heapaerobic? - or consider
sorted(H) instead as others suggested.

[toc] | [prev] | [next] | [standalone]

#60999

On Tue, 03 Dec 2013 15:56:11 +0200, Jussi Piitulainen wrote:

> Helmut Jarausch writes:
> ...
>> I know I could use a while loop but I don't like it.
> ...
>> from heapq import heappush, heappop
>> # heappop raises IndexError if heap is empty
> ...
>> # how to avoid / simplify the following function
>> 
>> def in_sequence(H) :
>>   try :
>>     while True :
>>       N= heappop(H)
>>       yield N
>>   except IndexError :
>>     raise StopIteration
> 
> That seems equivalent to this:
> 
> def in_sequence(H):
>   while H: yield heappop(H)

Many thanks, that's something I'd hoped for.

> But I don't like the side-effect. I'd change the name to something
> that indicates the draining of the heap - heapaerobic? - or consider
> sorted(H) instead as others suggested.

Since I fill the heap once and empty it afterwards I regard the side-effect
clearly visible.

Helmut

[toc] | [prev] | [next] | [standalone]

#60961

On 03Dec2013 12:18, Helmut Jarausch <jarausch@igpm.rwth-aachen.de> wrote:
> I'd like to extracted elements from a heapq in a for loop.
> I feel my solution below is much too complicated.
> How to do it more elegantly? 

I can't believe nobody has mentioned PriorityQueue.

A PriorityQueue (from the queue module in python 3 and the Queue
module in python 2) is essentially just a regular Queue using a
heapq for the storage.

Example (untested):

  from Queue import PriorityQueue

  PQ = PriorityQueue()
  for item in [1,2,3,7,6,5,9,4]:
    PQ.put(item)

  while not PQ.empty():
    item = PQ.get()
    ... do stuff with item ...

I iterate over Queues so often that I have a personal class called
a QueueIterator which is a wrapper for a Queue or PriorityQueue
which is iterable, and an IterablePriorityQueue factory function.
Example:

  from cs.queues import IterablePriorityQueue

  IPQ = IterablePriorityQueue()
  for item in [1,2,3,7,6,5,9,4]:
    IPQ.put(item)

  for item in IPQ:
    ... do stuff with item ...

Cheers,
-- 
Cameron Simpson <cs@zip.com.au> http://www.cskk.ezoshosting.com/cs/

Those who do not understand Unix are condemned to reinvent it, poorly.
        - Henry Spencer @ U of Toronto Zoology, henry@zoo.toronto.edu

[toc] | [prev] | [next] | [standalone]

#61000

On Wed, 04 Dec 2013 08:13:03 +1100, Cameron Simpson wrote:

> On 03Dec2013 12:18, Helmut Jarausch <jarausch@igpm.rwth-aachen.de> wrote:
>> I'd like to extracted elements from a heapq in a for loop.
>> I feel my solution below is much too complicated.
>> How to do it more elegantly? 
> 
> I can't believe nobody has mentioned PriorityQueue.
> 
> A PriorityQueue (from the queue module in python 3 and the Queue
> module in python 2) is essentially just a regular Queue using a
> heapq for the storage.
> 
> Example (untested):
> 
>   from Queue import PriorityQueue
> 
>   PQ = PriorityQueue()
>   for item in [1,2,3,7,6,5,9,4]:
>     PQ.put(item)
> 
>   while not PQ.empty():
>     item = PQ.get()
>     ... do stuff with item ...
> 
> I iterate over Queues so often that I have a personal class called
> a QueueIterator which is a wrapper for a Queue or PriorityQueue
> which is iterable, and an IterablePriorityQueue factory function.
> Example:
> 
>   from cs.queues import IterablePriorityQueue
> 
>   IPQ = IterablePriorityQueue()
>   for item in [1,2,3,7,6,5,9,4]:
>     IPQ.put(item)
> 
>   for item in IPQ:
>     ... do stuff with item ...
> 
> Cheers,

Many thanks!

I think you QueueIterator would be a nice addition to Python's library.
Helmut

[toc] | [prev] | [next] | [standalone]

#61071

On 04Dec2013 09:44, Helmut Jarausch <jarausch@igpm.rwth-aachen.de> wrote:
> On Wed, 04 Dec 2013 08:13:03 +1100, Cameron Simpson wrote:
> > I iterate over Queues so often that I have a personal class called
> > a QueueIterator which is a wrapper for a Queue or PriorityQueue
> > which is iterable, and an IterablePriorityQueue factory function.
> > Example:
> > 
> >   from cs.queues import IterablePriorityQueue
> > 
> >   IPQ = IterablePriorityQueue()
> >   for item in [1,2,3,7,6,5,9,4]:
> >     IPQ.put(item)
> > 
> >   for item in IPQ:
> >     ... do stuff with item ...
> 
> Many thanks!
> I think you QueueIterator would be a nice addition to Python's library.

I'm not convinced. I'm still sorting out the edge cases, and it's
my own code and use cases!

The basic idea is simple enough:

  class QueueIterator:
    def __init__(self, Q, sentinel=None):
      self.q = Q
      self.sentinel = sentinel
    def __next__(self):
      item = self.q.get()
      if item is self.sentinel:
        # queue sentinel again for other users
        self.q.put(item)
        raise StopIteration
      return item
    def put(self, item):
      if item is self.sentinel:
        raise ValueError('.put of sentinel object')
      return self.q.put(item)
    def close(self):
      self.q.put(self.sentinel)

  QI = QueueIterator(Queue())

Note that it does not work well for PriorityQueues unless you can
ensure the sentinel sorted later than any other item.

But you really need to be sure nobody does a .get() in the internal
queue, or the close protocol doesn't work. This is why the above
does not expose a .get() method.

You want to prevent .put() on the queue after close().
Of course, I have use cases where I _want_ to allow .put() after
close:-(

You may want to issue a warning if more than one call to
.close happens.

And so on.

And I have a some weird cases where the close situation has trouble,
which probably points to .close() not being a great mapping to
my termination scenarios.

It is easy to code for the simple data-in, data-out case though.

Cheers,
-- 
Cameron Simpson <cs@zip.com.au>

Computer manufacturers have been failing to deliver working systems on
time and to budget since Babbage.       - Jack Schofield, in The Guardian

[toc] | [prev] | [next] | [standalone]

#60965 — Re: extracting a heapq in a for loop - there must be more elegant solution

On Tue, Dec 3, 2013 at 2:13 PM, Cameron Simpson <cs@zip.com.au> wrote:
> On 03Dec2013 12:18, Helmut Jarausch <jarausch@igpm.rwth-aachen.de> wrote:
>> I'd like to extracted elements from a heapq in a for loop.
>> I feel my solution below is much too complicated.
>> How to do it more elegantly?
>
> I can't believe nobody has mentioned PriorityQueue.

As far as I'm aware, the only advantage of PriorityQueue over heapq is
that the former is thread-safe, which does not appear to be relevant
here.  I haven't tested it for speed, but I imagine it would be a fair
bit slower, mostly thanks to the locking it needs to do.

[toc] | [prev] | [next] | [standalone]

#60967 — Re: extracting a heapq in a for loop - there must be more elegant solution

On 12/3/13 4:43 PM, Ian Kelly wrote:
> On Tue, Dec 3, 2013 at 2:13 PM, Cameron Simpson <cs@zip.com.au> wrote:
>> On 03Dec2013 12:18, Helmut Jarausch <jarausch@igpm.rwth-aachen.de> wrote:
>>> I'd like to extracted elements from a heapq in a for loop.
>>> I feel my solution below is much too complicated.
>>> How to do it more elegantly?
>>
>> I can't believe nobody has mentioned PriorityQueue.
>
> As far as I'm aware, the only advantage of PriorityQueue over heapq is
> that the former is thread-safe, which does not appear to be relevant
> here.  I haven't tested it for speed, but I imagine it would be a fair
> bit slower, mostly thanks to the locking it needs to do.
>

In fact, if you look at the implementation of PriorityQueue, it uses a 
heapq internally, so yes, other than the locking, the speed will be the 
same.

--Ned.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web