Good data structure for finding date intervals including a given date

[Jean-Daniel]

On Sun, May 13, 2012 at 2:29 PM, Alec Taylor <alec.taylor6 at gmail.com> wrote:
> There is an ordered dict type since Python 3.1[1] and Python 2.7.3[2].

Ordered dict are useful, but they only remember the ordered in which
they were added, you can not order them a on key.

Thanks for the links.

>
> 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