efficient interval containment lookup

Steven D'Aprano steven at REMOVE.THIS.cybersource.com.au
Tue Jan 13 06:47:29 CET 2009

On Mon, 12 Jan 2009 20:55:36 -0800, Per Freem wrote:

> on one run, i get:
> interval tree: 8584.682
> brute force: 8201.644

Here are three runs on my computer:

interval tree: 10132.682
brute force: 12054.988

interval tree: 10355.058
brute force: 12119.227

interval tree: 9975.414
brute force: 12052.174

I find that interval tree is consistently faster than the brute force 
method, by a factor of at least 16%. I'd expect that benefit to increase 
dramatically as the number of intervals gets bigger.


More information about the Python-list mailing list