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

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.