priorityqueue, sortedlist in collections?
I wonder if anyone else finds the heapq and bisect APIs a little dated. It seems like these things could be offered in a more intuitive and featureful way by making them classes. They could go in the collections module: class priorityqueue: def __init__(self, elements=(), *, cmp=None, key=None, reversed=False) def add(self, element) def pop(self) --> remove and return the min element def __iter__(self) --> (while self: yield self.pop()) ... ... any other list methods that make sense ... for example, __len__ but not __getitem__ ... class sortedlist: def __init__(self, elements=(), *, cmp=None, key=None, reversed=False) def add(self, element) # insort # Methods involving searching are O(log N). def __contains__(self, element) def index(self, element) def remove(self, element) ... ... plus all the other read-only list methods, ... and the modifying list methods that make sense ... The point is, most of the API comes from list and sort. I think they'd be easier to use/remember than what we have. Once upon a time Tim mentioned (maybe semi-seriously) possibly adding a Fibonacci heap container. I think a plain old binary heap would be good enough for starters. I could do this. Any interest? -j
On 3/1/07, Jason Orendorff <jason.orendorff@gmail.com> wrote:
I agree, at least for heapq. The algorithm involves enough voodoo that it's not obvious how to extend it, so it might as well be wrapped in a class that hides as much as possible. The same can't be said for bisect though. All it does is replace del a[bisect_left(a, x)] with a.remove(x). A little cleaner, but no more obvious. And the cost is still O(n) since it involves moving all the pointers after x.
class priorityqueue:
Should inherit from object if this is going into 2.x.
__iter__ shouldn't modify the container.
-- Adam Olsen, aka Rhamphoryncus
On 3/2/07, Adam Olsen <rhamph@gmail.com> wrote:
On 3/1/07, Jason Orendorff <jason.orendorff@gmail.com> wrote:
I wonder if anyone else finds the heapq and bisect APIs a little dated.
Ooh, me, me!
I agree, at least for heapq. The algorithm involves enough voodoo
that it's not obvious how to extend it, so it might as well be wrapped in a class that hides as much as possible.
Sounds good to me. +1 The same can't be said for bisect though. All it does is replace del
A sortedlist class seems like a useful abstraction to me, since while using an instance of such a class, you could be sure that the list remains sorted. For example, you don't have to worry about it being changed outside of your code and no longer being sorted. Also, wouldn't a sortedlist class also have in insert() method to replace bisect.insort(), as well as different implementations of __contains__ and index?
On 3/1/07, Adam Olsen <rhamph@gmail.com> wrote:
On 3/1/07, Jason Orendorff <jason.orendorff@gmail.com> wrote:
class priorityqueue: Should inherit from object if this is going into 2.x.
generators do not need to be reiterable. lists are reiterable, but I wouldn't expect a socket (treated as a file) to be. For a queue that is already sorted, the natural use case is to take the task and do it, explicitly adding it back to the end if need be. I would expect an operation that *didn't* remove things from the queue to have view in the name somewhere. -jJ
On Fri, Mar 02, 2007 at 12:45:57PM -0600, Collin Winter wrote:
Impossible for external streams such as pipes and sockets. Oleg. -- Oleg Broytmann http://phd.pp.ru/ phd@phd.pp.ru Programmers don't die, they just GOSUB without RETURN.
On 3/2/07, Jim Jewett <jimjjewett@gmail.com> wrote:
A priorityqueue seems far more like a list than a socket though. I'd be very surprised if __iter__ was destructive. If destructive is the only option I would prefer it be a explicit method. Especially since it's common modify and reiterate over a priority queue, which I believe never happens for files or sockets. -- Adam Olsen, aka Rhamphoryncus
On 3/1/07, Jason Orendorff <jason.orendorff@gmail.com> wrote:
I wonder if anyone else finds the heapq and bisect APIs a little dated.
I find them too much of a special case.
... They could go in the collections module:
This alone would be an improvement. I don't disagree with the rest of your proposal, but for me, this is the big one. -jJ
On 3/1/07, Jason Orendorff <jason.orendorff@gmail.com> wrote:
I agree, at least for heapq. The algorithm involves enough voodoo that it's not obvious how to extend it, so it might as well be wrapped in a class that hides as much as possible. The same can't be said for bisect though. All it does is replace del a[bisect_left(a, x)] with a.remove(x). A little cleaner, but no more obvious. And the cost is still O(n) since it involves moving all the pointers after x.
class priorityqueue:
Should inherit from object if this is going into 2.x.
__iter__ shouldn't modify the container.
-- Adam Olsen, aka Rhamphoryncus
On 3/2/07, Adam Olsen <rhamph@gmail.com> wrote:
On 3/1/07, Jason Orendorff <jason.orendorff@gmail.com> wrote:
I wonder if anyone else finds the heapq and bisect APIs a little dated.
Ooh, me, me!
I agree, at least for heapq. The algorithm involves enough voodoo
that it's not obvious how to extend it, so it might as well be wrapped in a class that hides as much as possible.
Sounds good to me. +1 The same can't be said for bisect though. All it does is replace del
A sortedlist class seems like a useful abstraction to me, since while using an instance of such a class, you could be sure that the list remains sorted. For example, you don't have to worry about it being changed outside of your code and no longer being sorted. Also, wouldn't a sortedlist class also have in insert() method to replace bisect.insort(), as well as different implementations of __contains__ and index?
On 3/1/07, Adam Olsen <rhamph@gmail.com> wrote:
On 3/1/07, Jason Orendorff <jason.orendorff@gmail.com> wrote:
class priorityqueue: Should inherit from object if this is going into 2.x.
generators do not need to be reiterable. lists are reiterable, but I wouldn't expect a socket (treated as a file) to be. For a queue that is already sorted, the natural use case is to take the task and do it, explicitly adding it back to the end if need be. I would expect an operation that *didn't* remove things from the queue to have view in the name somewhere. -jJ
On Fri, Mar 02, 2007 at 12:45:57PM -0600, Collin Winter wrote:
Impossible for external streams such as pipes and sockets. Oleg. -- Oleg Broytmann http://phd.pp.ru/ phd@phd.pp.ru Programmers don't die, they just GOSUB without RETURN.
On 3/2/07, Jim Jewett <jimjjewett@gmail.com> wrote:
A priorityqueue seems far more like a list than a socket though. I'd be very surprised if __iter__ was destructive. If destructive is the only option I would prefer it be a explicit method. Especially since it's common modify and reiterate over a priority queue, which I believe never happens for files or sockets. -- Adam Olsen, aka Rhamphoryncus
On 3/1/07, Jason Orendorff <jason.orendorff@gmail.com> wrote:
I wonder if anyone else finds the heapq and bisect APIs a little dated.
I find them too much of a special case.
... They could go in the collections module:
This alone would be an improvement. I don't disagree with the rest of your proposal, but for me, this is the big one. -jJ
participants (6)
-
Adam Olsen -
Collin Winter -
Jason Orendorff -
Jim Jewett -
Oleg Broytmann -
Tal Einat