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.bro...@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 -- http://mail.python.org/mailman/listinfo/python-list