Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
The best way to speed up this loop is not to execute it.

Yes, I'm serious. Depending on your actual problem, there might be a way around it.

If you read abut inversion lists, you find that this idea can be generalized to overlapping lists.

Assume you have the ranges 10-50 and 20-100; You mark each start of a range with a positive number, and each end of range by a negative number. So 1-50 and 20-100 would translate to

[1, 20, -50, -100]

That way you only store two integers for a large range.

If you want to know how many ranges overlap at a given point, say at 30, you just traverse the array from left to right up to abs($_) <= 30, and count how many positive and how many negative numbers you have encountered; the difference is the number of overlapping ranges.

You can also cache such numbers as long as the array doesn't change, to avoid having it to iterate it from the beginning every time.


In reply to Re: Optimizing a double loop by moritz
in thread Optimizing a double loop by roibrodo

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



  • 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 or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (1)
As of 2021-10-22 03:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (85 votes). Check out past polls.

    Notices?