efficient interval containment lookup

[Steven D'Aprano]

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.



-- 
Steven