algorithm - 这个算法的名字是什么？

Question

注意:我是想找具体LRU算法的名字，并不是说这是缓存算法(我知道是，我写的)。告诉我这是一个缓存算法就像告诉一个正在寻找红黑树这个名字的人这是一个树平衡算法。

我最近创建了以下算法，但我相当肯定有人在我之前完成了这个并给它起了名字。有没有人觉得这很眼熟？

目的:保持一个固定大小的字符串池和它们被看到的次数。如果池超过最大大小，则只保留最近使用的项目。

伪代码:

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]           

Perl 5 中的一个简单实现如下所示:

#!/usr/bin/perl

use strict;
use warnings;

{ package Fixed::LRU::Counter;

    sub new {
        my ($class, $max) = @_;
        return bless {
            max => $max,
            cur => {},
            old => {},
        }, $class;
    }

    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";
}

Answer 1

Least frequently used cache algorithm

这不是 LRU，因为 LRU 按上次访问时间对缓存项进行排序，而不是像您那样按访问次数排序。