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

---

---

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