C ++ LRU кеш - нужны предложения по улучшению скорости - PullRequest
Новая
       52

C ++ LRU кеш - нужны предложения по улучшению скорости

0 голосов
/ 27 апреля 2020

Задача состоит в том, чтобы реализовать O (1) наименьший недавно использованный кэш

Вот вопрос по leetcode
https://leetcode.com/problems/lru-cache/

Вот мой Решение, хотя это O (1), это не самая быстрая реализация
Не могли бы вы дать некоторую обратную связь и, возможно, идеи о том, как я могу оптимизировать это? Спасибо! 


#include<unordered_map>
#include<list>

class LRUCache {

    // umap<key,<value,listiterator>>
    // store the key,value, position in list(iterator) where push_back occurred
private:
    unordered_map<int,pair<int,list<int>::iterator>> umap;
    list<int> klist;  
    int cap = -1;

public:
    LRUCache(int capacity):cap(capacity){

    }

    int get(int key) {
        // if the key exists in the unordered map
        if(umap.count(key)){
            // remove it from the old position 
            klist.erase(umap[key].second);
            klist.push_back(key);
            list<int>::iterator key_loc = klist.end();
            umap[key].second = --key_loc;
            return umap[key].first;
        }
        return -1;
    }

    void put(int key, int value) {

        // if key already exists delete it from the the umap and klist
        if(umap.count(key)){
            klist.erase(umap[key].second);
            umap.erase(key);
        }
        // if the unordered map is at max capacity
        if(umap.size() == cap){
            umap.erase(klist.front());
            klist.pop_front();
        }
        // finally update klist and umap
        klist.push_back(key);
        list<int>::iterator key_loc = klist.end();
        umap[key].first = value;
        umap[key].second = --key_loc;
        return;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Ответы [ 2 ]

2 голосов
/ 27 апреля 2020

Вот некоторые оптимизации, которые могут помочь:

Возьмите этот сегмент кода из функции get: 

    if(umap.count(key)){
        // remove it from the old position 
        klist.erase(umap[key].second);

Выше приведенный выше поиск key на карте дважды. Один раз для метода count, чтобы увидеть, существует ли он. Другой, чтобы вызвать оператор [] для получения его значения. Сохраните несколько циклов, выполнив это: 

auto itor = umap.find(key);
if (itor != umap.end()) {
        // remove it from the old position 
        klist.erase(itor->second);

В функции put вы сделаете следующее: 

    if(umap.count(key)){
        klist.erase(umap[key].second);
        umap.erase(key);
    }

То же, что и get, вы можете избежать избыточного поиска до umap. Кроме того, нет причины вызывать umap.erase только для того, чтобы добавить этот же ключ обратно на карту несколькими строками позже.

Кроме того, это также неэффективно 

    umap[key].first = value;
    umap[key].second = --key_loc;

Как и выше, Излишне ищем key дважды на карте. В первом операторе присваивания key отсутствует на карте, поэтому по умолчанию создается новая пара значений. Второе назначение - это еще один поиск на карте.

Давайте реструктурируем вашу функцию put следующим образом: 

void put(int key, int value) {

    auto itor = umap.find(key);
    bool reinsert = (itor != umap.end());

    // if key already exists delete it from the klist only
    if (reinsert) {
        klist.erase(umap[key].second);
    }
    else {
        // if the unordered map is at max capacity
        if (umap.size() == cap) {
            umap.erase(klist.front());
            klist.pop_front();
        }
    }

    // finally update klist and umap
    klist.push_back(key);
    list<int>::iterator key_loc = klist.end();
    auto endOfList = --key_loc;

    if (reinsert) {
        itor->second.first = value;
        itor->second.second = endOfList;
    }
    else  {
        const pair<int, list<int>::iterator> itempair = { value, endOfList };
        umap.emplace(key, itempair);
    }
}

Это насколько вы можете go, используя std::list. Недостатком типа list является то, что невозможно переместить существующий узел из середины вперед (или назад), не удалив его сначала, а затем добавив обратно. Это пара ненужных выделений памяти для обновления списка. Возможной альтернативой является то, что вы просто используете свой собственный тип двойного списка и вручную исправляете указатель prev / next самостоятельно.

1 голос
/ 27 апреля 2020

Вот мое решение, хотя это O (1), это не самая быстрая реализация, не могли бы вы дать отзыв и, возможно, идеи о том, как мне это оптимизировать? Спасибо!

Собираюсь взять точку selb ie здесь:
Каждый экземпляр if(umap.count(key)) будет искать ключ, а использование umap[key] является эквивалентом для поиска. Вы можете избежать двойного поиска, назначив итератор, который указывает на ключ, с помощью одной операции std::unordered_map::find().

selb ie уже дал код для поиска int get(), вот код для void put()'s one: 

auto it = umap.find(key);
if (it != umap.end()) 
{
    klist.erase(it ->second);
    umap.erase(key);
}

Sidecase:

На данный момент не применимо для вашего кода из-за отсутствия работы ввода и вывода, но в случае использования std::cin и std::cout, вы можете отключить синхронизацию между C и C ++ потоками, а также ie cin from cout в качестве оптимизации: (они связаны по умолчанию) 

// If your using cin/cout or I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
...