What is the name of this algorithm?

NOTE: I am trying to find the name of the specific LRU algorithm, not that this is a caching algorithm (I know it is, I wrote it). Telling me this is a caching algorithm is like telling someone looking for the name red-black tree that it is a tree balancing algorithm.

I recently created the following algorithm, but I am fairly certain someone must have done this before me and given it a name. Does this look familiar to anyone?

Purpose: Keep a fixed size pool of strings and the number of times they have been seen. If the pool exceeds the max size, only keep the most recently used items.

Pseudocode:

var cur
var old

func add_key(key)

    if cur not defined
        put a hash in cur

    if key in old
        copy value from old to cur for this key
        delete key from old

    increment cur[key]

    if there are too many keys in cur
        replace old with cur
        empty cur
        copy value from old to cur for this key
        delete key from old

    return cur[key]           

A simple implementation in Perl 5 looks like:

#!/usr/bin/perl

use strict;
use warnings;

{ package Fixed::LRU::Counter;

    sub new {
        my ($class, $max) = @_;
        return bless {
            max => $max,
            cur => {},
            old => {},
        }, $class;开发者_Python百科
    }

    sub add_key {
        my ($self, $k) = @_;

        if ($self->{old}{$k}) {
            $self->{cur}{$k} = $self->{old}{$k};
            delete $self->{old}{$k};
        }

        $self->{cur}{$k}++;

        if (keys %{$self->{cur}} > $self->{max}) {
            $self->{old} = $self->{cur};
            $self->{cur} = { $k => $self->{old}{$k} };
            delete $self->{old}{$k};
        }

        return $self->{cur}{$k};
    }
}

my $c = Fixed::LRU::Counter->new(3);

for my $k (qw/a a b c d e f f g a f/) {
    print "$k: ", $c->add_key($k), "\n";
}

---

Least frequently used cache algorithm

It is not LRU because LRU orders the cache items by last access time, not by access count like you do.

---

Isn't this an implementation you could use for cache, or a pagefile?

It works with a most-recent method, there are ofcourse other strategies, like removing the least used, removing the newest, etc etc.

---

It's certainly not MRU, but not exactly LRU either. Having both cur and old makes it look like you're trying to use old as an eviction buffer.

However, the way you're managing cur isn't really LRU or MRU -- when your cache gets full, you're keeping only the new entry, and throwing the entire rest of its content out to the eviction cache (old). Normally, when adding an entry would make your cache too large, you pick exactly one existing cache entry to throw out (to the eviction buffer, if you're using one). With the way you're throwing out the whole thing, I guess you could call it a "not most recently used cache with eviction buffer".

To be entirely honest, however, I think I'd probably use a much shorter, simpler name: "a mistake". I suppose there might be some circumstance under which this would/will/does work well, but at least right off it looks/sounds like a pretty poor idea.

The basic idea of a cache is that if something was used recently, it's probably going to be used again soon. In this case, however, you're (nearly) emptying the entire cache at almost completely arbitrary times. This might make sense if you know a lot about your data access, and know that you tend to load N data items and use them for quite a while, but when you load item N+1, you probably won't use the previous N items any more, so you might as well flush them all out, and recover them for the eviction buffer when that was wrong.