Re: extracting a heapq in a for loop - there must be more elegant solution
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 -- https://mail.python.org/mailman/listinfo/python-list
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. -- https://mail.python.org/mailman/listinfo/python-list
Re: extracting a heapq in a for loop - there must be more elegant solution
On Tue, 03 Dec 2013 13:06:05 +, Duncan Booth wrote: Helmut Jarausch jarau...@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 -- https://mail.python.org/mailman/listinfo/python-list
Re: extracting a heapq in a for loop - there must be more elegant solution
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: extracting a heapq in a for loop - there must be more elegant solution
On Wed, 04 Dec 2013 08:13:03 +1100, Cameron Simpson wrote: On 03Dec2013 12:18, Helmut Jarausch jarau...@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 -- https://mail.python.org/mailman/listinfo/python-list
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. -- https://mail.python.org/mailman/listinfo/python-list
Re: extracting a heapq in a for loop - there must be more elegant solution
On 04Dec2013 09:44, Helmut Jarausch jarau...@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 c...@zip.com.au
Computer manufacturers have been failing to deliver working systems on
time and to budget since Babbage. - Jack Schofield, in The Guardian
--
https://mail.python.org/mailman/listinfo/python-list
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) -- https://mail.python.org/mailman/listinfo/python-list
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(). -- https://mail.python.org/mailman/listinfo/python-list
Re: extracting a heapq in a for loop - there must be more elegant solution
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))) -- https://mail.python.org/mailman/listinfo/python-list
Re: extracting a heapq in a for loop - there must be more elegant solution
Helmut Jarausch jarau...@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 -- https://mail.python.org/mailman/listinfo/python-list
Re: extracting a heapq in a for loop - there must be more elegant solution
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. -- https://mail.python.org/mailman/listinfo/python-list
Re: extracting a heapq in a for loop - there must be more elegant solution
On 03Dec2013 12:18, Helmut Jarausch jarau...@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 c...@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, he...@zoo.toronto.edu -- https://mail.python.org/mailman/listinfo/python-list
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 c...@zip.com.au wrote: On 03Dec2013 12:18, Helmut Jarausch jarau...@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. -- https://mail.python.org/mailman/listinfo/python-list
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 c...@zip.com.au wrote: On 03Dec2013 12:18, Helmut Jarausch jarau...@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. -- https://mail.python.org/mailman/listinfo/python-list
Re: extracting a heapq in a for loop - there must be more elegant solution
On 03Dec2013 14:43, Ian Kelly ian.g.ke...@gmail.com wrote: On Tue, Dec 3, 2013 at 2:13 PM, Cameron Simpson c...@zip.com.au wrote: On 03Dec2013 12:18, Helmut Jarausch jarau...@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. I could claim I do a lot of multithreaded stuff, which is true. But really I just prefer the put/get abstraction. A heapq is very overtly a heap manipulator applied to an arbitrary list. A Queue is more self contained, for all that it is the same thing happening inside. Cheers, -- Cameron Simpson c...@zip.com.au Are we alpinists, or are we tourists followed by tourists! tourists! - Kobus Barnard ko...@cs.sfu.ca in rec.climbing, on things he's heard firsthand -- https://mail.python.org/mailman/listinfo/python-list
