Реализация кэша LRU


Что вы думаете о такой реализации LRU-кэш? Я пытаюсь мигрировать в современном C++, так что было бы здорово, если бы вы могли дать мне какие-либо советы здесь. Я слышал, что он не желал использовать сырые указатели, верно? Насчет только внутренне, как в Примере?

Кроме того, поскольку я не могу вернуть nullptr значение в get() метод, что является лучшей альтернативой для этого? Значение по умолчанию как в Примере?

#ifndef __LRU_HPP__
#define __LRU_HPP__
#include <map>
#include<iostream>
#include<assert.h>

template<class T>
struct Default {
  T value;
  Default():value(){}
};

template<class K, class V>
struct node {
  K key;
  V value;
  node<K,V>* next;
  node<K,V>* prev;
  explicit node(K key, V value);
};

template<class K, class V>
class lru {
private:
  node<K,V>* head;
  node<K,V>* tail;
  std::map<K,node<K,V>*> map;
  std::size_t capacity;
  void replace(node<K,V>*);
public:
  explicit lru(std::size_t);
  void put(K key, V value);
  V get(K key);
};

template<class K, class V>
inline node<K,V>::node(K key, V value) {
  this->key = key;
  this->value = value;
}

template<class K, class V>
inline lru<K,V>::lru(std::size_t capacity) {
  assert(capacity > 1);
  this->capacity = capacity;
  this->head = tail = nullptr;
}

template<class K, class V>
void lru<K,V>::put(K key, V value) {
  auto it = map.find(key);
  if (it != map.end()) {
    node<K,V>* temp = it->second;
    temp->value = value;
    replace(temp);
    return;
  }
  if(capacity == map.size()) {
    tail->prev->next = tail->next;
    node<K,V>* target = tail;
    map.erase(target->key);
    tail = tail->prev;
    delete tail;
  }
  node<K,V>* temp = new node<K,V>(key, value);
  temp->prev = nullptr;
  temp->next = head;
  if(head != nullptr)
    head->prev = temp;
  else
    tail = temp;
  head = temp;
  map.insert(std::pair<K,node<K,V>*> {key, temp});
}

template<class K, class V>
V lru<K,V>::get(K key) {
  auto it = map.find(key);
  if(it != map.end()) {
    replace(it->second);
    return it->second->value;
  }
  return Default<V>().value;
}

template<class K, class V>
void lru<K,V>::replace(node<K,V>* temp) {
  if (temp->prev != nullptr)
    temp->prev->next = temp->next;
  if (temp->next != nullptr)
    temp->next->prev = temp->prev;
  if (tail == temp)
    tail = temp->prev != nullptr ? temp->prev : temp;
  if (head != temp) {
    head->prev = temp;
    temp->next = head;
    head = temp;
  }
}
#endif


2037
11
задан 22 марта 2018 в 03:03 Источник Поделиться
Комментарии
3 ответа

Использование Пространства Имен

Я бы поставил все это в некоторые пространства имен, поэтому он не случайно не столкнуться с другими использование названия его определяет.

Я бы, наверное, тоже работают, даже немного сложнее сделать что-то, чтобы скрыть свой node и Default шаблоны. Например, node не должны быть видны на внешний мир, так что, наверное, было бы лучше, определенными внутри lru.

Предпочитаю инициализации для задания

Конструктор такой:

template<class K, class V>
inline node<K, V>::node(K key, V value) {
this->key = key;
this->value = value;
}

...обычно лучше написано что-то вроде этого вместо:

template <class K, class V>
inline node<K, V>::node(K key, V value)
: key(key)
, value(value)
{}

В некоторых случаях, вы должны нас инициализации (как этот), а не назначение. В данном случае, это не является обязательным, но я до сих пор считаю его предпочтительным.

Рассмотреть возможность передачи по ссылке

Прохождения keyS и valueпо стоимости в целом требует копирования. Вы могли бы хотеть рассмотреть, является ли это стоит прохождения, а не по ссылке. Это, как правило, выполняет мало (или ничего) если тип передается в виде "малых", но может существенно улучшить скорость, если тип большие.

Инкапсулируют знания типа ВКУ в тот тип

Сейчас твоя lru класс "знает" (зависит от) внутренности node класс. Я бы вообще предпочел, если только node знал о его внутренности. За одну возможность, вы можете пройти next и prev в конструктор, и пусть его ставят те ценности в node себя:

template <class K, class V>
inline node<K, V>::node(K key, V value, node *prev = nullptr, node *next = nullptr)
: key(key)
, value(value)
, prev(prev)
, next(next)
{}

В этом случае такой код:

node<K, V>* temp = new node<K, V>(key, value);
temp->prev = nullptr;
temp->next = head;

...станет что-то вроде:

node<K, V> *temp = new node<K, V>(key, value, nullptr, head);

Рассмотрим другие структуры данных

Хотя двусвязный список делает работу для разных задач, часто довольно расточительно, через пару указателей на узел в дополнение к данным, вы на самом деле заботитесь о хранении.

Я бы рассмотреть возможность использования односвязанный список. Хотя это может быть не сразу очевидно, как это можно сделать, я достаточно уверен, что вы можете.

Рассмотрим предварительно выделенные хранилища

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

7
ответ дан 22 марта 2018 в 05:03 Источник Поделиться

Заголовок охранники

Код содержит неопределенное поведение с подчеркивания зарезервированы для реализации:


17.6.4.3 зарезервированные имена [зарезервировано.имя]



Стандартная библиотека c++ резервирует следующие виды имен:


  • макросы

  • глобальные имена

  • имена с внешней компоновкой



Если программа заявляет или определяет имя в контексте, где оно зарезервировано, кроме случаев, явно разрешенных настоящим пунктом, его поведение не определено.

[...]

17.6.4.3.2 глобальные имена [глобальный.имя]



Определенные имена и сигнатуры функций, всегда зарезервированы для реализации:


  • Каждое имя, которое содержит двойное подчеркивание __ или начинается с символа подчеркивания, за которым следует прописная
    письмо (2.12) предназначен для выполнения для любого использования.

  • Каждое имя начинается с подчеркивания зарезервированы для реализации для использования в качестве имени в глобальном пространстве имен.


Так переименовать __LRU_HPP__ для LEAST_RECENTLY_USED_HPP или похожие.

Default

Вместо

return Default<V>().value;

использовать

return V{};

Если вы не хотите использовать Default<V> для обеспечения специализации.

Возможная ошибка

Я довольно уверен, что вы имели в виду delete targetне delete tail.

  if(capacity == map.size()) {
tail->prev->next = tail->next;
node<K,V>* target = tail;
map.erase(target->key);
tail = tail->prev;
delete tail; // << ?
}

В противном случае вы в конечном итоге с удален, но не обнуляется tail.

Вызов по значению

Использовать const & аргументы, если вы не собираетесь менять их впоследствии.

7
ответ дан 22 марта 2018 в 06:03 Источник Поделиться


  • Нет никаких оснований для node чтобы узнать ключ.

  • Узел конструктор принимает полностью создан узел, то есть prev и next поля должны быть инициализированы, а также (в nullptr).

  • Списки инициализации членов предпочли конструктор тела. Например,

        lru<K,V>::lru(std::size_t capacity)
    : capacity(capacity)
    , prev(nullptr)
    , next(nullptr) {
    assert(capacity > 1);
    }

  • Возвращая Default<V>.value() не вяжется с целью. По крайней мере, это означает, что клиент не может put такая ценность. Идиоматическое (т. е. стл) способ это сделать get возвращать итератор, с неисправности сигнализируются посредством возвращения end итератор.

  • Последовательность put:

    tail->prev->next = tail->next;
    ....
    tail = tail->prev;
    delete tail;

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

    Рассмотрим переписать:

    ....
    tail = tail->prev;
    delete tail->next;
    tail->next = nullptr;

  • Рецензент сразу замечает еще один "жучок" в put - а именно, что глава не обновляется - и это требует времени и умственной концентрации, чтобы вспомнить capacity > 1 утверждение, что ошибка становится несущественной. Я настоятельно рекомендую фактора удаления хвоста в функцию с именем, которое отражает этот факт. Я предлагаю pop_back_unguarded или что-то вдоль тех линий.

  • Я не думаю, что replace отражает то, что функция на самом деле делает. bump_up возможно?

7
ответ дан 22 марта 2018 в 06:03 Источник Поделиться