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: 

while (($start, $end) = each %interval) {
        for $time (@time) {
                if ($time >= $start && $time < $end) {                
+        
                        push @match, $time;
                }
        }
}

[download]

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.)

--
Mark Dominus
Perl Paraphernalia

In reply to Assemble times into ranges by Dominus

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.