On Sep 9, 2004, at 5:39 AM, Stefan Behnel wrote:
1) If we remove the entry during the call to cancel(), it takes log(N) time and is only done once.
2) If we do /not/ remove the entry, cancel() takes constant time (set a flag), but runUntilCurrent has to deal with a larger stack on each iteration. So this may slow down things considerably if many delayed calls are cancelled and remain on the stack.
I'm thinking of something like: - When you call cancel, set the cancelled flag, and increment a counter of cancelled items. - in runUntilCurrent, if the number of cancelled items in the list is both > 50 and > 1/2 of the total items, filter them out and re-heapify the list. Now, the only thing left that needs the heap_pos is moving a delayedcall to a sooner time. This is an unlikely event, and thus we should not be overly concerned about its speed. Now we can use the builtin heapq, which is written in C in Python 2.4. Patch attached to bug. James