Как называется этот алгоритм?

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

Наименее часто используемый алгоритм кэширования

Это не LRU, поскольку LRU упорядочивает элементы кэша по времени последнего доступа, а не по количеству доступа, как вы.

Answer 2

Разве это не реализация, которую вы могли бы использовать для кэша или файла подкачки?

Он работает с самым последним методом, есть, конечно, другие стратегии, такие как удаление наименее используемых, удаление новейших и т. Д. И т. Д.

Answer 3

Это, конечно, не MRU, но и не совсем LRU. Наличие cur и old создает впечатление, что вы пытаетесь использовать old в качестве буфера выселения.

Однако способ управления cur на самом деле не LRU или MRU - когда ваш кэш заполнен, вы сохраняете только новую запись, и выбрасывание всего остального содержимого в кэш выселения (old). Обычно при добавлении записи размер кэша становится слишком большим, вы выбираете ровно одну существующую запись кэша, которую нужно выбросить (в буфер удаления, если вы его используете). Учитывая то, как вы выкидываете все это, я думаю, вы могли бы назвать это «не самым последним используемым кешем с буфером удаления».

Честно говоря, я думаю, что я , вероятно, использовал бы гораздо более короткое и простое имя: "ошибка". Я предполагаю, что могут быть некоторые обстоятельства, при которых это будет / будет / работать хорошо, но по крайней мере сразу это выглядит / звучит как довольно плохая идея.

Основная идея кеша заключается в том, что если что-то использовалось недавно, то, вероятно, оно скоро будет использовано снова. В этом случае, однако, вы (почти) очищаете весь кэш практически в произвольное время. Это может иметь смысл, если вы знаете лот о вашем доступе к данным и знаете, что вы склонны загружать N элементов данных и использовать их довольно долго, но когда вы загружаете элемент N +1, вы , вероятно, больше не будете использовать предыдущие N элементов, так что вы могли бы также очистить их все и восстановить для буфера выселения, если это было неправильно.