> I hadn't expected purge() to call heapify(), so I was just expecting O(N) > runtime for the actual removal. The comments claim the runtime of the > purge operation is O(N + ClogN) where C is the number of deleted elements > (which would make it O(N) when C is 1, but looking at the code I think it's > actually O(N + ((N-C)/2)log((N-C)/2)), which is O(NlogN) when C is 1. So > it's not O(N^2), but it's also definitely not O(N) despite the comment's > claim. > > Yes. I think this is a more appropriate claim. But in my experience it seems to grow larger than NlogN but perhaps there are secondary issues here like L1/L2 cache hits that dramatically slow it down
> Now I just have it essentially flag the timer task as clear and it will go > > through the timer queue and not get executed. > > > > Sounds fine, as long as "flag the timer task as clear" also means "call > TimerTask.cancel(), so that the task's state will be TimerTask.CANCELLED so > it'll be removed the next time it comes to the top of the queue in > Timer.mainLoop(), in addition to any WeakReference stuff we may do". If > not, you're going to have a lot of no-op TimerTasks that stick around > forever, so 1) your value of N will grow over time, so even O(N) operations > will take longer over time, 2) there's still an expensive thread context > switch even if the task is a nominal no-op, and 3) eventually you could OOM > due to the memory those no-op TimerTasks take. Does that match what you've > implemented? > > Yes. here’s the new cancel method: https://gist.github.com/burtonator/6fe3ee640f5f1b27caa2 I call task .cancel() then .clear() (which clears the reference). and here’s the new SchedulerTimerTask https://gist.github.com/burtonator/be4bd7b39c250b2b1a0c -- Founder/CEO Spinn3r.com Location: *San Francisco, CA* blog: http://burtonator.wordpress.com … or check out my Google+ profile <https://plus.google.com/102718274791889610666/posts>
