Perl-Sensitive Sunglasses | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
A guy posted a question to p5p today.
It was in the wrong place (p5p is not for questions about
programming in Perl) so I sent him away, but it was still
an interesting question.
He has a hash %interval where the keys are start times and the values are corresponding end times. He also has an array @time of interesting times. He want to know which elements of @time occur inside one of the intervals. Here's something like his original code:
He has a problem: This is too slow. %interval contains 10,000 intervals, and @time contains 5,000 times. He needs it to be faster. I can see that improvements might be possible on two levels. One could improve the code without changing the data structures. For example, you could sort keys %interval and @time and then go through the @time items in sorted order, ignoring the start-times that were too late. You could replace the inner loop with grep. Probably a better approach would be to improve the data structures. I can't think offhand of a good way to store the information, however. (One thing that does come to mind is that he should preprocess the intervals, and merge any intervals that overlap into one large interval. Then he could make a single pass over both lists.)
-- In reply to Assemble times into ranges by Dominus
|
|