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
