Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

I'm a fan of the Binary Search (my implementation also borrows heavily from Mastering Algorithms with Perl), but I'm not sure it's the best tool for this job. You're looking for everything from 15 minutes back, through the present (end of the file). File::ReadBackwards seems like a better algorithm. On the one hand it's a linear search from the end of file to the 15 minute mark. On the other hand, even if you're using a binary search to find that 15 minute mark, you still have the linear operation of retrieving everything from the EOF to that 15 minute mark for processing.

May as well just read the file backwards, and stop when you find the record that is more than 15 minutes old. That way instead of a O(log n) plus an O(n) operation (the search, and the retrieve), you have a single O(n) operation (the retrieve, stopping when you get to the mark). But more importantly, you eliminate a ton of complexity.

Quoting from Wikipedia:

When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it, and another study shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.


Dave


In reply to Re: Using binary search to get the last 15 minutes of httpd access log by davido
in thread Using binary search to get the last 15 minutes of httpd access log by mhearse

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!
  • 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, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            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.
  • Log In?
    Username:
    Password:

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

    How do I use this? | Other CB clients
    Other Users?
    Others chanting in the Monastery: (8)
    As of 2014-09-18 23:15 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (126 votes), past polls