这个算法的名字是什么？

注：我试图找到具体的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"; 
}

来源

2011-03-25 Chas. Owens

您正在跟踪项目被查看的次数，但它对您的缓存算法没有任何影响（例如：它看起来根本没有用于确定某个项目被驱逐或不）。这是红鲱鱼吗？ – mhum 2011-03-26 00:41:09

@mhum它实际上记录了我们看到这些项目的频率（这是我们真正关心的），但可能有无数项目，所以我们只想跟踪我们最近看到的项目。 – 2011-03-26 13:35:59

@Chas。欧文斯：虽然你可能在其他地方使用它，但我看不到你在缓存算法中实际使用它的方式。例如，如果删除了“$ self - > {cur} {$ k} ++”这一行，那么add_key（）会有什么不同？虽然add_key（）的返回值将毫无意义，但cur和old缓冲区的内容将保持不变，是不是？或者我误解了你的实现？ – mhum 2011-03-26 19:38:31

Least frequently used cache algorithm

这不是LRU因为LRU订单缓存项目的最后访问时间，而不是像你这样访问计数。

来源

2011-03-25 14:35:58 jdehaan

该类是LRU，不是MRU的好处，但我正在寻找特定算法的名称，而不是普通类。 – 2011-03-25 14:47:46

@Chas该算法是如此微不足道，我不认为它有一个自己的名字。 – 2011-03-25 14:51:39

我认为这是你可以构建的LFU算法的最简单变体。大多数基于LFU的算法（如LFU *或Window-LFU）旨在解决此算法固有的高速缓存污染问题，如果在实施过程中不考虑时间的话。 – jdehaan 2011-03-25 15:27:24

这不是一个实现，你可以使用缓存或页面文件？

它的工作原理有最近期的方法，有ofcourse其它策略，如消除使用最少的，除去最新的，等等等等

来源

2011-03-25 14:32:40 Nanne

这当然不是MRU，但也不完全是LRU。同时拥有cur和old使其看起来像您试图使用old作为驱逐缓冲区。

但是，你管理cur的方式是不是真的LRU 或 MRU - 当你的缓存已满，你保持仅新条目，和投掷的整个休息了内容输出到驱逐缓存（old）。通常情况下，添加条目会使缓存过大时，您会选择正确的一个现有缓存条目丢弃（如果您使用的是缓存条目）。随着你扔掉整个东西的方式，我想你可以把它称为“不是最近使用的驱逐缓冲区高速缓存”。然而，说实话，我想可能是使用了一个简短得多的名字：“一个错误”。我想可能有一些情况下，这将/将/工作很好，但至少从它看起来/听起来像一个很不好的主意。

缓存的基本思想是，如果最近使用了某些东西，它可能很快就会再次使用。但是，在这种情况下，几乎是在几乎完全任意的时间清空整个缓存。这威力意义，如果你知道很多关于你的数据访问，并且知道你会加载N个数据，并利用它们相当长一段时间，但是当你加载项N + 1，你可能韩元不再使用以前的N个项目，所以你可以把它们全部清理出去，并在错误的时候为驱逐缓冲区恢复它们。

来源

2011-03-25 16:33:41

这个算法的名字是什么？

回答

相关问题