Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

Re (tilly) 1: A (kinda) Circular Cache

by tilly (Archbishop)
on Mar 24, 2001 at 00:08 UTC ( #66724=note: print w/replies, xml ) Need Help??

in reply to A (kinda) Circular Cache

Sorry, this is not as efficient as you advertise.

Every time you scan or manipulate an array that is a O(n) operation. Arranging to constantly scan arrays quickly turns into O(n*n) which is slow algorithmically.

I hinted at this to you in Re (tilly) 3: Efficiency Question. MeowChow and I talked more in private than you see at that node. The key concept here is that you want to use hash lookups (O(1) operation) as often as possible and then rebuild your cache (O(n) operation but with a poor constant) only when you have to. This is algorithmically much, much better than doing O(n) searches repeatedly.

The general rule is that whenever you see "scan array" you should look for a hash.

There are other stylistic notes. For instance you could write your new method as:

sub new { my $self = bless { array => [] }, shift; $self->{size} = shift || 30; $self; }
which by using the 2-argument form of bless will allow someone to inherit from your cache implementation if they want...

Replies are listed 'Best First'.
re: A (kinda) Circular Cache
by mr.nick (Chaplain) on Mar 24, 2001 at 00:26 UTC
    I remember well the previous discussion about this, I'm afraid that I simply couldn't work out how to do it efficiently.

    I tried maintaining a seperate hash for accessing the data in addition to the array which maintained the order, but ran into difficulties keeping them in sync. I tried having the hash reference positions in the array, but that would require updating the hash when the array changed order (after a get or del or ins). I tried other methods, but found myself still walking the array to maintain it (dels & ins).

    Since I was walking the array anyhoot, I just left it where you see it now.

    What I don't understand is your comment Arranging to constantly scan arrays quickly turns into O(n*n) which is slow algorithmically.. In what way is my O(n) turned into O(n*n) ? Any given single operation of the cache only walks the array once (excluding the splice); isn't that the definition of O(n)? (I'm straining to remember my "big o" notation crap from a decade ago).

    I should note that I decided to use an array to maintain the order instead of something akin to $hash->{hits}++ and sorting/dropping by that. I presumed a
    for my $x (sort { $a->{hits} <=> $b->{hits} } @array) { ... }
    would be much more costly than a flat array.
      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.)

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://66724]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (5)
As of 2023-03-27 11:15 GMT
Find Nodes?
    Voting Booth?
    Which type of climate do you prefer to live in?

    Results (65 votes). Check out past polls.