這個算法的名字是什麼？

注：我試圖找到具體的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

這個算法的名字是什麼？

回答

相關問題