Good data structure for finding date intervals including a given date

[Alec Taylor]

There is an ordered dict type since Python 3.1[1] and Python 2.7.3[2].

If you are looking for the best possible self-sorting structure for
searching, then perhaps you are looking for what's outlined in the
2002 article by Han & Thorup: Integer Sorting in O(n sqrt(log log n))
Expected Time and Linear Space[3].

[1] http://www.python.org/getit/releases/3.1/
[2] http://www.python.org/getit/releases/2.7.3/
[3] http://dl.acm.org/citation.cfm?id=645413.652131

On Sat, May 12, 2012 at 10:17 PM, Jean-Daniel
<jeandaniel.browne at gmail.com> wrote:
>
> 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?
>
> This has been discussed here: http://bugs.python.org/issue1324770 ,
> and lack of good use case was the reason the bug was closed. A dict
> implemented with red black trees is slower (but not too slow) at
> inserting, searching and deleting but the dict is always kept ordered.
> Bigger projects have their own implementation of ordered dict so such
> datastructures in the standard library would help the porting of the
> project to other platforms. Take the example of the zodb and the
> C-only implementation of the btree: btree in the stdlib in Python
> would help the porting to GAE or pypy [2].
>
> Cheers,
>
> [1] in the "Cormen" book:
> http://en.wikipedia.org/wiki/Introduction_to_Algorithms
> [2] https://blueprints.launchpad.net/zodb/+spec/remove-btree-dependency
> --
> http://mail.python.org/mailman/listinfo/python-list