Am 12.05.2012 14:17, schrieb Jean-Daniel: > Hello, > > I have a long list of n date intervals that gets added or suppressed > intervals regularly. I am looking for a fast way to find the intervals > containing a given date, without having to check all intervals (less > than O(n)). > > Do you know the best way to do this in Python with the stdlib? > > A variant of the red black trees can do the job quickly [1], is this a > good enough use case to discuss the inclusion of a red black tree > implementation in the stdlib?
A more general data structure for spatial search are R-Trees [1]. In few words R-Tree optimize indexing and containment tests in n dimensions. Christian [1] http://en.wikipedia.org/wiki/R-tree -- http://mail.python.org/mailman/listinfo/python-list
