On 13 Lug, 22:35, Miles <[EMAIL PROTECTED]> wrote: > On Sun, Jul 13, 2008 at 3:05 PM, Giampaolo Rodola' <[EMAIL PROTECTED]> wrote: > > On 13 Lug, 19:31, "Martin v. Löwis" <[EMAIL PROTECTED]> wrote: > >> > I understand that heapq is not that efficient to implement timeouts as > >> > I thought at first. > >> > It would have been perfect if there were functions to remove arbitrary > >> > elements withouth needing to re-heapify() the heap every time. > > >> It is efficient for that - you just need to use it correctly. > > >> To remove the nth element from a heap, replace it with the last element, > >> and then _siftup that element: > > >> The time complexity for that operation is O(log(len(heap))). > > The problem is that in order to remove an arbitrary element from a > heap, you usually have to do an O(n) linear search in order to find it > first, since you can't know ahead of time which index an arbitrary > element is at. (You can, actually, but only if your heap > implementation somehow notifies the elements of their new index when > it moves them in the heap, which the Python heapq module doesn't do, > so you'd have to write your own heap implementation.) > > > And if instead of removing an element I'd want to change its value? > > E.g.: > > > >>> heap = [0, 2, 1, 4, 5, 6, 7, 8, 9] > > >>> heapify(heap) > > >>> heap > > [0, 2, 1, 4, 5, 6, 7, 8, 9] > > >>> heap[4] = 12 > > Don't do that; you must first remove the element and then reinsert it. > > -Miles
That seems to be slower than re-heapifying() the heap. The code I used (which is probably wrong): def reset(self): """Reschedule this call resetting the current countdown.""" assert not self.cancelled, "Already cancelled" self.timeout = time.time() + self.__delay n = heap.index(self) if n == len(heap) - 1: heap.pop() else: heap[n] = heap.pop() heapq._siftup(heap, n) heapq.heappush(heap, self) Moreover I have the feeling that doing such thing requires a different code whether the new value I use as replacement is lower or higher in comparison to the older one. Am I right? --- Giampaolo http://code.google.com/p/pyftpdlib/ -- http://mail.python.org/mailman/listinfo/python-list