Trees

[Marko Rauhamaa]

Terry Reedy <tjreedy at udel.edu>:

> Others have answered as to why other special-purpose
> constrained-structure trees have not been added to the stdlib.

Ordered O(log n) mappings are not special-purpose data structures. I'd
say strings and floats are much more special-purpose than ordered
mappings, and yet Python has direct support for those.

As I said, I use ordered mappings to implement timers. GvR uses the
heapq module for the purpose. The downside of heapq is that canceled
timers often flood the heapq structure; in networking you can easily
start a thousand timers a second but virtually no timer ever expires.
Python's asyncio ignores the problem, but GvR mentioned a periodic
"garbage collection" as a potentially effective solution. I tested the
garbage collection trick and it did seem very effective.


Marko