Что может вызвать ошибку во время выполнения в этой реализации LRU (hashmap и двусвязный список)? - PullRequest
Новая
       29

Что может вызвать ошибку во время выполнения в этой реализации LRU (hashmap и двусвязный список)?

0 голосов
/ 31 января 2019

Я получаю ошибку времени выполнения на LeetCode, но это прекрасно работает в моей системе Linux в 0,046 пользовательского времени для самого большого тестового случая.Вывод точно соответствует ожидаемому выводу на LeetCode.Мое решение использует хэш-карту и двусвязный список.Хеш-карта хранит итератор в узле связанного списка (в дополнение к паре ключ-> значение), так что список можно обновить O (1) вместо O (n).Он работает для нескольких тестовых случаев, но я получаю ошибку времени выполнения на тестовом примере с размером кэша 512 и инструкциями 2019. 

class LRUCache {
public:
    LRUCache(int _capacity) { capacity = _capacity; }    
    int get(int key) {
        if(hmap.find(key) == hmap.end()) return -1;
        addq(key);
        return hmap[key].first;
    }    
    void put(int key, int value) {
        list<int>::iterator ptr = addq(key);
        hmap[key] = make_pair(value, ptr);
    }
private:
    list<int> q;
    unordered_map<int, pair<int,list<int>::iterator>> hmap;
    int capacity;
    list<int>::iterator addq(int key) {
        if(hmap.find(key) == hmap.end()) {
            if(q.size() == capacity) {
                int to_pop = q.back();
                hmap.erase(to_pop);
                q.pop_back();
            }                        
        }
        else q.erase(hmap[key].second);
        return q.insert(q.begin(), key);
    }
};

1 Ответ

0 голосов
/ 01 февраля 2019

Проблема с вашей get (int key) функцией.Когда вы получаете доступ к кешу, вы должны сделать запись недействительной и обновить ваши итераторы.Вы делаете это с помощью функции addq, но никогда не обновляете соответствующую запись в вашем hmap.Поэтому возникает ошибка во время выполнения, потому что вы затем получаете доступ к итератору, который уже был аннулирован вашей addq функцией.

Глядя на следующий фрагмент: 

if(hmap.find(key) == hmap.end()) return -1;
addq(key);
return hmap[key].first;

addq возвращаетитератор, но вы никогда не обновите итератор в вашей карте, поэтому это должно быть: 

hmap[key].second = addq(key);
...