[Python-Dev] collections.sortedtree (original) (raw)

Antoine Pitrou solipsis at pitrou.net
Wed Mar 26 22:48:48 CET 2014

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.

More information about the Python-Dev mailing list