re: A (kinda) Circular Cache

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) {
...
}
[download]

would be much more costly than a flat array.

Comment on re: A (kinda) Circular Cache Download Code

Replies are listed 'Best First'.

Re (tilly) 3: A (kinda) Circular Cache
by tilly (Archbishop) on Mar 24, 2001 at 01:11 UTC

classic

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

[reply]


Perl Monk, Perl Meditation
	PerlMonks