On Sun, May 13, 2012 at 2:29 PM, Alec Taylor <alec.tayl...@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.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
