Dave Rolsky wrote:
Is there any chance you would consider something other than RedBlack trees for the individual TZ files? The reason I ask is we could choose some algorithm that was faster for searching than RedBlack trees as long as we make some assumptions about the data.From profiling, I think the single biggest speed up that could be done for DateTime, when using an Olson DB timezone, would be to implement Tree::RedBlack in XS. Even better would be to implement a custom red-black tree that natively worked with the kind of weird values that are fed into (complex data structures as opposed to scalars). This would be a huge win for anyone who had to work with time zones.
I'm looking at my copy of "Introduction to Algorithms" for inspiration, but nothing is actually leaping out at me. I think that an array of objects would be suffient, as long as we could assume that
a) the utc_start values are unique for each TZ;
b) the utc_end values are not overlapping the subsequent utc_start;
c) they are sorted.
In this case, we could actually use a binary search on the array to locate the appropriate utc_start/utc_end values for the period in question. This would be faster than O(1) in practice for search.
Or am I missing some instance where we would have to insert values into the TZ?
John
--
John Peacock
Director of Information Research and Technology
Rowman & Littlefield Publishing Group
4720 Boston Way
Lanham, MD 20706
301-459-3366 x.5010
fax 301-429-5747
