[Python-Dev] collections.sortedtree

[Antoine Pitrou]

On Wed, 26 Mar 2014 23:41:42 +0200
Marko Rauhamaa <marko at pacujo.net> wrote:
> Antoine Pitrou <solipsis at pitrou.net>:
> 
> > Wouldn't a heapq work as well for those two?
> 
> In my experience, networking entities typically start a timer at each
> interaction and cancel the pending one. So you have numerous timers that
> virtually never expire. You might have 100 interactions per second, each
> canceling and restarting a 10-minute timer.
> 
> I don't know first hand if that causes heap queues to cause measurable
> heap or CPU pressure.

Each individual heapq operation (push or pop) will be O(log n). That's
not different from a balanced search tree (although of course the
constant multiplier may vary).

Regards

Antoine.