Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
The classic algorithm mistake is to wind up walking through one array, scanning another for each item. If the two arrays are both of similar size n, this is a O(n*n) operation. There are many, many variations on this, but they all boil down to paying attention to whether you are scanning a list, then asking why.

So you are right, your operations are O(n). But these are operations that you expect to do very often, and the result in real code will be an overall O(n*n) type operation. As I said in Re (tilly) 3: Sort this data, you should be leery of doing a loop within a loop if you can avoid it.

Now you are right that it is hard to do a perfect LRU with a hash. If it matters that your cache always have the exact same size, then you are going to face constant resynchronization work. Now you can do it efficiently. It will require having a linked list, keeping track of both head and tail, and having a hash lookup into the list to avoid scanning it. With all of that you can do an algorithmically efficient true LRU. But note that while algorithmically it is scalable, in practice the operations are complex enough that it will be slow...

However in the tradition of Close enough for government work! what is far less work - and still algorithmically good - is to say that maintaining a perfect LRU cache of fixed size is not that important. Instead let it grow, and then rebuild upon need. (Perl uses this type of periodic on demand allocation of resources in several places. Works well.) Once you accept that idea you can go for the simpler strategy of using a hash as a cache, and rebuilding the cache whenever it gets too big.

This is what I did before. The resulting algorithm is O(1) the vast majority of times, but 1 time in n will be O(n). Amortize the cost of the one very expensive hit where you rebuild the hash over all of the times that you didn't do that, and the result averages out to O(1). (I sped up both map and unshift with patches like this.)


In reply to Re (tilly) 3: A (kinda) Circular Cache by tilly
in thread A (kinda) Circular Cache by mr.nick

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, 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
  • 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.
  • 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?Last hourOther CB clients
    Other Users?
    Others having a coffee break in the Monastery: (3)
    As of 2024-07-14 17:00 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      No recent polls found

      Notices?
      erzuuli‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.