efficient interval containment lookup

Tim Chase python.list at tim.thechases.com
Tue Jan 13 11:13:06 CET 2009

Per Freem wrote:
> i forgot to add, my naive_find is:
> def naive_find(intervals, start, stop):
>   results = []
>   for interval in intervals:
>     if interval.start >= start and interval.stop <= stop:
>       results.append(interval)
>   return results

I don't know if using a list-comprehension here is a better 
choice, but your code looks very much like

   def naive_find(intervals, start, stop):
     return [interval for interval in intervals
       if interval.start >= start and interval.stop <= stop]

which may even be simple enough to include in-line rather than as 
a sub-function (with any associated call overhead).

I've found that usually Python's smart/efficient handling of 
list-comprehensions can make an appreciable difference within 
critical-loop constructs.


More information about the Python-list mailing list